search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
0 votes
10 views
In Mid Square Method(Hashing), we square the given number and then use appropriate bits from the middle. Can we have so many answers for a particular question?

On what basis we choose the middle digit?

What if the square is 4 digit 1234, then what will be the middle value? Will it be 23 or 2 or 3.

Please explain.
in DS 9 points 10 views

1 Answer

0 votes

@Lata Patwal

 

Mid-Square hashing ..

 

Mid-Square hashing is a hashing technique in which unique keys are generated. In this technique, a seed value is taken and it is squared.

Then, some digits from the middle are extracted. These extracted digits form a number which is taken as the new seed. This technique can generate keys with high randomness if a big enough seed value is taken. However, it has a limitation.

As the seed is squared, if a 6-digit number is taken, then the square will have 12-digits. This exceeds the range of int data type. So, overflow must be taken care of. In case of overflow, use long long int data type or use string as multiplication if overflow still occurs….

The chances of a collision in mid-square hashing are low, not obsolete. So, in the chances, if a collision occurs, it is handled using some hash map…

Example:

Suppose a 4-digit seed is taken. seed = 4765 Hence, square of seed is = 4765 * 4765 = 22705225 Now, from this 8-digit number, any four digits are extracted (Say, the middle four).

So, the new seed value becomes seed = 7052 Now, square of this new seed is = 7052 * 7052 = 49730704 Again, the same set of 4-digits is extracted. So, the new seed value becomes seed = 7307 . . . .

 

This process is repeated as many times as a key is required....

Mid square technique takes a certain number of digits from the square of a number. This number extracted is a pseudo-random number, which can be used as a key for hashing….

 

Algorithm:

1. Choose a seed value. This is an important step as for same seed value, the same sequence of random numbers is generated.

 

2. Take the square of the seed value and update seed by a certain number of digits that occur in the square. Note: The larger is the number of digits, larger will be the randomness.

 

3. Return the key.…

 

https://www.youtube.com/watch?v=LXWSeRIE2Ak 

 

https://www.youtube.com/watch?v=mxrBibfna7A  

 

https://www.youtube.com/watch?v=EMK6d25aiAQ 

633 points
...