Hash Functions: The Mathematics Behind Modern Software

Change a single letter, "hello" to "Hello," and the SHA-256 hash changes completely:

hello → 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
Hello → 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969

Nothing about the second fingerprint resembles the first. That property, called the avalanche effect, is one reason hash functions sit underneath dictionaries in every programming language, password storage, file downloads, Git version control and blockchains.

Collisions Are Guaranteed

A hash function maps inputs of any length to outputs of a fixed length. SHA-256 always produces 256 bits.

There are infinitely many possible inputs but only 2²⁵⁶ possible outputs. By the pigeonhole principle, infinitely many different inputs must share the same hash. Collisions aren't a flaw you can design away. The goal of a good hash function is to make collisions impossible to find in practice.

What Makes a Good Hash Function?

All hash functions should be:

• Deterministic: the same input always gives the same output
• Fast to compute
• Uniform: outputs spread evenly across the range

Cryptographic hash functions also need:

• Preimage resistance: given a hash, you can't find an input that produces it
• Second-preimage resistance: given an input, you can't find a different one with the same hash
• Collision resistance: you can't find any two inputs with the same hash

Hashing for Data Structures

A hash table stores key-value pairs in an array. To find where a key goes:

index = hash(key) mod table_size

This is modular arithmetic turning a big number into an array position. With a good hash function, lookups take O(1) time on average, which is why dictionaries and sets are so fast.

A classic simple hash for strings treats characters as digits in a large base:

h = (c₀ × 31ⁿ⁻¹ + c₁ × 31ⁿ⁻² + … + cₙ₋₁) mod 2³²

Java's String.hashCode() uses exactly this form with base 31. When two keys land in the same slot, the table handles the collision by chaining entries or probing for another slot.

The idea dates back to IBM engineer Hans Peter Luhn, who described hashing for fast information retrieval in an internal IBM memo in 1953.

The Birthday Bound

How many random inputs until two share a hash? Not 2ⁿ, but about 2^(n/2). That's the birthday paradox: with 23 people, there's a better-than-even chance two share a birthday.

That's why cryptographic hashes need to be long: a 256-bit hash gives about 128 bits of collision security. See The Birthday Paradox.

An Insider Reference: When MD5 and SHA-1 Fell

MD5, designed by Ron Rivest in 1991, produces 128-bit hashes. In 2004, Chinese cryptographer Xiaoyun Wang and colleagues announced practical methods for finding MD5 collisions. Within a few years, researchers showed they could forge digital certificates with it.

The consequences became real in 2012, when the Flame espionage malware used an MD5 collision attack to forge a Microsoft code-signing certificate, letting it spread disguised as legitimate Windows updates.

SHA-1 (160 bits) was next. In February 2017, researchers from Google and CWI Amsterdam announced SHAttered, the first public SHA-1 collision: two different PDF files with the same hash. It required about 9.2 quintillion (2⁶³) SHA-1 computations. Browsers and certificate authorities had already begun abandoning SHA-1, and the attack confirmed they were right.

Today's standard is the SHA-2 family (including SHA-256), published by NIST in 2001, with SHA-3 standardized in 2015 as an alternative design.

Hashing Passwords

Websites shouldn't store your password. They store a hash of it, then hash whatever you type at login and compare. But fast hashes are a problem here: attackers with GPUs can test billions of guesses per second.

So password hashing adds two defenses:

• Salt: a random value added to each password before hashing, so identical passwords get different hashes and precomputed tables don't work
• Slowness: algorithms like bcrypt (1999), scrypt and Argon2 are deliberately expensive in time and memory

Other Everyday Uses

• Git identifies every commit and file by its hash, historically SHA-1 and now moving to SHA-256
• Downloads publish hashes so you can verify a file wasn't corrupted or tampered with
• Bitcoin mining is a search for inputs whose SHA-256 hash falls below a target
• Deduplication systems store identical files once by comparing hashes

Two Concepts Worth Knowing

Pigeonhole Principle

If you put more than n items into n boxes, at least one box holds two items. For hash functions, more possible inputs than outputs means collisions must exist.

Avalanche Effect

A function has the avalanche effect if flipping one input bit changes each output bit with probability about 1/2. It prevents similar inputs from producing similar hashes. View hashes bit by bit with the binary to hexadecimal converter.

Quick Answer: What Is a Hash Function?

A hash function converts data of any size into a fixed-size value, like a fingerprint. Hash tables use hashes to find data quickly. Cryptographic hash functions such as SHA-256 are designed so it's infeasible to reverse them or find two inputs with the same hash, even though collisions must exist mathematically.

Try Them Yourself

• Binary to Hexadecimal Converter: read a hash as bits
• Number Theory Formulas: modular arithmetic for hash tables
• Base-2 Logarithm Table: the birthday bound 2^(n/2)
• Random Number Generator: simulate collisions in small hash spaces
• The Math Behind Bitcoin: hashing as proof of work
• What Is a Checksum and Why Does It Work?: the simpler cousin of hashing

Pick numbers from 1 to 100 at random and stop when you get a repeat. On average you'll stop after about 12 or 13 picks, far sooner than 100. That's the birthday bound, the math every hash designer fights.