When does a trie use more memory than a hash set holding the same keys?

**Count nodes, not symbols** The claim "tries save space because prefixes are shared" is half of an accounting exercise, and it is the half that flatters tries. The right model has two terms. *Trie:* the node count of an uncompressed trie equals the number of **distinct prefixes** over the key set. Its upper bound is the sum of all key lengths (no sharing at all), its lower bound is roughly the length of the longest key (total sharing). Each node then costs whatever its children container costs, plus a terminal flag, plus allocator and pointer overhead — commonly tens of bytes to carry a single symbol's worth of information. *Hash set:* one entry per key, holding the key bytes (or a reference to them) and a hash or tag, in a table deliberately kept below full occupancy so probes stay short. Memory grows with the number of keys and the total key bytes, and there is no per-symbol structure at all. **Where sharing pays, and where it does not** Sharing is a property of the key *distribution*, not of tries. Take ten thousand randomly generated 64-symbol content identifiers drawn from a 16-symbol alphabet. There are 65,536 distinct four-symbol prefixes, far more than ten thousand keys, so after about four levels almost every key is already alone on its own path. Total nodes land near 10,000 x 60 = 600,000. The hash set holds 10,000 entries. Even if a trie node were as cheap as a hash entry — it is not, because it also stores child links — the trie loses by roughly sixty to one. Now take keys that are hierarchical: request paths, package-style identifiers, catalogue codes with a shared vendor prefix, natural-language word lists where thousands of entries share a stem. Here the distinct-prefix count is a small multiple of the key count, and the trie's per-node overhead is spread across many keys. This is the regime the folklore describes, and it is real — it is just not universal. | Key set | Distinct prefixes vs keys | Which is smaller | |---|---|---| | Random long identifiers | ~60x more nodes than keys | hash set, by a lot | | Hierarchical path-like keys | ~2-5x more nodes than keys | close; depends on node cost | | Short keys over a tiny alphabet | ~1-2x | trie can win outright | **The compression fix** Most of the waste in the bad case is long chains of single-child nodes — the unique tail of each key, one node per symbol, each carrying a container built to hold many children and holding one. A **radix (compressed) trie** collapses every maximal non-branching chain into a single edge labelled with the whole substring. Node count drops from O(total symbols) to O(number of keys): with k keys there are at most k leaves and at most k-1 branching internal nodes. In the identifier example that is roughly twenty thousand nodes instead of six hundred thousand. What compression does *not* change: lookup still reads all L symbols of the query, because the edge labels must be compared symbol by symbol. Compression removes nodes, not work. It also complicates insertion, which now has to *split* an edge when a new key diverges in the middle of a label. **Two more terms people forget** *Per-node fanout storage.* If each node reserves one slot per possible symbol, node cost scales with the alphabet, and almost all slots are empty — most nodes in a real trie have one or two children. Choosing a smaller children representation moves the total as much as compression does. *Locality.* A trie lookup chases L dependent pointers, each likely a cache miss, in an order the hardware cannot predict. A hash set does one hash and typically one or two probes into a contiguous table. Even at equal memory, the flat structure is usually faster for pure membership. **So why build one at all** Because the memory buys a capability, not speed. A hash set can answer only "is this exact key stored". A trie enumerates every key under a prefix, counts them, finds the longest stored prefix of a query, and yields keys in sorted order — none of which a hash structure can do without scanning everything. Judge the memory against the queries you need, not against membership alone. If membership is all you need, the trie is a worse hash set. **The one-line takeaway** A trie's size is driven by distinct prefixes and per-node overhead; sharing only pays when the keys genuinely overlap, and compression is what rescues the case where they do not.