(1) Consider inserting the keys 2, 21, 3, 58, 11, 42, 34 into a hash table...

 

Transcribed Image Text:

(1) Consider inserting the keys 2, 21, 3, 58, 11, 42, 34 into a hash table of length m 10 with the hash function h(k) = k mod 10. (a) (2 points) Illustrate the result of inserting these keys using linear probing to resolve collisions. (b) (2 points) Illustrate the result of inserting these keys using chaining to resolve collisions. (2) Consider inserting the keys 8, 5, 14 into a hash table of length m = 8 with the hash function h(k) = [m(kA [kA])] where A = 0.625. (a) (2 points) Illustrate the result of inserting these keys. (b) (1 point) Now compute the hash function of the key k = 14 using the alternative algorithm described below. You can assume we have a word size w = 4. Since m = 8 = 23. p = 3. Since A = 0.625 = 10/24 = 10/2, s = 10. Alternative Algorithm: Compute ks and convert it to a bi- nary number. This number will consist of <2w bits. Look at the rightmost w bits. Of those bits, convert the leftmost p bits back to an integer. This integer is your hash table slot. (1) Consider inserting the keys 2, 21, 3, 58, 11, 42, 34 into a hash table of length m 10 with the hash function h(k) = k mod 10. (a) (2 points) Illustrate the result of inserting these keys using linear probing to resolve collisions. (b) (2 points) Illustrate the result of inserting these keys using chaining to resolve collisions. (2) Consider inserting the keys 8, 5, 14 into a hash table of length m = 8 with the hash function h(k) = [m(kA [kA])] where A = 0.625. (a) (2 points) Illustrate the result of inserting these keys. (b) (1 point) Now compute the hash function of the key k = 14 using the alternative algorithm described below. You can assume we have a word size w = 4. Since m = 8 = 23. p = 3. Since A = 0.625 = 10/24 = 10/2, s = 10. Alternative Algorithm: Compute ks and convert it to a bi- nary number. This number will consist of <2w bits. Look at the rightmost w bits. Of those bits, convert the leftmost p bits back to an integer. This integer is your hash table slot.