1. 2.1 3. , Assume that a hash table has 11 slots and the hash function...

 

Transcribed Image Text:

1. 2.1 3. , Assume that a hash table has 11 slots and the hash function is h(k) = k mod 11. Demonstrate the insertion into the hash table of the following sequence of keys with collision resolved by chaining: 5, 28, 19, 15, 20, 33, 12, 17, 10, 13 Show all the steps ; Consider a hash table of size m=1000 and a corresponding hash function h(k) given by the multiplication method for A (5 - 1)/2 = 0.6180... (as discussed in the lecture slides). Compute the locations to which the following sequence of keys are mapped: 61, 62, 63, 64, 65. Show all the steps Open addressing is another technique of collision resolution. a) [4 Pts] What are the three hashing techniques used in open addressing? b) [6 Pts] Which of the above techniques can generate primary clustering? Explain how primary clustering can be formed using an example. Why primary clustering is not desirable? c) [6 Pts] Which of the above techniques can generate secondary clustering? Explain how secondary clustering can be formed using an example. d) [4 Pts] Which of the above techniques can eliminate both primary clustering and secondary clustering? Explain using an example. 1. 2.1 3. , Assume that a hash table has 11 slots and the hash function is h(k) = k mod 11. Demonstrate the insertion into the hash table of the following sequence of keys with collision resolved by chaining: 5, 28, 19, 15, 20, 33, 12, 17, 10, 13 Show all the steps ; Consider a hash table of size m=1000 and a corresponding hash function h(k) given by the multiplication method for A (5 - 1)/2 = 0.6180... (as discussed in the lecture slides). Compute the locations to which the following sequence of keys are mapped: 61, 62, 63, 64, 65. Show all the steps Open addressing is another technique of collision resolution. a) [4 Pts] What are the three hashing techniques used in open addressing? b) [6 Pts] Which of the above techniques can generate primary clustering? Explain how primary clustering can be formed using an example. Why primary clustering is not desirable? c) [6 Pts] Which of the above techniques can generate secondary clustering? Explain how secondary clustering can be formed using an example. d) [4 Pts] Which of the above techniques can eliminate both primary clustering and secondary clustering? Explain using an example.