When is a hash table not O(1)? Collisions, O(n²) inserts and hash flooding

Hash table lookups and inserts are O(1), or so the usual summary goes. The official documentation attaches a condition to that.

The cost table in Rust’s standard library lists get and remove on HashMap as O(1)~ and insert as O(1)~*. The ~ marks an expected cost and the * an amortized one. It adds that, because hashing is probabilistic, performance much worse than expected is possible, though very unlikely. The Java SE 21 HashMap documentation promises constant time for get and put “assuming the hash function disperses the elements properly among the buckets.”

This post covers what happens when that assumption fails, and how language runtimes defend against someone breaking it on purpose. The baseline is the Python 3.15 documentation (updated 10 October 2026), the Rust 1.99.0 documentation and the Java SE 21 API documentation.

With equal hashes, comparison is all that’s left

A hash table uses a key’s hash value to pick where it goes. Two keys with different hash values can’t be equal, so the table can skip past them at once. Keys with the same hash value can’t be told apart by the hash, so the table has to compare them directly. Python’s data model documentation only requires one direction: objects that compare equal must have the same hash value. Equal hash values say nothing about the objects being equal.

Take the extreme case: n distinct keys that all share one hash value.

• When the k-th key goes in, the table already holds k−1 keys, all with that same hash value.
• To decide whether the new key is already present, it has to be compared with each of those k−1 keys. Skip even one, and that one might have been equal to the new key.
• Inserting all n keys therefore takes at least 0 + 1 + … + (n−1) = n(n−1)/2 comparisons.

That lower bound is 499,500 for n = 1,000 and 49,995,000 for n = 10,000. Ten times the input raises it about a hundredfold: Θ(n²). Lookups suffer the same way: under the same hash-plus-equality model, searching for a missing key takes at least n equality comparisons before the answer comes back “not found”. The argument assumes the table can only use the hash and an equality test on keys. If it can also order the keys, as Java can below, the argument doesn’t carry over as is.

In Python, a __hash__ that returns a constant is enough to set this up.

class Key:
    eq_calls = 0

    def __init__(self, v):
        self.v = v

    def __hash__(self):
        return 42  # every key has the same hash value

    def __eq__(self, other):
        Key.eq_calls += 1
        return isinstance(other, Key) and self.v == other.v

n = 1000
d = {Key(i): i for i in range(n)}
print(Key.eq_calls, n * (n - 1) // 2)

The argument above gives a lower bound on the number of __eq__ calls. Exactly how many CPython makes depends on its dict implementation, so this post doesn’t state a number; run it and compare the two values yourself. A __hash__ like this in real code keeps results correct but makes dicts and sets as slow as lists. The Python documentation recommends hashing a tuple of the attributes used in comparison, as in hash((self.name, self.nick, self.color)).

When an attacker picks the input

A constant hash is a mistake you make yourself. The harder case is a perfectly good hash function whose input comes from outside. If whoever supplies the keys can produce many distinct keys with the same hash value, the server ends up in the situation above when it loads them into a dict. Under the model above, that takes at least n(n−1)/2 equality comparisons. This attack is called hash flooding; the Rust documentation calls it HashDoS.

When the Python documentation explains hash randomization, it gives the purpose as protection against “a denial-of-service caused by carefully chosen inputs that exploit the worst case performance of a dict insertion, O(n²) complexity,” and links to the 2011 oCERT advisory (oCERT-2011-003).

Python: a secret value mixed into str and bytes hashes

Hash randomization has been on by default since Python 3.3. According to the documentation, the __hash__() values of str and bytes are “salted” with an unpredictable random value. The value stays constant within one process but differs between runs of Python. The idea is that an attacker who doesn’t know the server process’s secret can’t precompute colliding strings.

The PYTHONHASHSEED environment variable changes this behaviour.

• Unset or random: a random seed is used.
• A decimal integer from 0 to 4294967295: that value is used as a fixed seed. The documentation’s examples of why you’d want this are repeatable hashing for the interpreter’s own self-tests and letting a cluster of Python processes share hash values.
• 0: hash randomization is disabled.

A PYTHONHASHSEED=0 added to make test runs reproducible removes this defence if it leaks into production configuration. A fixed seed is in the same position once its value is known.

Randomization has a side effect. When hash values change, the iteration order of sets changes. The Python documentation says it has never guaranteed that order, and that it typically varies between 32-bit and 64-bit builds. If a set prints in a different order on every run, that is this feature at work, not a bug. sys.hash_info.algorithm (since 3.4) names the string hash algorithm in use.

Integer keys aren’t randomized

The documentation names str and bytes as the salted types. Numeric hashes follow their own rule. The hash of a rational number is defined by reduction modulo a fixed prime P, and CPython uses P = 2**61 − 1 on machines with 64-bit C long (sys.hash_info.modulus). Negative numbers get the sign applied, and a result of −1 is replaced with −2.

An integer is a rational with denominator 1, so applying the rule gives m mod P as the hash of a non-negative integer m. That means the following holds on 64-bit CPython.

import sys

P = sys.hash_info.modulus      # 2**61 - 1 on 64-bit CPython
assert hash(P) == hash(2 * P) == hash(3 * P) == 0
assert hash(-1) == -2

Every multiple of P hashes to 0, and that doesn’t change between runs. If outside input flows straight into integer dict keys, hash randomization won’t protect that code. Limiting how many keys one request can create, covered below, is one defence for that case.

Rust: a default hasher chosen with HashDoS in mind

According to the Rust 1.99.0 documentation, HashMap’s default hashing algorithm was selected to resist HashDoS attacks and is randomly seeded. A best effort is made to generate the seed from a secure source of randomness provided by the host, but the documentation warns that seeds created when the system’s entropy pool is abnormally low, such as during boot, may be of lower quality.

The algorithm is currently SipHash 1-3, and the documentation says this may change at any point. It adds that other algorithms outperform it for small keys such as integers and for large keys such as long strings, but those algorithms typically don’t protect against HashDoS. Before swapping in a faster hasher, check whether the keys come from outside input.

Java: key order as a tie-breaker

The Java SE 21 HashMap documentation says that using many keys with the same hashCode() is a sure way to slow down any hash table. To soften the impact, when keys are Comparable, the class may use comparison order among keys to help break ties.

The n(n−1)/2 lower bound earlier assumed only equality tests. The Java documentation goes no further than saying comparison order may be used; it doesn’t describe how. String implements Comparable<String>, so string keys are eligible. Since the documentation says “may”, when this actually applies and any cost bound aren’t part of the API contract.

What to check in your code

• Hash a tuple of every field used in equality in a custom __hash__. A constant, or a hash over only some of the fields, means more collisions.
• Don’t run Python in production with PYTHONHASHSEED=0 or a known fixed value. Don’t write code that relies on set iteration order.
• Python integer hashes aren’t randomized. Put appropriate request or resource limits on integer keys chosen by outside input.
• In Rust, before replacing the default hasher with a faster one, confirm the keys don’t come from untrusted input.
• Cap how many keys one request can create from outside input. That limits how much work an attacker can trigger. Choose a limit that suits the request or the resources involved.

What a hash function is, and how cryptographic hashes differ, is covered in What a hash function does. For another case where average and worst case split apart, see when quicksort hits O(n²); the amortized cost that the * in Rust’s table stands for is explained in dynamic arrays and amortized time.