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.

Doing it exactly means computing the distance from the query to every vector and taking the smallest — back to scanning the entire warehouse. At hundreds of millions of vectors and hundreds of dimensions, every query makes the user wait. So in practice we give up on the exact top result and settle for finding something that is almost certainly the top result: approximate nearest neighbor search (ANN). Its two dominant schools are LSH and HNSW, and we look at both next.

LSH: deliberately building a "sloppy" hash

LSH (Locality-Sensitive Hashing) inverts the premise. Instead of the avalanche effect, it deliberately designs hash functions where the more similar two inputs are, the more likely they are to land on the same shelf.

The best-known construction for cosine similarity, the random hyperplane method, is almost anticlimactically simple. Stand a randomly oriented board (a hyperplane) in the space; if a vector falls on the front of it, the bit is 1, and if behind, 0. That is one bit of hash. Stand up sixteen boards and you have sixteen bits, which is up to 65,536 shelves.

Two vectors pointing in similar directions tend to end up on the same side of a randomly placed board. Written as a formula, the probability that a single board gives them the same bit is

In words: $\theta$ (theta) is the angle between the two vectors $\mathbf{x}$ and $\mathbf{y}$. At zero degrees — identical directions — the probability of agreement is 1; at a right angle it is 1/2; pointing opposite ways it is 0. Closeness in angle translates directly into probability of landing on the same shelf, and that is the heart of LSH.

Put in words: measure the angle between the two vectors, express it as a fraction of a half turn, and subtract that fraction from one — what remains is how often a randomly thrown board files them together. Two documents about the same subject sit at a narrow angle, so board after board keeps putting them on the same shelf; two unrelated documents sit near a right angle and only share a shelf about half the time. Nothing here computes similarity — the boards are simply asked their opinion, and agreement is the measurement.

At query time you hash the query with the same boards and compute exact distances only for the handful of candidates on the matching shelf — one shelf's worth of work instead of the entire collection. The catch is that more bits means finer shelves, which raises the chance that the true neighbor just misses and lands on the shelf next door. So real systems keep several hash tables built from different sets of boards and treat anything that shares a shelf in any table as a candidate, which cuts the misses.

LSH in code (numpy pseudocode)

The core is three lines.

import numpy as np

def lsh_codes(X, planes):
    return X @ planes > 0            # (N, k) True/False = a k-bit shelf number

rng = np.random.default_rng(0)
planes = rng.normal(size=(768, 16))  # 16 random boards in a 768-dimensional space
codes = lsh_codes(vectors, planes)   # summarize every vector into 16 bits
query_code = lsh_codes(query[None], planes)
# keep only the rows whose codes match query_code as candidates, then compute exact distances

X @ planes is the dot product of each vector with each board's normal, and the sign tells you which side of the board it is on. There is no training whatsoever — the boards are just random numbers. That refusal to learn anything is what makes LSH elegant.

HNSW: walking a graph toward the target

LSH is light to implement, but reducing misses means adding tables, which makes memory and accuracy hard to satisfy at once. Today's vector databases mostly use a graph-walking approach instead: HNSW (Hierarchical Navigable Small World).

The analogy is a trip by plane, then train, then on foot. Getting from your home in Tokyo to one particular bakery in Paris on foot from the start is hopeless. You cross continents by plane, reach the city by rail, and walk the last few streets. HNSW does that with a graph.

• Each vector is a node, and nearby nodes are connected by edges (at most $M$ per node)
• On top of that, sparser upper layers are stacked, thinned out so the topmost layer holds very few nodes and its edges span long distances in one hop

The search starts at the top layer. From the current node, move to whichever neighbor is closest to the query, and repeat until no neighbor is an improvement (greedy search); then drop one layer and repeat. By the time you reach the bottom layer you are already right next to the query. This layered, thinned-out structure ports the idea behind skip lists — which speed up search in an ordered list — onto a neighbor graph, and was proposed in the paper by Malkov and Yashunin (see the primary source).

Insertion uses the same search to find nearby nodes and then just adds edges, so data can be added later. Unlike LSH it costs something to build, but in exchange it hits a high accuracy rate while examining far fewer candidates.

How this shows up on the job

The people who touch this are the ML engineers and backend engineers who own RAG, search and recommendation. The day after you pick an embedding model, the question of which index to store it in always arrives.

• The tools: as libraries, FAISS (IndexFlatL2 for exact exhaustive search, IndexHNSWFlat for HNSW) and hnswlib; as databases, pgvector, Qdrant, Milvus and others. All of them are running the HNSW of this article (or an IVF-family method) inside, down to nearly identical parameter names
• The knobs you turn: three of them for HNSW. M (edges per node — the foundation for both memory and accuracy), efConstruction (how carefully neighbors are searched during construction; longer build time buys a better graph) and efSearch (search breadth at query time — this is the main dial you adjust day to day to trade latency against recall). In pgvector the same three appear as m / ef_construction / hnsw.ef_search
• How to evaluate it properly: on a modest sample, run exact exhaustive search to produce the true top 10, measure how many of those the ANN index returns (recall@10), and only then set the knobs. Shipping on speed numbers alone without measuring recall is the most common accident by far, and because the search degrades quietly, nothing pages you about it
• The traps: (1) building an inner-product index while thinking in terms of cosine similarity and forgetting to normalize the vectors (long vectors then rank at the top no matter what); (2) heavy deletion and update traffic damages the graph and accuracy drifts down, so schedule periodic rebuilds as part of operations; (3) swapping the embedding model means rebuilding the index from scratch — dimensionality and distance space both change, so plan at design time for a migration period running old and new side by side

Summary

• A hash table computes where things go, which makes exact-match lookup $O(1)$ on average. Collisions are inevitable, and managing the load factor is what keeps performance
• But the better the hash, the further apart it throws similar things. Searching by meaning needs the opposite property
• LSH is a hash where similarity raises the chance of sharing a shelf — it translates angle into collision probability
• HNSW greedily walks a multi-layer neighbor graph, and is what most vector databases run today
• The application built on top of all this is RAG fundamentals. What decides how fast retrieval is and how often it is right are the knobs from this article