hashdos

confirmedshipRust · CPUSystems & data structuresJuly 17, 2026

the question

Does a hash table with a predictable hash become O(n^2) under adversarially chosen colliding keys, and does a keyed hash restore linear time?

what came out

Confirmed. With a weak low-bits hash, adversarial keys all land in one bucket and insert time quadruples per doubling of N (the O(n^2) signature), reaching 38ms with a chain of 32,000 at N=32k, 108x slower than the same keys under a keyed hash, which stays linear with a chain of 6.

method & receipts

Result: confirmed
Pre-registered — the prediction was written down and committed before the run.
Reproducible — one script re-runs the whole thing from scratch.
Tested — a correctness/benchmark suite ships alongside the code.

→ read the code and re-run it

github.com/v-code01/hashdos