Please show all work! A famous hash function when the key values are positive in

Question

Please show all work!

A famous hash function when the key values are positive integers is the mid-square method, which squares the key value and then takes out the "middle" r digits as the bin number. For instance, when r = 2, and the key value is 3450, we first square 3450 to get 11902500, and then take 02 as the bin number. And if the key value is 3162, we first square 3162 to get 9998244, and then take 98 as the bin number. Now answer the following question assuming that r = 2, and the key values are four digit numbers. (See Lecture 15 notes for guidance) How many buckets(bins) will be needed? For each of the key values 2237, 1697, and 9832, find its corresponding bucket. Give two key values that map to the same bucket(bin). If we need to search for the key value 2015, which bucket(bin) should we search in?

Explanation / Answer

a.) As we are taking 2 number from the middle so minimum and maximum number that can be formed with 2 digits are 00 and 99. Thus , number of buckets required are 100.

b.)For 2237 square is 5004169. So the middle number is 04 which will be its bucket number.

For 1697 square is 2879809. So the middle number is 79 which will be its bucket number.

For 9832 square is 96668224. So the middle number is 68 which will be its bucket number.

c.)So two key values that map to same bucket number are 100 and 1000.

d.)Square of 2015 is 4060225. As it's middle number is 60 so bucket number 60 will be searched for it.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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