Concept · Algorithms & complexity
Hash tables
Hash a key to pick a bucket, and get average O(1) insert, lookup and delete — the structure behind maps, sets, caches and indexes.
A hash table stores key–value pairs in an array of buckets. A hash function turns the key into a number, and that number modulo the array size picks the bucket. Lookup repeats the same calculation and checks one bucket, so insert, lookup and delete take O(1) on average, regardless of how many items are stored. Go's map, JavaScript's Map and Python's dict are hash tables.
Collisions and resizing
Different keys can land in the same bucket — a collision. Implementations handle it in one of two ways:
- Chaining: each bucket holds a small list (or array) of entries, scanned on lookup.
- Open addressing: on a collision, probe other slots in a fixed sequence until a free one is found.
Either way, performance depends on the load factor — items divided by buckets. As it rises, buckets get longer, so tables resize (typically doubling) and rehash every entry when a threshold is crossed. One insert then costs O(n), but resizes are rare enough that inserts stay amortized O(1).
A good hash function spreads keys evenly. A poor one, or an attacker who can choose keys that collide, pushes everything into a few buckets and degrades lookups to O(n) — the basis of hash-flooding denial-of-service attacks, which is why Go and other runtimes seed their hash functions randomly per process.
What hash tables don't do
- No order. Iterating a Go map visits keys in an unspecified order (deliberately randomised). Need sorted keys? Collect and sort them, or use a tree.
- No range queries. "All keys between A and F" requires a scan; a B-tree answers it directly.
- Keys must be hashable and comparable. In Go, slices and maps can't be map keys; in JavaScript, object keys are compared by reference.
Where they show up
Hash tables are the workhorse for de-duplication, counting, joining data in memory, caches (an LRU cache pairs one with a linked list), and turning O(n²) "search inside a loop" code into O(n). Databases use them for hash joins and hash indexes, and distributed systems extend the idea across machines with consistent hashing. See the data structures lesson for worked examples.