Collision occurs when two different keys hash to the same value. Collision resolution techniques are used to handle collisions and maintain the integrity of the hash table.
The purpose of collision resolution during insertion is to locate an open location in the hash table when the record’s home position is already taken.
• Common collision resolution techniques include chaining and open addressing.
Open Addressing:
In Data Structures and Algorithms (DSA), Open Addressing is collision resolution technique used in hash tables. In Open Addressing, when a collision occurs (i.e., when a key hashes to an index that is already occupied), the algorithm probes for an alternative location within the hash table to place the key.
There are several variations of Open Addressing, including:
1.) Linear Probing: In linear probing, if a collision occurs, the algorithm linearly searches for the next available slot in the hash table, starting from the original hashed index. This can lead to clustering of elements in the hash table.
2.) Quadratic Probing: In quadratic probing, the algorithm uses a quadratic function to probe for the next available slot after a collision. This helps reduce clustering compared to linear probing.
3.) Double Hashing: Double hashing uses a secondary hash function to determine the step size for probing. If a collision occurs, the algorithm uses the secondary hash function to compute the next probe index.
Open Addressing can be more memory-efficient than chaining because it avoids the overhead of maintaining linked lists. However, care must be taken to handle clustering and ensure efficient probing sequences to maintain good performance.
Separate Chaining:
In Data Structure and Algorithms (DSA) ,Separate chaining is defined as a method by which linked lists of values are built in association with each location within the hash table when a collision occurs.
The figure shows incidences of collisions in different table locations.
- Its worst-case complexity for searching and deletion is o(n)..
Separate chaining is efficient when the hash function evenly distributes elements across the hash table and when the linked lists don’t become too long. However, if many elements hash to the same index, the performance can degrade, as the time complexity of operations like search and insertion becomes closer to linear time with respect to the number of elements in the table.
