Why can't a single hash lookup answer a longest-prefix-match routing query?

seniorshould knowfreq 40%

answer

the query key was never stored
hashing scatters a key and its prefixes
how many candidate lengths exist
descend and remember the deepest hit
cost tracks address width, not table size

basics

~20 s

A hash structure answers exact-key membership only, and a destination address is almost never itself a stored entry. Longest-prefix match asks which stored prefix of any length matches deepest — that needs an ordered descent, not one lookup.

solid answer

~50 s

A route table stores prefixes of many different lengths, and the query is a full address that usually matches none of them exactly; you want the longest stored prefix that matches. Hashing destroys the prefix relationship — a stored entry and the address that matches it hash to unrelated slots — so one lookup can only ask about one exact string. You can still do it with hashing by probing every candidate prefix length, or by binary-searching on length with marker entries, but both cost several lookups and extra bookkeeping on every update. A trie makes the query shape native: descend the address one bit or symbol at a time, remember the deepest node marked as a stored prefix, and return that record when you fall off or run out. Cost is bounded by the address width, not by the number of routes.

A route table stores prefixes of many different lengths, and the query is a full address that usually matches none of them exactly; you want the *longest* stored prefix that matches. Hashing destroys the prefix relationship — a stored entry and the address that matches it hash to unrelated slots — so one lookup can only ask about one exact string. You can still do it with hashing by probing every candidate prefix length, or by binary-searching on length with marker entries, but both cost several lookups and extra bookkeeping on every update. A trie makes the query shape native: descend the address one bit or symbol at a time, remember the deepest node marked as a stored prefix, and return that record when you fall off or run out. Cost is bounded by the address width, not by the number of routes.

code

pseudocode · 13 lines

pseudocode

// bit-trie: find the longest stored prefix of `address`
node = root
best = null
for i in 0..W-1
    if node.is_prefix_end
        best = node.route        // deeper match beats any earlier one
    b = bit(address, i)
    node = node.children[b]
    if node == null
        return best              // fell off: deepest so far wins
if node.is_prefix_end
    best = node.route            // a full-width prefix also counts
return best

go deeper

for a junior

Know the difference between "is this exact key stored" and "which stored prefix matches this input deepest". A hash structure answers only the first, and that gap is a large part of why tries exist.

for a middle

Explain the descent precisely: consume the query one bit or symbol at a time, update a remembered best whenever you pass a node marked as a stored prefix, and return that remembered value when you fall off or finish.

for a senior

Compare the real alternatives under constraint — length probing or binary search on length with a hash structure, a path-compressed trie, a multibit-stride trie — and say what each one does to lookup depth, memory and the update path.

for a principal

Own the tradeoff between a structure you can update in place under live traffic and one you rebuild offline for lookup speed. For a table under constant churn the update path, not the lookup, usually decides the design.

The query is not the one a hash structure answers

A forwarding table stores entries like "this block of addresses, 24 bits significant" alongside "this larger block, 16 bits significant". A lookup arrives with a full-width address and must find the entry whose prefix matches it and is longer than any other matching entry's — the more specific route wins over the more general one. That is a longest-prefix match (LPM).

A hash structure supports exactly one question: was this precise key inserted? The full address was almost certainly never inserted; only prefixes were. And hashing is designed to scatter — the whole point of a good hash is that a string and its prefix land in unrelated slots — so there is no way to "look near" the address and find its ancestors. One lookup of the address itself returns nothing useful, and returning the first matching prefix you find would be wrong even if you could find one, because a longer match may exist.

You can do it with hashing, at a price

The honest senior answer is not "impossible" but "not in one lookup":

Probe every length. For an address of width W, truncate to each stored prefix length and do one lookup per candidate, keeping the longest hit. That is up to W lookups per packet, though you can restrict to the lengths actually present in the table.
Binary-search on length. Insert extra marker entries so a hit at length m tells you whether any longer match can exist, then binary-search the length axis in about log W lookups. It is a real, deployed technique, and the price is that every route insertion or withdrawal must maintain markers and precomputed best-match values — the update path gets substantially more complex.

Both trade a simple structure for a complicated one because they are fighting the query's shape.

The trie makes the shape native

Store each prefix as a path: one edge per bit (or per stride of bits), a marker where a prefix ends. Then LPM is a single descent that remembers the deepest marker it passed. When the descent falls off the end of the tree, or consumes the whole address, the remembered node is the answer, and "no match" is naturally handled by the default route stored at the root.

Three properties matter here:

Cost is bounded by address width, not table size. A descent is at most W steps whether the table holds a thousand routes or a million. That is a stronger guarantee than an expected-time hash bound, which matters when you are budgeting per-packet latency.
Updates are local. Adding or withdrawing a route touches one path. No global markers, no recomputation across other entries.
The structure encodes specificity directly. Depth is prefix length, so "longest match" reduces to "deepest marker", with no comparison of lengths anywhere.

The two refinements you should be able to name

Path compression. Real tables are sparse; long runs of single-child nodes are common. Collapsing them into one edge that skips a known bit run gives a Patricia-style radix trie: node count becomes proportional to the number of stored prefixes, at the cost of verifying the skipped bits when you arrive.

Multibit strides. Consuming k bits per level instead of one cuts depth from W to W/k, at the cost of up to 2^k child slots per node. Choosing strides per level is how forwarding structures trade memory for a lower bounded lookup depth; a fixed 8-8-8-8 split over a 32-bit address gives four memory accesses per lookup.

The shape generalises

