Page 196 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 9: Hashing

Figure 9.1: Hash Table Implementation using Overflow Chaining for Collision Handling Notes

Consider using division method of hashing store the following values in the hash table of
size 11:
25, 45, 96, 101, 102, 162, 197, 201
Use sequential method for resolving the collisions.
Since division method of hashing is to be used the hash function his:
h(key) = key mode 11, where key is the value to be stored.

I start with the value 25, and compute the hash value using 25 as key. The hash value is h(25) =
25 mod 11 = 3. Therefore store 25 at the index 3 in the table.
For 45, h(45) = 45 mod 11 = 1, hence place 45 at the index 1.
For 96, h(96) = 96 mod 11 = 8,

∴ store 96 at index 8.
For 101,h(101) = 101 mod 11 = 2,
∴ store 101 at index 2.
For 102, h(102) = 102 mod 11 = 3, there is a collision, therefore you find a location closer to location

at index 3 which is empty to accommodate 102, you see that the location at index 4 is empty.
∴ store 102 at index 4.
For 162, h(162) = 162 mod 11 = 8, again there is a collision, therefore you find a location closer

to location at index 8 which is empty to accommodate 162, you see that location at index 9 is
empty.
∴ store 162 at index 9.

For 197, h(197) = 197 mod 11 = 10, store 197 at index 10.
For 201, h(20 1) = 201 mod 11 = 3, again there is a collision, therefore you find a location closer

to location at index 3, which is empty to accommodate 201, you see that location at index 5 is
empty.
∴ store 201 at index 5.

LOVELY PROFESSIONAL UNIVERSITY 191