Consider an extendable hash structure where buckets can hold 3 search key values. The entries with the key values listed below are inserted in

Question

48 users unlocked this solution today!

 

Consider an extendable hash structure where buckets can hold 3 search key values. The entries with the key values listed below are inserted in the following order: 57, 28, 26, 98, 38, 79, 7, 109, 30 The hash function given is h(x) = x mod 16. The hash value of a search key is a 4-bit binary value. Use the most significant bit of the hash value during insertion. (a) [25 pts] Insertion of which key values leads to bucket splits? Which of those splits causes the bucket address table to double? (b) [15 pts] After inserting all key values, i. What is the global depth of the bucket address table? ii. What is the local depth of the bucket that contains 26? iii. What is the local depth of the bucket that contains 109? iv. What is the local depth of the bucket that contains 7? v. What is the local depth of the bucket that contains 79?