Data structures and complexity

A hash map turns a key into a bucket index and looks there, which is why it is constant time on average regardless of size. Collisions are handled either by chaining, where a bucket holds a small list, or by open addressing, where a colliding entry moves to the next free slot. Chaining is simpler and tolerates a fuller table; open addressing is faster in practice because it stays within a cache line more often.

The average case assumes keys spread evenly, and that assumption is an attack surface. Choose keys that all hash to one bucket and every lookup becomes a scan of a list, turning constant time into linear time on every operation. That was a real, widely exploited denial-of-service class, and the fix now standard in every major language is a hash seed randomised per process, so an attacker cannot compute the collisions in advance.

Load factor is the parameter that decides performance, and it is the ratio of entries to buckets. Past roughly 70 to 75 per cent, collisions rise sharply, so the map grows by allocating a larger table and rehashing every entry into it. That resize is a linear pause, which is fine for throughput and shows up in tail latency, and it is why pre-sizing a map you know the size of is a genuine optimisation.

Ordering is the property people accidentally depend on. A hash map has none by definition, and any apparent order is an implementation detail that will change. Python's dictionaries preserve insertion order as a guarantee since 3.7; most other languages do not, and code that iterates a map and expects stability across runs or versions is code waiting to break.

Keys must be hashable and stable, which in practice means immutable. Mutating an object after using it as a key changes its hash and strands the entry: it is still in the table, in the bucket it originally hashed to, and no lookup will ever find it again. Languages that allow mutable keys make this easy to do by accident, and the resulting bug looks like data loss.

A balanced binary tree is a fine in-memory structure and a poor on-disk one, because every level is a separate read and a read from storage costs orders of magnitude more than a memory access. Be honest about which storage: a seek on a spinning disk is around ten milliseconds against roughly a hundred nanoseconds for main memory, a ratio near a hundred thousand, while an NVMe read is tens of microseconds and the ratio is closer to a thousand. Either way a tree of depth thirty is thirty of them, and the shape of the structure, not the algorithm, is what makes it slow. The B-tree's argument survives the faster medium because a thousandfold is still a thousandfold.

A B-tree fixes it by storing many keys per node, sized to match a disk page, usually a few kilobytes. Fanout of several hundred means depth stays tiny: a table of a hundred million rows is typically three or four levels deep, so a lookup is three or four reads, and the top levels are cached in memory anyway. That is why index depth barely grows as tables get large, which is the property that makes relational databases scale gracefully on reads.

Almost every relational index is a B-tree, and the variant in use is nearly always a B+ tree, where only the leaves hold values and the leaves are linked to each other. That linking is what makes range scans cheap: find the start, then walk sideways, without returning to the root for each subsequent key. Ordered results and BETWEEN queries both come from that one detail.

LSM trees are the other family and they make the opposite trade. Writes go to an in-memory table and are flushed as sorted files, so writes are sequential and fast, and reads may have to consult several files, which is why they lean on Bloom filters to skip the ones that cannot contain a key. Compaction merges those files in the background, spending disk bandwidth later to keep reads from degrading. Cassandra, RocksDB and most modern key-value stores are built this way.

The choice between them is a workload question rather than a fashion. B-trees favour reads and in-place updates; LSM trees favour heavy sustained writes and pay for it in read amplification and background compaction that has to be operated. Knowing which one is underneath your database explains a surprising number of its performance characteristics.

The general lesson is the one worth keeping: the structure is chosen to match the cost model of the medium it lives on. Memory rewards pointer-light layouts and cache locality, disk rewards few large sequential reads, and the network rewards fewer round trips. The same data deserves a different structure in each.

A Bloom filter answers exactly one question cheaply: is this item definitely absent, or possibly present. It is a bit array plus a handful of hash functions. Adding an item sets the bits those hashes point at; checking one reads them. If any bit is zero the item was never added, which is certain. If all are set, it probably was, and it might be a coincidence of other items' bits.

That asymmetry is the whole point. Put one in front of an expensive lookup and everything definitely absent skips the lookup entirely, for a few bits per item rather than the cost of storing the keys. Around ten bits per item gives roughly a one per cent false positive rate, which means a filter for a hundred million keys fits in about 120 megabytes while the keys themselves would be many gigabytes.

The parameters trade against each other in a known way: more bits per item lowers the false positive rate, and the number of hash functions has an optimum for a given ratio. What you cannot do is delete. Clearing bits would break other items that share them, which is why a standard Bloom filter is add-only and why counting variants exist for the cases that need removal.

It appears constantly once you recognise it. Storage engines keep one per data file so a read can skip files that cannot contain the key. Caches use one to answer the penetration problem, where requests for keys that exist nowhere would otherwise reach the database every time. Browsers and mail systems have used them for candidate checks against large blocklists.

The relatives are worth knowing by name. A cuckoo filter supports deletion and is often smaller at low error rates. HyperLogLog answers a different question, how many distinct items are there, in kilobytes rather than gigabytes with a couple of per cent error, which is why every analytics product uses it to count unique visitors. Both belong to the same family: give up exactness, buy an enormous reduction in space.