Hashing & Hash Tables

Hash tables find the bucket by hash first and only then compare keys for equality. If equal keys hash differently, a lookup probes the wrong bucket, so a stored entry is never found and a set can silently hold duplicates.

Nothing moves. The entry stays in the bucket chosen from the key's old hash value, while later lookups hash the new field values and probe elsewhere. The entry is stranded: unreachable by lookup, still occupying the table.

A hash function must return the same value for the same key contents every time, because a table locates an entry only by recomputing its bucket. Mix in a counter, a clock reading, or an object's memory address and stored entries become unreachable.

The avalanche property: changing one bit of the key should flip about half the output bits, so structured keys land in unrelated places. Without it, a family of similar keys maps into a narrow band of hash values and fills only a handful of buckets.

The hash must be computed from the same normalized form the equality check compares — for example total cents — so every representation that compares equal hashes identically. Hashing the raw amount-and-unit fields lets equal keys hash apart, and lookups silently miss.

Linear probing puts a colliding key in the next free slot, so lookup replays that walk: start at the home slot and step forward comparing keys, stopping only at an empty slot, never at the first non-matching key.

Both keys stay: the bucket holds a list, and the new entry is linked into that list. A lookup indexes the bucket in constant time, then walks the chain comparing full keys, so its cost grows with the chain's length.

Emptying the slot cuts a probe path. A lookup walks forward from the home slot and stops at the first empty slot, so a key that collided and landed past the hole is now reported missing even though it is still stored.

Load factor is entries divided by buckets — under uniform hashing, exactly the expected chain length. A lookup pays a constant-time bucket index plus a walk of that many nodes, so cost is 1 + load factor, constant only because resizing bounds it.

A lookup must walk straight past a tombstone and stop only at a truly empty slot. An insert may reuse the first tombstone it sees, but only after probing on to confirm the key is not already stored further along.

Load factor is entries divided by buckets: 12,000 over 16,384 is about 0.73. It measures average occupancy, not collision-freedom. With a good hash, roughly half those buckets sit empty and thousands of keys already share a bucket with someone.

A key's bucket index is derived from its hash reduced by the table size, so changing the size changes where most keys belong. Copying buckets across unchanged would leave entries in slots that lookups no longer probe.

Because operation cost rises with occupancy long before a table fills. Growing at 0.6-0.75 spends spare bucket slots — cheap next to a stored entry — to keep chains and probe sequences short on every lookup.

Because doubling makes resizes exponentially rarer, so the total re-bucketing work across n inserts stays under about 2n and averages to a constant per insert over the whole sequence. It never promises that any individual insert is cheap.

Divide the expected entry count by the target load factor and round up: five million records at a 0.75 growth threshold needs about 6.7 million buckets. Sizing to five million buckets exactly still triggers a resize.

Reach for a hash set when membership is the only fact you need, and a hash map when every key must carry data with it. A crawler tracking already-fetched addresses wants a set; a document indexer counting how often each word appears needs a map from word to count.

Because for each record you can compute the partner you need and ask the map whether it has already been seen, in expected constant time. That replaces the inner loop of a nested scan, turning O(n^2) comparisons into one O(n) pass that trades O(n) memory for the speedup.

Masking with a power-of-two capacity turns the index step into a single bitwise AND instead of a division, and doubling splits each bucket cleanly. Prime sizing exists to blend weak hash bits; masked tables buy that with an explicit mixing step.

A hash set is normally the same hash table with the value half unused: each entry holds the key and its cached hash, and a membership test is an ordinary lookup reporting found or not found.

Sorting answers a different question: it destroys arrival order, so "first repeat" stops being defined, and it costs O(n log n). A one-pass seen-set tests membership before each insert, reports the earliest repeated badge in O(n) expected time, and stops the moment it finds one.

Hash-table lookup is constant time only on average, assuming keys spread evenly across buckets. When many keys land in the same bucket the lookup walks that bucket instead, so the worst case is O(n) in the number of stored entries.

Iteration walks the internal bucket array from the first slot to the last, so the order falls out of each key's hash value and the table's current capacity. Nothing in that arrangement records when a key arrived, and no implementation commits to keeping it.

Every insert first scans its bucket to check whether the key is already present. When all n keys share one bucket, the k-th insert walks k-1 nodes, so the total is 1+2+...+(n-1), which is Theta(n squared).

Amortized O(1) promises any sequence of n inserts costs O(n) in total, so the per-insert average is constant. It does not promise a single insert is cheap: the one crossing the growth threshold re-places every entry in linear time.

Expected O(1) assumes keys were not chosen against the hash function. A client who can determine that function submits many keys that land in one bucket, so every insert and lookup there becomes a linear scan.

A bloom filter's 'no' is certain: that item was never added. Its 'yes' means only 'probably present' — a fraction of queries for items that were never added still come back positive. Negatives are facts, positives are hints.

The hash map gives O(1) lookup from key to node but knows nothing about recency. The doubly linked list orders nodes by last use, so the eviction victim sits at a known end and unlinking it costs O(1).

An ordered map keeps its keys in sorted order, so it supports in-order iteration, range scans between two keys, and nearest-key lookups. You pay O(log n) on every insert, lookup and delete instead of a hash map's expected O(1).

False positives come from the union of everything already inserted. A never-added element tests positive when all of the positions it checks happen to be set — each possibly by a different element. No two keys need to share a hash value.

Bits are shared. Clearing the positions of one element can zero a bit another still-present element depends on, so that element starts testing negative. Deleting this way destroys the no-false-negative guarantee, which is the filter's only hard promise.