Hash tables

Hash Tables

Overview

Hash tables are not magic constant-time dictionaries. The core move is to separate the address calculation, collision policy, load-factor budget, and adversarial model, then choose the weakest mechanism that keeps expected probes, memory movement, deletion behavior, and cache locality within the real service constraints.

Shared CLRS Conventions

Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style.

When to Use

• A prompt involves dictionaries, symbol tables, direct addressing, hash tables, hash functions, collision resolution, chaining, open addressing, double hashing, linear probing, tombstones, load factor, or universal hashing.
• You need to translate expected-time hashing assumptions into production capacity planning, p99 latency, adversarial-input defense, or memory-hierarchy behavior.
• A proposed design relies on expected constant time and you must state the hashing assumptions that make the claim meaningful.
• Keys are integers, byte strings, vectors, identifiers, request parameters, or user-controlled data whose distribution may matter.

Do not use this skill merely because a platform dictionary exists. Use the language or database default unless algorithm choice, attack resistance, resizing behavior, deletion semantics, or cache locality is the actual question.

First Decision: What Problem Are You Really Solving?

Need	Prefer	Why
Dense small universe with no huge gaps	Direct addressing or bit vector	Worst-case constant lookup is paid for by allocating the whole universe
Sparse universe with dynamic inserts and deletes	Hash table	Compresses the address space to live keys while keeping expected constant operations
Frequent deletes and simple stable performance	Chaining, or open addressing with explicit cleanup policy	Deletion is straightforward for chaining; tombstones in open addressing accumulate
Cache-sensitive high-throughput table	Open addressing, often linear-probing-family designs at conservative load	Avoids pointers and probes contiguous cache blocks
Unknown or adversarial keys	Randomized or keyed hash family	Fixed static functions can be collision-targeted
Static set with only search	Consider sorted array, perfect hashing, or open addressing with extra capacity	Preprocessing can buy simpler worst-case lookup behavior
Variable-length byte strings	A string hash or keyed/cryptographic-inspired mixer plus a collision strategy	Division and word multiply-shift are integer-key building blocks, not complete string-table designs

Before accepting a hash-table proposal, ask:

1. Are keys dense enough for direct addressing, or is the universe much larger than live keys?
2. Is the workload dominated by hits, misses, inserts, deletes, iteration, or resizing?
3. Is the input trusted, random-looking, structured, or adversarial?
4. Is p99 latency driven by probes, cache misses, pointer chasing, memory bandwidth, or hash computation?
5. Can the table rebuild or rehash, and what is the maximum live plus tombstone occupancy before it must do so?

Direct Addressing Mindset

Direct addressing teaches the ideal dictionary: one key, one slot, worst-case constant operations. It is production-aligned only when the key universe is genuinely small or compact after remapping.

Use direct addressing when the allocation cost is proportional to the real domain you must cover anyway, such as small enum IDs, file descriptors within a fixed bound, bitsets for membership, or dense remapped IDs.

Do not allocate a huge direct-address table just because lookup would be constant. If initialization is the blocker, use the sparse-table trick: keep a compact stack/list of initialized keys and validate a slot by checking that its back-pointer/index agrees with the compact list. The deeper lesson is lazy validity, not huge zero-filled memory.

Load Factor and Expected Cost Reference

The load factor is the average occupancy per table slot:

$$ \alpha = \frac{n}{m} $$

For chaining, the value above may exceed one. For open addressing, at most one element occupies a slot, so it must stay below one for the standard bounds.

Scheme	Assumptions	Cost label	Planning consequence
Chaining, unsuccessful search	Independent uniform hashing, constant hash computation	Expected chain scan	Misses scan one expected chain; high load grows roughly linearly
Chaining, successful search	Same, searched element uniformly among stored elements	Expected stored-element scan	Longer chains are sampled more often; still constant when load is bounded
Open addressing, unsuccessful search or insert	Simple uniform hashing for probe sequences, no deletions, load below full	Miss or insert probe bound	Misses and inserts explode as the table fills
Open addressing, successful search	Same, searched key uniformly among stored keys	Hit probe bound	Hits rise more slowly than misses, but still require headroom

Reference bounds:

• Chaining unsuccessful search and successful search are expected constant time when the load factor is bounded. The cost form is:

$$ \Theta(1 + \alpha) $$

• Open addressing unsuccessful search and insertion are bounded by:

$$ \frac{1}{1 - \alpha} $$

• Open addressing successful search is bounded by:

$$ \frac{1}{\alpha}\ln\frac{1}{1 - \alpha} $$

Use the miss or insert bound for capacity planning when misses, upserts, cache lookups, dedupe checks, or negative membership tests matter. Successful-search averages are not enough for p99 planning.

Hash Function Mindset

Independent uniform hashing is the ideal model for chaining, and simple uniform hashing is the ideal model for open-address probe sequences. Real implementations approximate these models. Always say where the randomness comes from.

