Hash Tables
A hash table is a data structure that maps keys to values using a hash function, providing average-case O(1) time complexity for lookups, insertions, and deletions. It is one of the most widely used data structures in software development — Python’s dict, JavaScript’s objects and Map, Java’s HashMap, and Go’s map are all hash table implementations.
The core mechanism is straightforward: a hash function converts a key into an array index, and the value is stored at that index. When two keys hash to the same index (a collision), the table must resolve it — either by chaining entries in a linked list or by probing for the next open slot.
Key Concepts
Hash Functions — A good hash function distributes keys uniformly across the table, minimizing collisions. It must be deterministic (same key always produces the same hash) and fast to compute. Cryptographic hash functions (SHA-256) are overkill for hash tables; simpler functions like MurmurHash or FNV are preferred.
Collision Resolution:
| Strategy | Mechanism | Trade-off |
|---|---|---|
| Chaining | Each bucket holds a linked list of entries | Simple, but cache-unfriendly |
| Open addressing (linear probing) | Probe sequential slots | Cache-friendly, but clustering degrades performance |
| Robin Hood hashing | Steal from “rich” entries during probing | More uniform probe lengths |
Load Factor — The ratio of entries to buckets (n/m). As load factor increases, collision probability rises. Most implementations resize (typically doubling) when load factor exceeds 0.7–0.75, giving O(1) amortized insertion.
Worst Case — If all keys hash to the same bucket, operations degrade to O(n). This is rare with good hash functions but exploitable — hash flooding attacks send crafted keys to cause worst-case behavior, which is why languages like Python randomize hash seeds.
Common Pitfalls
- Using mutable objects as hash keys — if the object changes after insertion, the hash changes and the entry becomes unreachable
- Assuming insertion order is preserved — only guaranteed in Python 3.7+ dicts and specific implementations
- Ignoring hash collision attacks in security-sensitive contexts
Best Practices
- Prefer language-standard hash map implementations over custom ones
- Pre-size the hash table when the approximate number of entries is known to avoid unnecessary resizing
- Use immutable keys (strings, tuples, frozen sets) to prevent hash invalidation
Related Topics
- data-structures-overview — Hash tables in the broader context of data structure selection
- arrays — The underlying storage mechanism for most hash table implementations