TRT
Sign in
mediumFoundationsconcept

Why do Python, Rust and Go randomize their string hashes?

Explain the attack that randomized hashing prevents, why it is realistic for a server, how a secret key defends against it, and what the defense costs.

TRT practice prompt — not a verified question from a named employer.

The Runtime Theory Team2 min read
Learn it firstWhat a hash function doesA hash function turns any key into a fixed-size number, quickly and the same way every time. Everything a hash table does starts there.

A strong answer

Start with the attack this prevents. A hash table is only fast while keys spread across its slots. If an attacker knows the hash function, they can generate thousands of strings that all have the same hash (hash flooding). Every one of them lands in the same slot, so each insert has to walk past all the earlier ones, and n inserts cost O(n²) work instead of O(n). This is called hash flooding.

It is a realistic attack because servers build hash tables from input they don't control: form fields, JSON object keys, HTTP headers and query parameters. In 2011, researchers showed that a single crafted request could keep a server busy for minutes on many popular web platforms.

Randomizing the hash takes away the attacker's knowledge. The language mixes a secret random key into every string hash. Python chooses its key when the process starts; Go and Rust choose a key for each new map. Within one table the hash is still deterministic, which is all the table needs. The attacker can't see the key, so they can't work out which strings will collide.

A key only helps if the hash function mixes it in thoroughly, so these languages pair it with a hash built for the job. Python and Rust use SipHash, which was designed to defend hash tables against flooding while staying fast on short keys. Go uses a seeded hash built on the processor's AES instructions where they are available.

The price is that hash values change from run to run, so a program must never store them or depend on the iteration order they produce.

What the interviewer is listening for

  • The attack: colliding keys turn O(1) operations into O(n), and n inserts into O(n²).
  • Why it is realistic: servers put untrusted input into hash tables.
  • How the defense works: a secret key, per process or per table, that the attacker can't see.
  • The trade-off: hashes are no longer stable between runs.

Common mistakes

  • Saying the randomization makes hashes "more random" or spreads ordinary keys better. A good fixed hash already spreads ordinary keys; the defense is against an adversary who chooses the keys.
  • Proposing a cryptographic hash such as SHA-256 for every lookup. It would resist flooding, but it is far too slow for a hash table. SipHash exists because it is keyed and fast.
  • Forgetting that Java took a different path. Its string hash is fixed by its specification, so Java limits the damage with tree bins instead.

This answer walks

Practice follow-ups

  1. 01Hashes now change between runs. How would you store hashed keys on disk, or route requests to servers by hash?
  2. 02Java's String.hashCode is fixed by its specification. How does Java's HashMap limit the damage instead?
  3. 03Why isn't a random key enough on its own if the hash function itself is weak?
  4. 04Where else in a web service does an attacker control the keys of a hash table?
  5. 05What does PYTHONHASHSEED=0 do, and when is it reasonable to set it?

More interviews in this track

hard · dsaHow would you count distinct users across a fleet of services in constant memory?hard · dsaWhy can't a sparse table answer range sums?hard · dsaWhy is a lock-free stack still hard to get right?

Not started

Sign in to save your learning progress.

Sign in to save