Hash Collisions and Adversarial Inputs
Hash tables use a hash-derived position to narrow the search for a key, then resolve competing entries according to the implementation. A collision must not make distinct keys interchangeable. Correct equality checks preserve meaning; collision strategy and workload shape determine the amount of work required.
Separate ordinary collisions from deliberately expensive inputs. Resizing can improve average occupancy without fixing a poor or predictable distribution. For untrusted input, use the runtime’s supported defenses plus request and parser limits appropriate to the application.
TL;DR
- Distinguish equal full hash values from different hashes landing in the same bucket.
- Compare keys for equality rather than treating a bucket or hash as identity.
- Define load factor as entries divided by buckets or slots under the stated model.
- Treat resizing and adversarial-input protection as different mechanisms.
- Bound parsing, key count, key size and total work at the relevant input boundary.
Quick Example
This complete Python teaching map uses separate chaining and a deliberately weak integer-to-bucket rule. Four entries trigger growth from four buckets to eight. The three selected keys still share a bucket after growth. The fixture is tiny and performs no network traffic or resource-exhaustion test.
Expected output reports successful equality, update, resize and missing-key checks. The absent key 24 shares the same bucket as real keys but must still raise KeyError. This is not Python’s dictionary implementation and is not a secure map for untrusted application input.
Core Concepts
Two meanings of collision
Different keys can have the same full hash value. Different full hash values can also become the same bucket index after reduction into a finite table. The example demonstrates the latter with integer keys and modulo reduction. An observed shared bucket does not prove the full hash values are equal.
Chaining and open addressing
Separate chaining stores competing entries in a bucket-associated structure. Open addressing searches other table positions using a probing rule. Deletion, tombstones, clustering and capacity policy differ across designs. Do not copy one design’s occupancy assumptions into another without checking its contract.
Load factor is not a distribution test
In the example, load factor is entry count divided by bucket count. A low average can coexist with one long chain. Java’s HashMap documentation illustrates an implementation-specific relationship between capacity, load factor and rehashing, while conditioning ordinary performance on useful dispersion. Its default is not a universal target for every table. Java HashMap
Diagnose which work is increasing
Measure the operation that actually became expensive. Key hashing, key equality, collision search, resizing, allocation and parsing can all contribute. A request that takes longer after accepting more keys does not establish which of these is responsible.
Use a small deterministic fixture first. Assert that updates do not create extra entries, absent colliding keys stay absent and growth preserves every mapping. For an open-addressed implementation, include its supported deletion and probe-termination behavior too.
Avoid calling a larger table a defense simply because the first demonstration becomes faster. The keys may have dispersed accidentally under the new capacity. The example supplies a countercase that remains concentrated after doubling, showing why occupancy and distribution require separate evidence.
Defend the input boundary in layers
CPython’s documented default salts string and bytes hashes with a process-dependent unpredictable value. That protection is specific to those built-in behaviors; a user-defined object with a constant hash or expensive equality is a different case. The Python data model also requires equal objects to have equal hashes and cautions against mutable hash values for keys. Python 3.12 hash contract
PEP 456 explains the security rationale for improving CPython string/bytes hashing. Treat it as a historical design source, not proof that every current build, key type or other language uses one fixed algorithm. Keep supported runtime protections enabled rather than replacing them with a convenient homemade hash. PEP 456
Limit request bytes, decoded key count, key length, nesting and other expensive parsing dimensions as appropriate. Boundaries may need to apply before the map is fully constructed; rejecting an oversized object afterward can be too late to avoid the parsing cost. Use controlled negative cases to confirm where rejection happens.
Consider rate and concurrency limits and useful diagnostics for repeated expensive requests. These complement data-structure protections rather than making an unlimited parser safe. Avoid logging full sensitive keys or payloads just to count rejected requests.
Keep testing local and bounded. Demonstrate correctness with a few synthetic keys, then use an authorized isolated environment for any realistic stress evaluation. Record runtime, key type, input size and measurement scope. A toy chain length is neither a production attack nor a benchmark of a real service.
Best Practices
Preserve the equality contract
Test distinct keys that share a bucket and repeated writes to the same key. A hash value is an index aid, not a unique identity guarantee.
Bound work before constructing large objects
Apply parser and request limits at the stage where they actually prevent cost. Verify negative cases rather than relying on a documented limit alone.
Keep runtime claims specific
Identify language, release, key type and implementation. Distinguish supported hash protections from growth policy and application resource limits.
Common Mistakes
Bad: Treating a bucket collision as proof of equal hashes.
Correct: Check the full hash and bucket-reduction steps separately.
Bad: Expecting doubling to disperse every concentrated input.
Correct: Inspect distribution and retain a countercase that survives the capacity change.
Bad: Assuming string hash randomization protects arbitrary custom keys.
Correct: Review the actual key hash/equality behavior and apply input/work limits.
FAQ
Are collisions necessarily bugs?
No. Finite indexing requires collision handling. The bug is losing correctness or failing to meet the intended work/resource constraints.
Can chaining have a load factor above one?
Yes, because several entries can occupy one bucket’s chain. This does not mean that the same occupancy is safe for an open-addressed design.
Does the example reproduce CPython dict?
No. It is a deliberately simple teaching map. Its modulo rule and resize behavior are not claims about CPython internals.
Related Topics
- Hash Tables — Study the base data structure and its operating contract.
- Data Structures — Compare structures by operations and constraints.
- CPU, Memory, and Allocation Profiling — Measure hashing, equality and allocation costs separately.