Hashing approach	Use when	Trap
Division method	Educational integer examples or carefully chosen non-patterned table sizes	A fixed modulus can preserve key patterns; prime sizing may fight practical resizing
Multiplication or multiply-shift	Fast fixed-width integer mixing, especially with power-of-two table sizes	A fixed constant gives no adversarial guarantee by itself
Universal hashing	You need a theorem against any fixed key set	The guarantee is over a randomly chosen function family, not any one static function
Random odd multiply-shift	Fast practical integer hashing with bounded collision probability	The chapter's bound is approximate-universal, not a full random oracle
Cryptographic or keyed hashing	User-controlled keys, hash-flooding risk, or variable-length strings needing robust mixing	It may cost more CPU; on modern hardware this can still be cheaper than random memory misses
String or vector hashing	Variable-length byte strings or identifiers	First reduce the byte sequence with a sound mixer; do not treat a long string as a single machine word

Industrial rule: a fast weak hash can make the table's asymptotics irrelevant under structured or hostile input. A slower robust hash can win when measurements or threat models show that it prevents long probe chains, cache misses, or attack-driven collision storms.

Randomization and Universality

Universal hashing prevents a fixed adversarial key set from forcing the same bad collisions every run. The family matters more than the individual textbook formula.

Property	Meaning for answers
Uniform	A fixed key is equally likely to land in any slot over the random choice of hash function
Universal	Any two distinct keys collide with probability at most the reciprocal of the table size
Approximately universal	Collision probability is within a constant factor of the universal target
Independent	Several keys jointly behave like independent random slot choices

Do not say universal hashing means a static function can be chosen once and forgotten under adversarial workloads. In a long-running service, the practical analogue is a secret per-process or per-table seed, monitored collision behavior, and rehashing if the distribution becomes pathological.

Collision Strategy Decision Table

Strategy	Strength	Weakness	Production translation
Chaining	Simple deletion, load may exceed one, robust under growing buckets	Pointer chasing and allocation hurt cache locality; worst chain can be long	Good baseline for frequent deletes or external storage, but use compact buckets or tree/fallback defenses in hostile settings
Open addressing	Stores elements in the table, avoids pointers, often cache-friendly	Cannot exceed full occupancy; deletion and clustering are delicate	Use low load thresholds, resizing, tombstone cleanup, and measured probe distributions
Double hashing	Many probe sequences and less primary clustering than linear probing	More random memory access and step-size constraints	Good theoretical open-addressing default when cache locality is not the only concern
Linear probing	Excellent locality; deletion can be done by shifting within clusters	Primary clustering; needs stronger hash independence and conservative load	Often fastest in memory hierarchies when paired with a strong keyed hash and rebuild policy

Treat collision strategy and hash function as separate axes. A cache-friendly probing strategy cannot rescue a hash that maps many real keys to the same neighborhood; a strong hash cannot rescue an overfull table with unbounded tombstones.

Static Sets and Perfect Hashing

Perfect hashing is the right answer when the key set is fixed and lookups dominate. The mindset is different from a dynamic dictionary: spend randomized preprocessing to remove collision work from future searches.

Use this idea when all of these are true:

1. the set of keys is known before queries begin,
2. insertions and deletions are absent or handled by rebuilding,
3. lookup latency predictability matters more than update flexibility,
4. the implementation can afford build-time retries and extra metadata.

The two-level construction uses a first-level universal hash to place keys into buckets, then gives each bucket its own second-level table and randomly chosen hash function. The first level controls the sum of squared bucket sizes; the second level retries until that bucket has no collisions. The operational lesson is to isolate collision risk locally instead of overbuilding the entire table for the worst bucket.

In production, do not hand-roll textbook perfect hashing just because a set is static. Compare it with a sorted array, generated minimal-perfect-hash library, trie/FST, database index, or ordinary hash table. Choose perfect hashing when the build pipeline is controlled and the saved lookup variance or memory layout justifies the preprocessing complexity.

Deletion Discipline

Chaining deletion is conceptually simple when the deletion operation receives a pointer or handle to the stored object; doubly linked lists make that constant time. If deletion receives only a key, the search cost still applies.

Open addressing deletion is not simply setting a slot to empty. A search stops at an empty slot, so clearing a slot can make later keys unreachable. The textbook tombstone value preserves probe chains, but tombstones make the table act fuller over time. For frequent deletes, require at least one of these policies:

1. periodic rebuild when tombstone count crosses a threshold,
2. resize or rehash based on live plus deleted occupancy,
3. a probing scheme with valid backward-shift deletion, such as linear probing,
4. a different table design if delete-heavy p99 latency is the priority.

For linear probing, the deletion lesson is an invariant: after removing a slot, shift forward keys backward only when the vacated slot lies earlier in that key's probe sequence than its current location. Preserve reachability, not merely compactness.

