A hash function turns a key into an array index. Two keys landing in the same bucket is a collision.
If you had to keep one data structure and throw the rest away, it should be the hash table. It is the reason a dictionary lookup in your language of choice is instant, the reason a cache can answer in microseconds, the reason a database can find a row without scanning the table, and — increasingly — part of how a vector store keeps track of which metadata belongs to which embedding. It is so deeply embedded in everything that most engineers stop seeing it. This is a refresher on what is actually happening, and where it quietly breaks.
The one idea
A hash table stores key-value pairs in an array. To decide where in the array a key goes, it runs the key through a hash function — a deterministic function that turns any key into a number — and takes that number modulo the array size to get an index (a “bucket”). To look the key up again, it runs the exact same function and goes straight to that bucket.
That is the whole trick. Instead of searching for a key (O(n)), you compute its location (O(1)). The diagram above shows it: "user:42" hashes to bucket 1, and every future lookup of "user:42" computes bucket 1 again and reads it directly. No scan.
Collisions, and why the load factor matters
The catch is right there in the picture. "user:87" and "user:19" both hash to bucket 3. That is a collision, and it is not an error — it is a mathematical certainty. You are mapping a huge space of possible keys onto a small array, so pigeonhole says keys will share buckets. The design question is not “how do I avoid collisions” but “how do I stay fast when they happen.”
Two classic strategies:
- Chaining. Each bucket holds a small list. Collisions get appended, as with
user:19in the diagram. Lookup means hashing to the bucket, then walking a (hopefully tiny) list. - Open addressing. On collision, probe to the next free slot by some rule. No side lists; everything lives in the array, which is friendlier to the CPU cache.
Both stay fast only while collisions stay rare, and that is governed by the load factor — the ratio of stored entries to buckets. Push it too high and buckets get crowded, chains lengthen, and your beautiful O(1) degrades toward O(n). This is why real hash tables resize: when the load factor crosses a threshold (commonly around 0.7), they allocate a bigger array and rehash everything into it. That resize is an occasional O(n) hiccup hiding behind the average O(1) — and if you have ever seen a latency spike that correlates suspiciously with a cache filling up, you have met it.
Where it shows up (which is: everywhere)
- In-memory caches. Redis and Memcached are, at heart, giant hash tables with eviction bolted on. The O(1) get is the hash lookup.
- Database indexes. Hash indexes give O(1) exact-match lookups. (B-trees win when you need ranges — a topic for its own post.)
- Deduplication. “Have I seen this before?” is a hash-set membership test. Content-addressed storage, Git object stores, and crawler seen-sets all lean on it.
- Partitioning and sharding. Deciding which server owns a key is
hash(key) mod N. That naive version has a nasty failure mode when N changes — which is exactly why consistent hashing exists. - Language internals. Python dicts, Java
HashMap, Go maps, JavaScript objects — hash tables, all the way down.
The AI-era angle
Modern AI infrastructure did not retire the hash table; it gave it new jobs.
Vector databases are hybrids. The approximate-nearest-neighbor index handles “what is similar,” but the exact lookups — fetch the document for this ID, filter by this tenant, attach this metadata — are still hash-table territory. Semantic search and exact match live side by side, and confusing which one you need is a common source of “why can’t it find the row I know is there” bugs.
Prompt and embedding caches are hash tables with a twist. Prompt caching keys on a hash of the prompt prefix; an embedding cache keys on a hash of the input text so you never pay to re-embed the same chunk twice. The economics of a RAG pipeline often come down to how good that cache hit rate is — which is a load-factor and key-design question.
Feature stores and dedup at training scale. Deduplicating a training corpus so the model does not memorize the same document a thousand times is a hash-set problem at terabyte scale. When exact hashing gets too expensive, you reach for a probabilistic cousin — the Bloom filter — which trades a little accuracy for a lot of memory.
What to keep in your head
- Average O(1), worst-case O(n). The average is what you get with a good hash function and a sane load factor. The worst case is what you get when both fail at once — and an attacker who can force collisions can deliberately drive you into it (hash-flooding denial of service). This is why hash functions in security-sensitive contexts are randomized per process.
- A bad hash function silently kills performance. If your hash clusters keys into a few buckets, you have effectively built a linked list with extra steps. When you provide your own key type, its hash matters.
- Hashing is not encryption and not fingerprinting-for-integrity. The hash in a hash table optimizes for speed and spread. Cryptographic hashing (which shows up when we get to TLS) optimizes for being impossible to reverse or forge. Same word, different jobs.
The hash table is fifty years old and sits under the newest systems we build. Understanding it is not nostalgia — it is knowing why your cache is fast, when it will stop being fast, and where the next bottleneck is hiding.