Hash Functions: What "Random" Means When It Has to Be Deterministic

Hook #

A Ruby Hash gives you O(1) lookup. So does Python's dict, Java's HashMap, Go's map. They all do the same trick: take whatever key you give them — a string, a tuple, an arbitrary object — and turn it into a number that picks a bucket. The function that does the turning is called a hash function, and choosing the right one is the difference between a hash table that runs in O(1) and one that quietly degrades to O(n) on production data. This lesson is about what makes a hash function good, why "looks random" is the wrong intuition, and why the same primitive shows up in cryptography, distributed systems, and the fingerprint at the bottom of every Git commit.

What you'll be able to do by the end of this lesson #

• State the four properties a good non-cryptographic hash function must have: determinism, uniformity, avalanche, speed.
• Distinguish a non-cryptographic hash function (MurmurHash, FNV) from a cryptographic one (SHA-256, BLAKE3) by what each is designed to resist.
• Explain why a hash function for integers can't just return the integer itself.
• Recognise three places hash functions appear outside hash tables: content addressing (Git, IPFS), bloom filters, distributed hash tables.

A quick try before we start #

Suppose you want to hash strings to a bucket index in 0..15 (so, 16 buckets). You write this:

rubydef hash(s)
  s.bytes.sum % 16
end

Try it on "abc" and "bca" and "cab". What buckets do they land in?

Now try it on "hello", "olleh", and "lehlo". Same question.

What's wrong with this hash function as a candidate for a hash table? Write down at least two failures before reading on.

The core idea, from first principles #

A hash function is a function h: K → N from some key space K (strings, integers, tuples, arbitrary structured values) to a fixed range of natural numbers, typically [0, m) for some m (the number of buckets). It's deterministic — calling h(k) twice on the same k always returns the same number — but the pattern of outputs across different keys should look random.

That "look random" phrase is doing a lot of work. Let's make it precise. A good non-cryptographic hash function has four properties:

1. Determinism #

h(k) is a function of k alone. No clocks, no random seeds re-rolled per call, no global state. The same key must always hash to the same bucket, or your hash table can't find what it put there. This is so basic it's easy to forget — but it's the reason a hash function can't be s.bytes.sum + rand(16).

