Hash tables in practice: collisions, load factor and seeded hashing

What it is

A hash table maps a key to a bucket index by computing hash(key) mod capacity. Two keys that land in the same bucket collide; the table resolves this by chaining (a small list per bucket) or by open addressing (probing other slots). The load factor is entries divided by capacity. The Java HashMap documentation describes the load factor as the measure of how full the table may get before its capacity is increased, with a default of 0.75; when entries exceed load factor times capacity, the table is rehashed, which touches every entry. Python's data model states that hash values of str and bytes are salted with an unpredictable per-process value (hash randomization, on by default since 3.3), and the Go specification says the iteration order over maps is not specified.

Why it matters

Average O(1) lookups depend on keys spreading evenly. An attacker who can choose keys (query parameter names, JSON field names, form fields) and knows the hash function can make thousands of keys collide, turning each insert into a linear scan and one request into quadratic work; this is hash flooding, and per-process seeding is the standard defence. Rehashing is O(n) and happens at thresholds, so a loop that inserts n items pays for several rehash rounds: amortised cost stays O(1), but individual inserts spike.

How to apply

• Never persist, transmit or compare across processes any language-level hash value; it changes with seed, version and build. Sort output that must be stable instead of relying on map order.
• Presize when the count is known (HashMap(initialCapacity), make(map[K]V, n)) to avoid rehash rounds in hot loops.
• Keys must not change while they are in the table; mutating a key after insertion makes the entry unfindable. Equal objects must hash equal: define equality and hash together.
• When implementing a table (embedded code, custom allocator): use a hash with good avalanche, seed it per process, cap the load factor, and test the longest probe chain with adversarial keys.
• For reproducible tests, fix the seed explicitly (PYTHONHASHSEED) rather than relying on accident, and run the suite with a random seed as well.

Pitfalls

A test that passes under one seed and fails under another reveals order dependence in the code, not a flaky test. Floating-point keys: 0.0 and -0.0 compare equal and must hash equal; NaN is not equal to itself. A table used as a cache without a size bound is a memory leak. Cryptographic digests such as SHA-256 are unnecessary for tables and slow; fast keyed hash functions designed for tables are the norm.