A mid-square hash squares the key, extracts R digits from the result\'s middle,

Question

A mid-square hash squares the key, extracts R digits from the result's middle, and returns the remainder of the middle digits divided by hash table size N.

Using a mid square hash, where bucket = 100, and R = 2, where would the following bucket indexes be?
Key = 122
Key = 134

(Key= 122, N = 100, R = 2
122*122 = 14,884
R = 48 OR 88? Which of the following is considered the the middle 2 digits?
R mod 100 = ANS?)  

(Key = 134, N = 100, R = 2
134*134=17,956
R = 2 = 79 or 95? Which of the following is considered the the middle 2 digits?
R mod 100 = ANS)

Is this the correct way to find the mid-square hash bucket? Or am I doing it wrong?

Explanation / Answer

when the number has even number of digits, middle number starts from n/2 and when the number has odd number of digits, middle number starts from (n+1)/2.

so a) key is 122.

Square of key is 14884 and it has odd number of digits.so middle number starts from (5+1)/2=3

Therefore r=2 means 88.

b)key is134.

Square of the key is 17956 and it has odd number of digits. so middle number starts from (5+1)/2=3.

Therefore r=2 means 95.

Your way of approach is correct . if middle r digits exceed the size of bucket, divide the middle r digits by size and the obtained remainder will be the answer.

Please feel free to post in comments box if you have any queries.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.