(Caveat: seeded hashing is fine — and increasingly common as a defence against denial-of-service via hash collisions. The seed is fixed per-process or per-table, not per-call. We'll meet this in lesson 3.)

2. Uniformity #

If you hash n random keys into m buckets, you want roughly n/m keys per bucket. Not clumped. Not skewed toward low or high indices. The mathematical statement: for any well-behaved input distribution, the hash function should produce a roughly uniform distribution over [0, m).

The s.bytes.sum % 16 function fails uniformity catastrophically. The two examples in the quick-try hash to the same bucket because they have the same letters — they're anagrams of each other, and sum doesn't care about order. Real strings have positional structure (abc ≠ cba to the human reading them), and a good hash function preserves that distinction by mixing positions, not just summing them.

The standard fix is to multiply by a small odd constant as you fold characters in:

rubydef hash(s)
  h = 0
  s.bytes.each { |b| h = (h * 31 + b) & 0xFFFFFFFF }
  h % 16
end

This is Java's String.hashCode(). The 31 is the small odd constant. Why 31? Two reasons: it's prime (so the multiplications mix bits non-trivially), and h * 31 = (h << 5) - h — a single shift and subtract, fast on every CPU. The pattern — fold each byte into a running accumulator while shifting bits up so position matters — is the universal shape of byte-stream hashing.

3. Avalanche #

A small change in the input should cause a big change in the output. Specifically: flipping one input bit should change roughly half the output bits. This is the avalanche property, and it's what gives hash functions their "look random" feel.

Why does it matter? Consider keys like "user_id_1", "user_id_2", "user_id_3". Without avalanche, consecutive integers map to consecutive buckets (lots of collisions in adjacent slots, called clustering in lesson 3). With avalanche, consecutive integers map to scattered buckets (clustering disappears).

Test it on Java's String.hashCode():

• "abc".hashCode() = 96354
• "abd".hashCode() = 96355

That's a one-bit change in the input (c → d differs in the low bit) producing a one-bit change in the output. Java's hash fails the avalanche test. It works "well enough" for hash tables because the modulo by table size mixes things further, but better hash functions exist (MurmurHash3, xxHash, CityHash) that do the bit-mixing properly and don't depend on modulo to recover.

4. Speed #

A hash function is on the hot path of every hash-table lookup. If hashing is slow, the O(1) lookup becomes "O(1) per operation but a large constant" — which can lose to O(log n) on a BST in absolute time. Production hash functions for byte data hash gigabytes per second on a modern CPU (xxHash3 hits 30+ GB/s); the cost of hashing a 32-byte string is effectively free relative to the L1 cache miss of fetching the bucket.

The trade-off this implies: cryptographic hash functions are usually too slow for hash tables. SHA-256 hashes ~1 GB/s on a typical CPU — 30x slower than xxHash. The extra speed is paid for in cryptographic resistance you don't need for a hash table.

Why these four are the whole list #

Determinism is a correctness requirement (the table can't work without it). Uniformity gives you the O(1) average case (buckets are evenly loaded). Avalanche gives you robustness against patterned inputs (no clustering on adjacent keys). Speed gives you the constant that makes O(1) actually feel fast.

Notice what's not on the list: cryptographic security. A non-cryptographic hash function can be reverse-engineered ("given a target bucket b, find inputs that hash to b") and that's fine for a hash table. The instant you need adversaries-can't-predict-the-output, you're in cryptography's territory, and you reach for a different tool.

The cryptographic vs non-cryptographic split #

The shift from non-cryptographic to cryptographic is not about quality; both are excellent at what they're designed for. It's about what you're paying for. Non-cryptographic hash functions pay the minimum for the four properties. Cryptographic hash functions additionally pay for resistance against an adversary trying to construct bad inputs — and the cost is roughly 10-30x in speed.

Why this works the way it does #

The deep reason these properties matter: hash functions are how we replace an O(log n) ordered lookup with an O(1) random-bucket lookup, and the O(1) is only as good as the randomness. A perfectly uniform hash function gives O(1) expected. A clumpy one gives the linked-list-per-bucket degeneration to O(n).

The historical reason hash functions exist: memory is faster than search. Searching a sorted array of n keys takes O(log n) — at n = 1 million, that's 20 comparisons. A hash table needs one comparison after the bucket lookup. The cost of the bucket lookup is the cost of the hash function plus one array index. For 32-byte string keys, that's maybe 20 nanoseconds on a modern CPU — versus 20 cache-missing comparisons in a tree, which can be microseconds.

The mathematical depth (worth knowing exists, not memorising on first pass): universal hashing is the rigorous answer to "how do I choose a hash function that gives O(1) expected time for any input, even one chosen adversarially?" The trick is to pick the hash function randomly from a family of hash functions, after the inputs are known. Then no fixed adversary can construct a worst case. MIT 6.006's lecture 9 is the canonical exposition; the technique underlies the security mitigations every modern language's hash table uses against denial-of-service attacks (more in lesson 3).

Explain it back to me #

A colleague writes a hash function for IPv4 addresses (32-bit integers) as def hash(ip); ip % 16; end — they say "it's already a number, no need to do anything fancy."

In your own words, what's wrong with this — using the words "uniformity" and "avalanche"? Hint: think about real IPv4 addresses in a corporate network — most start with 10. or 192.168. — and what their low 4 bits look like.

And one more: why is String#hash in Ruby seeded with a random value at process startup (per-process, but the same for every call within the process)? What attack is the seed preventing?

A small exercise #

Three short tasks:

1. Anagram failure. Write a hash function for strings in 5 lines or less that gives the same hash to all anagrams of the same word. Then write a sentence saying why this function is unsuitable for a hash table. (You're proving you understand failure mode.)

2. Distribution check. In any language, hash the integers 0..9999 using i % 16 and using (i * 2654435761) >> 28 (Knuth's multiplicative hash for 32-bit, modulo 16). Count the bucket counts. Which is more uniform? Why?

3. Property identification. For each of the following hash-function uses, name which of the four properties matters most: a. Sharding a list of 1M user records across 32 database servers b. Detecting if two large files are identical without comparing them byte by byte c. Computing a cache key from a complex request object d. Hashing passwords for storage in a user database

Where this connects #

Backward: Course 1.1 lesson 7 (Number Theory and Modular Arithmetic) gave you the modulo arithmetic that hash functions use to fold output into a bucket range. The choice of m (table size) is itself a number-theoretic question — prime numbers minimise certain collision patterns; powers of 2 enable fast bit-masking instead of slow division. Course 2.1 lesson 3 (ADTs) listed Map and Set with hash tables as the canonical implementation; this is the lesson where hash tables start to make mechanical sense.

Forward: Lesson 2 (Hash Tables) is where the four properties become four bullet points in the performance analysis. Lesson 3 (Open Addressing) is where the avalanche property starts to really matter — bad avalanche causes primary clustering, which collapses linear probing into O(n). Lesson 4 (Bloom Filters) uses multiple hash functions per insertion to get its space savings — and they have to be independent, which is itself a non-trivial property. Course 3.12 (Cryptography) is where the cryptographic-resistance column of the table becomes the entire subject. Course 7.x (Distributed Systems) is where consistent hashing — a clever use of uniform hash functions for partitioning — solves the database-sharding problem. Git's content addressing, IPFS's CIDs, every blockchain's block ID — all are cryptographic hashes of content, treating the hash itself as the canonical identifier of the data. Once you've internalised "hash function = deterministic random function," you'll see the pattern repeatedly across the rest of CS.