Chaining

Chaining is a hashing technique using which we can avoid the collision (i.e. two different elements have the same hash value). In which we use the link list to store the elements in the hash table which map to the particular value. So, to store an element in the hash table we will simply insert the element into the particular link list. If there is collision then we will simple store both the element in same link list.

Here I am using Hash function: h= value%10;

In the above image, we can clearly see that if we insert 18, 21, 89 then no collision occurs but after that if we insert 58, 68 then collision will occur because hash value of 58 and 68 is 8 which is same as the hash value of 18(already inserted) so here chaining come into picture, it so easy to resolve the collision in chaining, we just need to insert 58, 68 in the 8th indexed link list.

Now let's talk about the Time Complexity:

The average cost of a lookup depends only on the average number of the keys per linked list - (i.e. it is roughly proportional to the load factor).

The worst-case scenario is when all the entries are inserted into the same linked list (i.e. if suppose if I inserted the elements 8, 18, 28, 38, 48, 58 into the hash table then all these elements will map to the same indexed position which increases the size of the linked list in 8th indexed so then if we try to access the element 48 the it will take not than O (1) time because I already told above that lookup time depends on the number of the keys per linked list.

Contributor's Info

Created: Edited:
0Comment