Data Structures For Storing Chains

What is Collision?

Since a hash function gets us a small number for a key which is a big integer or string, there is a possibility that two keys result in the same value. The situation where a newly inserted key maps to an already occupied slot in the hash table is called collision and must be handled using some collision handling technique....

What are the chances of collisions with the large table?

Collisions are very likely even if we have a big table to store keys. An important observation is Birthday Paradox. With only 23 persons, the probability that two people have the same birthday is 50%....

How to handle Collisions?

There are mainly two methods to handle collision:...

Separate Chaining:

The idea behind separate chaining is to implement the array as a linked list called a chain....

Advantages:

Simple to implement.  Hash table never fills up, we can always add more elements to the chain.  Less sensitive to the hash function or load factors.  It is mostly used when it is unknown how many and how frequently keys may be inserted or deleted....

Disadvantages:

The cache performance of chaining is not good as keys are stored using a linked list. Open addressing provides better cache performance as everything is stored in the same table.  Wastage of Space (Some Parts of the hash table are never used)  If the chain becomes long, then search time can become O(n) in the worst case Uses extra space for links...

Performance of Chaining:

Performance of hashing can be evaluated under the assumption that each key is equally likely to be hashed to any slot of the table (simple uniform hashing)....

Data Structures For Storing Chains:

1. Linked lists...