Memory-Hierarchy Guidance

The RAM-model probe count is only a proxy. In real systems, a random cache miss can dominate several arithmetic or mixing operations.

• Chaining may have good expected comparison counts but poor locality because nodes and buckets can live in different cache lines.
• Open addressing uses contiguous table storage and often wins despite theoretical clustering concerns.
• Linear probing's primary clustering is bad in the RAM model but can be beneficial for cache-block locality when load is controlled.
• Complex hash functions may be acceptable if they run in registers and prevent expensive random-memory probe chains.

When p99 matters, monitor probe lengths, cluster lengths, rebuild frequency, resize latency, and hash-flooding indicators. Do not plan only from average successful lookup cost.

One Practical Design Pattern

For a high-throughput in-memory dictionary with fixed-width keys, common deletes, and p99 latency constraints:

1. Start from a mature platform hash map unless measurements require a custom table.
2. Use a seeded, high-quality mixer for the key type; for hostile keys use keyed hashing.
3. Choose collision strategy from deletion and locality constraints: chaining for simple stable deletes, or open addressing with explicit tombstone/back-shift/rebuild policy for cache locality.
4. Set separate thresholds for live load and effective occupancy.
5. Measure hit, miss, insert, delete, resize, and rebuild tails separately.
6. Rehash with a new seed if collision distribution becomes suspicious.

This pattern extracts the hashing mindset without hand-rolling the educational pseudocode unless the implementation constraints justify it.

Invariant and Proof Recipes

• Chaining expected search: Define indicator variables for whether another key collides with the searched key. Sum collision probabilities using linearity of expectation; independence can be weakened to universal pairwise collision bounds for many results.
• Universal hashing proof: Fix two distinct keys, show the random parameters make their intermediate values distinct and uniformly distributed, then count how many reductions collide modulo the table size.
• Open addressing unsuccessful search: Bound the chance that the first several probes all hit occupied slots. Sum tail probabilities to get the geometric-style bound.
• Open addressing successful search: A successful search repeats the insertion probe sequence. Average the insertion cost over the load factor at the time each key was inserted.
• Double hashing correctness: Show the step size is relatively prime to the table size so the probe sequence visits every slot before repeating.
• Linear-probing deletion: Maintain the invariant that every live key is reachable from its home slot before encountering an empty slot.

RED Pressure Failures This Skill Prevents

Baseline failure	Required correction
Picking chaining as the only answer for delete-heavy p99 workloads	Discuss chaining's deletion simplicity and open addressing's cache-locality advantage; make the tradeoff explicit
Treating universal hashing as a fixed static function that remains safe against adversaries	State that the expectation is over a random choice from a family and use seeding or rehashing in production
Ignoring tombstone accumulation in open addressing	Plan with effective occupancy and require rebuild, cleanup, or backward-shift deletion
Giving hit-only averages for capacity planning	Use miss and insert probe bounds when negative lookups, inserts, or p99 latency matter
Recommending division or raw multiply-shift for variable-length strings	Distinguish integer-key building blocks from byte-string hashing pipelines
Reciting textbook algorithms without industrial translation	Name cache locality, pointer chasing, load thresholds, adversarial input, and measurement hooks

Common Mistakes

Mistake	Correction
Saying hash tables are constant time without assumptions	State average or expected time and the hashing model
Confusing load factor meanings	Chaining permits average chain length above one; open addressing must stay below full occupancy
Deleting an open-addressed slot by writing empty	This can break reachability; use tombstones, rebuilds, or valid shift deletion
Counting only live entries after many deletes	Track live entries and tombstones or occupied-ever slots
Choosing table size by theorem aesthetics alone	Production resizing, power-of-two masking, cache layout, and hash mixing interact
Treating primary clustering as always bad	It hurts RAM-model probe counts but can improve locality when controlled
Using cryptographic hashing reflexively	Use it when adversarial risk or robust variable-length mixing justifies the CPU cost
Trusting average-case claims for p99 latency	Measure tail probe counts and rebuild before clusters dominate

Verification Pressure Tests

Use these to check future answers:

1. Delete-heavy dictionary: For 64-bit keys, common deletes, and p99 latency, the answer should compare chaining deletion simplicity with open-address cache locality and require load/tombstone policies.
2. Adversarial static hash trap: For a fixed static function and user-controlled keys, the answer should reject unconditional expected constant time and explain randomized universal or keyed hashing.
3. Capacity planning formulas: For a workload with misses and inserts, the answer should use load factor and open-address miss or insert bounds, not only successful-search averages.
4. Variable-length strings: For byte-string keys in a cache-sensitive table, the answer should separate the string hash/mixer from the collision strategy and mention robust seeding or cryptographic-inspired hashing when appropriate.
5. Linear-probing deletion: For deletion without tombstones, the answer should preserve probe-sequence reachability rather than merely shifting every later key backward.