Data Structures: Hash Table Collision Handling
Collision Handling: Collision handling comes into effect when two pieces of data are hashed to the same spot inside of a hash table. The type of collision handling determines how the hash table attempts to find an empty slot for the new piece of data. There are a bunch of collision handling algorithms out there, but I’ll stick to some of the more common ones.
Linear Probing: In linear probing, if a piece of data is hashed to an occupied space, the hash table will go through the rest of the table slot by slot until it finds a viable one. Probes the rest of the table linearly until it finds a viable slot.
External Chaining: In external chaining, the data is simply linked to the last piece of data added to that slot. Essentially this means you’ll have linked lists of data inside of a hash table slot containing more than one piece of data.
Quadratic Probing: Quadratic probing is just like linear probing, but instead of going through the rest of the list, it changes the index to index = index + i + i^2 where i is the number of collisions the data has encountered. This type of collision handling is good for attempting to spread out data in the case that you have a weak hash function or your data is piled up in a particular area.