Two Primary Collision Resolution Techniques are present in DSA: – Chaining and Open Addressing.
Chaining
Chaining is the technique where each bucket is the hash table points to a linked list (or chain) of entries that have the same hash code. When a collisions occurs, the new entry is simply added to the linked list at the corresponding bucket.
- Separate Chaining
- Each Bucket contains a pointer to the head of a linked list.
- All entries that has to the same bucket are stored in the Linked List.
- Insertion
- When inserting a new entry, the hash function is used to determine the appropriate bucket.
- The entry is then added to the linked list in that bucket.
- Search
- To find an entry, the hash function determine the bucket.
- The linked list in that bucket is traversed to find the desired entry.
- Deletion
- To hash function locates the bucket.
- The linked list is traversed to find and remove the entry.
Open Addressing
Open Addressing is a collision resolution technique where all are stored directly in the hash table array. When a collision occur, the algorithm searches for the next available slot according to a specific probing sequence.
- Probing Sequence
- When a collision occurs, open addressing searches for the next available slot using a probing sequence.
- Common probing methods include linear probing, quadratic probing and double hashing.
- Insertion
- The hash function determines the initial buckets.
- If the bucket is occupied, the problem sequence is followed to find the next available slot.
- Search
- The hash function determines the initial bucket.
- If the bucket does not contain the desired entry, the probing sequence is followed to check subsequent.
- Deletion
- Special handling is required to ensure that the probing sequence remains intact and that subsequent searches can still locate the correct entries.