Any "longest stored prefix of this input" problem has the same answer: dial-plan and phone-number routing, longest-match route selection in a request router where /a/b/c must beat /a, tokenizers that greedily match the longest entry in a vocabulary, filesystem mount-point resolution. All of them are prefix-descent problems dressed differently, and all of them are answered badly by exact-key hashing.

The direction to keep straight

O(1) expected lookup does not beat O(W) descent here, because they answer different questions. The hash is fast at a question nobody asked. The correct comparison is W trie steps against W (or log W) hash lookups plus the update-time bookkeeping the hashing scheme requires.

The one-line takeaway

Hashing indexes whole keys; longest-prefix match is a question about every prefix of the query at once, and only a structure ordered by prefix answers it in one pass.

**The query is not the one a hash structure answers** A forwarding table stores entries like "this block of addresses, 24 bits significant" alongside "this larger block, 16 bits significant". A lookup arrives with a full-width address and must find the entry whose prefix matches it *and is longer than any other matching entry's* — the more specific route wins over the more general one. That is a **longest-prefix match** (LPM). A hash structure supports exactly one question: was this precise key inserted? The full address was almost certainly never inserted; only prefixes were. And hashing is designed to scatter — the whole point of a good hash is that a string and its prefix land in unrelated slots — so there is no way to "look near" the address and find its ancestors. One lookup of the address itself returns nothing useful, and returning the first matching prefix you find would be wrong even if you could find one, because a longer match may exist. **You can do it with hashing, at a price** The honest senior answer is not "impossible" but "not in one lookup": - **Probe every length.** For an address of width W, truncate to each stored prefix length and do one lookup per candidate, keeping the longest hit. That is up to W lookups per packet, though you can restrict to the lengths actually present in the table. - **Binary-search on length.** Insert extra *marker* entries so a hit at length m tells you whether any longer match can exist, then binary-search the length axis in about log W lookups. It is a real, deployed technique, and the price is that every route insertion or withdrawal must maintain markers and precomputed best-match values — the update path gets substantially more complex. Both trade a simple structure for a complicated one because they are fighting the query's shape. **The trie makes the shape native** Store each prefix as a path: one edge per bit (or per stride of bits), a marker where a prefix ends. Then LPM is a single descent that remembers the deepest marker it passed. When the descent falls off the end of the tree, or consumes the whole address, the remembered node is the answer, and "no match" is naturally handled by the default route stored at the root. Three properties matter here: 1. **Cost is bounded by address width, not table size.** A descent is at most W steps whether the table holds a thousand routes or a million. That is a stronger guarantee than an expected-time hash bound, which matters when you are budgeting per-packet latency. 2. **Updates are local.** Adding or withdrawing a route touches one path. No global markers, no recomputation across other entries. 3. **The structure encodes specificity directly.** Depth *is* prefix length, so "longest match" reduces to "deepest marker", with no comparison of lengths anywhere. **The two refinements you should be able to name** *Path compression.* Real tables are sparse; long runs of single-child nodes are common. Collapsing them into one edge that skips a known bit run gives a Patricia-style radix trie: node count becomes proportional to the number of stored prefixes, at the cost of verifying the skipped bits when you arrive. *Multibit strides.* Consuming k bits per level instead of one cuts depth from W to W/k, at the cost of up to 2^k child slots per node. Choosing strides per level is how forwarding structures trade memory for a lower bounded lookup depth; a fixed 8-8-8-8 split over a 32-bit address gives four memory accesses per lookup. **The shape generalises** Any "longest stored prefix of this input" problem has the same answer: dial-plan and phone-number routing, longest-match route selection in a request router where `/a/b/c` must beat `/a`, tokenizers that greedily match the longest entry in a vocabulary, filesystem mount-point resolution. All of them are prefix-descent problems dressed differently, and all of them are answered badly by exact-key hashing. **The direction to keep straight** O(1) expected lookup does not beat O(W) descent here, because they answer different questions. The hash is fast at a question nobody asked. The correct comparison is W trie steps against W (or log W) hash lookups plus the update-time bookkeeping the hashing scheme requires. **The one-line takeaway** Hashing indexes whole keys; longest-prefix match is a question about every prefix of the query at once, and only a structure ordered by prefix answers it in one pass.

Can longest-prefix match be done with hashing at all?
Yes, at a cost. Probe one lookup per candidate prefix length and keep the longest hit, or insert marker entries so you can binary-search the length axis in about log W lookups. Both work and both are deployed, but they pay for it on the update path: every route change has to maintain markers and precomputed best matches, where a trie update touches one path.
What does path compression buy in a routing trie?
Real prefix tables are sparse, so most nodes have a single child and exist only to spell out bits nobody branches on. Collapsing those runs into one edge that skips a known bit sequence makes node count proportional to the number of stored prefixes instead of to total bits, in exchange for verifying the skipped bits on arrival.
Why do high-throughput forwarding structures use multibit strides?
Consuming k bits per level cuts depth from W to W/k, so a 32-bit address resolved in 8-bit strides costs four memory accesses instead of thirty-two. The price is up to 2^k child slots per node, so stride widths are chosen per level to fit a memory budget — a direct memory-for-latency trade.

saying these in an interview costs you the question

Says just hash the address and look it up
Assumes the query address is itself a stored entry
Claims expected O(1) hashing beats an O(W) descent here
Forgets to carry the deepest match through the descent
Stops the descent at the first marked node found
Thinks lookup cost grows with the number of stored routes

Why can't a single hash lookup answer a longest-prefix-match routing query?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

▾common follow-ups3 questions

▾red flags6 flags

§ context

▾related questions4 questions

▾related topics4 topics

answer

go deeper

context