Hashing and Nearest-Neighbor Search — The Groundwork Under Vector Search

Two inventions that made looking things up fast — the exact-match hash table, and LSH and HNSW for searching by meaning — from zero assumed knowledge. What is actually running underneath RAG and every vector database.

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

Finding one book in a warehouse of a million

Picture a warehouse holding a million books stacked in no particular order. To find the one you want, there is nothing to do but check them one at a time from the end of the row. On a bad day that is a million checks. This is a linear scan: work proportional to the amount of data $n$, or $O(n)$.

Shelve the books alphabetically by title and you can open the middle of the collection and ask "is my book before this or after it?", halving the search each time. A million books are reached in about twenty steps. That is binary search, $O(\log n)$.

But there is a more radical option: stop searching. "A book with this title works out to shelf number 814" — if you run the same calculation when you file it and when you fetch it, there is nothing to sort and nothing to narrow down; your hand goes straight to the shelf. Deciding the location by computing it is the idea behind hashing.

Hash tables: computing the address

A hash function turns any piece of data (a key) into an integer within a fixed range. The most naive form looks like this.

In words: take the key $k$ (an integer built from the character codes if it is a string), divide by the number of shelves $m$, and use the remainder as the location. That is the whole formula. The remainder always lands between $0$ and $m-1$, so every key falls on some shelf, and the same input always produces the same output — which is why the place you stored it and the place you look are the same place.

Read aloud, it is a rule which says: shelf number = the item's own number, divided by how many shelves exist, keep what is left over. The everyday version is a coat check with 100 hooks and a ticket numbered 1,234: you count off hooks, going around and around, until the ticket runs out, and stop at hook 34. Nobody has to write down where the coat went, because the ticket recomputes the answer on the way back.

This is what sits behind a Python dict or a JavaScript object: a key fetches its value in $O(1)$ on average — essentially constant time whether you hold a thousand entries or a billion. The data structure tour drew the map of the whole family; this article zooms in on the "looking things up" part of it.

Collisions — two keys, one address

There are only $m$ shelves and effectively an unlimited supply of possible keys, so different keys landing on the same shelf is unavoidable (the pigeonhole principle). That is a hash collision, and there are two main answers to it.

• Chaining: make each shelf a list and hang everything that lands there off it in a chain. A lookup scans linearly, but only within that one shelf
• Open addressing: if the shelf is taken, try the next shelf according to a fixed rule

Either way, performance is governed by the load factor — how many items are stored relative to the number of shelves. With plenty of empty shelves, collisions are rare and lookups stay $O(1)$. Pack them too tightly and the chains grow until you are back to a linear scan. So implementations watch the load factor and, once it crosses a threshold (0.75 is a common one), double the number of shelves and re-file everything. That relocation is why an occasional insert into a dict is much slower than the rest.

Hashing can only find exact matches

The hash table so far has a surprising weakness. A good hash function is deliberately designed for the avalanche effect: change one bit of the input and the output jumps to something unrelated. That is ideal for scattering collisions evenly, but it also means "cat" and "cats" land on completely unrelated shelves. The ability to keep similar things near each other is exactly zero.

And yet the kind of search modern AI needs is precisely "find me the similar ones". Text and images are converted into embedding vectors — strings of a few hundred numbers whose directions align as their meanings converge — which turns retrieval into the problem of finding the stored vectors closest to a query vector: nearest-neighbor search. This is also what happens when RAG pulls up relevant documents.