Every time you write d["key"], a hash table is at work. The idea is simple: convert the key into a number, use that number as an index in an array, and access the data directly.
Conflicts are bound to happen
The key space is infinite, but the array is finite, so there are certainly two different keys that map to the same index. There are two common ways to handle this:
- Append to list: Each cell contains a list; if there is a key collision, append to that list
- Linear search: If the cell is already occupied, find the next available cell
The second method is more CPU-buffer-friendly, so it is common in modern libraries, even though removing elements is more complex.
The load factor determines the speed
The load factor is the ratio of the number of elements to the number of cells. When it exceeds a threshold—typically around 0.7—collisions spike and lookups slow down. At that point, the table must allocate a new array twice as large and then re-hash the entire table.
An insertion that triggers rehashing can be thousands of times slower than normal. On average, it’s still a constant, but if you’re writing a latency-sensitive system, that overhead could be the difference between success and failure.
A Few Practical Tips
- If you know the number of elements in advance, allocate the capacity right from the start to avoid having to re-hash multiple times
- The key must be immutable—modifying the key after insertion causes the element to be lost, because the hash value has changed
- A hash table does not preserve insertion order unless the language guarantees it; do not rely on any observed order
Thảo luận