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.