Data Structures Questions Medium
Linear probing and coalesced hashing are two different collision resolution techniques used in hash tables.
Linear probing is a simple and straightforward method where, when a collision occurs, the next available slot in the hash table is searched sequentially until an empty slot is found. The main difference between linear probing and other collision resolution techniques is that it does not use any additional data structure to store the collided elements. Instead, it directly stores them in the hash table itself. This means that the elements are stored in a linear manner, hence the name "linear probing". However, one drawback of linear probing is that it can lead to clustering, where consecutive elements are stored together, causing longer search times.
On the other hand, coalesced hashing is a more sophisticated collision resolution technique that uses an auxiliary data structure, typically a linked list, to store collided elements. When a collision occurs, the collided element is stored in the auxiliary data structure, and a reference to that element is stored in the hash table. This allows for better utilization of the hash table and reduces clustering. In coalesced hashing, the auxiliary data structure is typically implemented as a linked list, where each node contains the collided element and a pointer to the next node. The last node in the linked list points to an empty slot in the hash table, indicating the end of the chain.
In summary, the main difference between linear probing and coalesced hashing is that linear probing directly stores collided elements in the hash table itself, while coalesced hashing uses an auxiliary data structure to store collided elements and references to them in the hash table. Coalesced hashing provides better utilization of the hash table and reduces clustering compared to linear probing.