Question

Show the result of inserting 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hashtable with collision resolution by chaining.

The table should have 9 slots and use h(k) = k mod 9 for the hash function.

Now, show the result of inserting the first 6 of these into another hashtable using linear probing.

For these inserted entries, what was the largest number of entries you had to search before finding an open slot?

Answer 1

In the question, firstly the result is to be shown by using the collision reolution by chaining. For deriving out the solution we need to create the hash table according to the given values. The hash table is formed below:

Item	Hash value calculation	Hash value
5	5%9=5	5
28	28%9=1	1
19	19%9=1	1
15	15%9=6	6
20	20%9=2	2
33	33%9=6	6
12	12%9=3	3
17	17%9=8	8
10	10%9=1	1

Since from the above we can see that the collision takes place in h(28)=h(19)=h(10)=1

and in

h(15)=h(33)=6

Now according to chaining process, we allocate several items at the same location. Now these several items will be located to the same location only when they have same hash value.

So the items mentioned will be allocated to the 9 slots as mentioned(0 to 8) as follows, also note that in the chaining method the chains will be formed at the same location for several items:

The above is the way to store the items into hashtable with collision resolution by chaining.

_____________________________________________________________________________________

Collision resolution by linear probing.

In linear probing technique, collision is resolved by searching linearly in the hash table until an empty location is found.

Hence, from the reference of the table formed above, the insertion of the items happen in the following steps:

In the above image all the steps are mentioned as of how, when and at what position the item has been entered.

In Steps 3,5,6,7 and 9 the linear probing took place as the items required to search for the location for themselves.

However, if we see that in Step 9 where 10(item) was to be given the location 1 according to the hash value, it couldn't find the location till slot 8, hence went to the starting postion  0, making the item 10 to move the largest number of steps i.e. 8 to find the place for itself.

So for these inserted entries, the largest number of entries we had to search before finding an open slot is 8 entries for item 10.