Hash Table
An hash table is a key-value data structure.
From the key, we derive a hash code and from a hash code an index that points to the value.
When two value has the same hash code or index, there is a collision. One of the solution to fix a collision is chaining. For the same hash code or index, a chain of values is mapped.
There is multiple ways to chain values:
- linked list: the most common, the worst case lookup is O(n)
- binary search tree: rarely used except for non-uniform distribution, the worst case lookup is O(log(n))
- open addressing with linear probing: look for the next available spot in the table, sometimes at fixed offset; fast and space-efficient, but can cause clustering issue (when there is no available spot)
- quadratic probing with double hashing
The purpose of hash-table to provide a constant-time for insertion, find, or delete operations.
Resources
| https://www.youtube.com/watch?v=shs0KM3wKv8 |