Question

5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table after inserting the sequence of 8 numbers picked in the question above. iii. (3) Calculate the average number of probes required when an element is present. Show your work. (b) Consider a hash table of size M = 10 and the hash function h(x) = r mod 10. i. (2) The hash table is initially empty. Now insert the keys 23, 45, 55, 73 and 83 into the hash table, in this order, using linear probing. Show the contents of the hash table after all the keys are inserted. Note: Indexing in the table starts with 0. ii. (2) Show the contents of the above hash table after deleting 73 and then inserting 93. (c) Consider a hash table of size M = 10 and the hash function h(x) = r mod 10 with double hashing to resolve collisions. The secondary hash function is h2(x) = 5 – (r mod 5). i. (3) The hash table is initially empty. Now insert the keys 23, 45, 62, 43, and 12 into the hash table, in this order. For each key, specify the array locations which are probed and the location where the key is inserted. ii. (2) Give an example of two more keys, where the first key can be inserted, but the second one cannot be, even though there are empty cells in the table of the previous question (part c(i)).

Answer 1

Q a)

h(x) = x mod 5
1)
Numbers-> 11 34 76 55 24 98 66 45 13

2)
Calculate hash of each element and chain elements
Bucket Elements
0:   55->45
1:   11->76->66
2:   13->
3:   98->
4:   34->24

3)
Average Probes = Total probes/Total number of elements inserted
= (1+1+2+1/8) = 0.5
1 for 45, 76, 24 and 2 for 66

--------------------------------------------------------------------------------------------------------------------------------

Q b)
h(x) = x mod 10
1)
key=23, hash=3, index=3
key=45, hash=5, index=5
key=55, hash=5, index=6 (after 1 probe)
key=73, hash=3, index=4 (after 1 probe)
key=83, hash=3, index=7 (after 3 probes)

Key	0	1	2	3	4	5	6	7	8	9
element				23	73	45	55	83

2)

delete 73

Key	0	1	2	3	4	5	6	7	8	9
element				23		45	55	83

Insert 93, hash=3 index=4 after 1 probe

Key	0	1	2	3	4	5	6	7	8	9
element				23	93	45	55	83

---------------------------------------------------------------------------------------------------------------------------------------

Q c)
h1(x) = x mod 10
h2(x) = 5-(x mod 5)
1)
->key=23
h1(x)=3
h2(x)=5-(3)=2
index=3 (no probing)

->key=45
h1(x)=5
h2(x)=5-(0)=5
index=5 (no probing)

->key=62
h1(x)=2
h2(x)=5-(2)=3
index=2 (no probing)

->key=43
h1(x)=3
h2(x)=5-(3)=2
index=3 (full), 5(full), 7(empty)
index = 7 ( after 2 probes)

->key=12
h1(x)=2
h2(x)=5-(2)=3
index=2 (full), 5(full), 8(empty)
index = 8 ( after 2 probes)

2)
Example 45,55
h1(45) = 5, h2(45)=5
h1(55) = 5, h2(55)=5
once 45 is inserted, 55 will probe at 5,0,5,0.. indices