What Is a Hash Function?
Hashing Fundamentals · Data & Hashing track
6 min read
In this module
Fingerprinting Data
Imagine you've got a 10 gigabyte file and you want to know whether it's changed since yesterday. You could compare every single byte — all 10 billion of them — against yesterday's copy. Or you could compute a short "fingerprint" of the file and check the fingerprints. Match? File hasn't changed.
A hash function takes input of any size and produces a fixed-size output called a hash (sometimes a digest, sometimes a fingerprint). Same input, same hash, every time. Different inputs should — ideally — produce different hashes.
sha256("Hello") --> "185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969"sha256("Hello!") --> "334d016f755cd6dc58c53a86e183882f8ec14f52fb05345887c8a5edd42c87b7"sha256("Hello" again) --> "185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969"Three things to notice:
- The same input ("Hello") always gives the same output — determinism.
- A tiny change (adding "!") scrambles the output completely — the avalanche effect.
- Both outputs are the same length (64 hex characters = 256 bits) no matter the input size.
A hash function maps input of arbitrary size to a fixed-size output. It is deterministic (same input, same output), and a good hash function exhibits the avalanche effect (small input changes cause large output changes). Hashing is a one-way operation - you cannot recover the input from the hash.
One-Way Functions
Cryptographic hash functions are one-way. Given the output, there's no efficient way to figure out the input. You can't "reverse" the hash.
That's a different beast from encryption, where decrypting gets the original data back. Hashing throws information away. A 10 GB file collapses to 256 bits — the vast majority of the original is gone. The hash is a summary, not an encoding.
Password storage shows why one-wayness earns its keep. A website stores the hash of your password, not the password itself. Log in, and the site hashes what you typed and compares it to the stored hash. Match? You're in. If an attacker steals the database, they walk away with hashes, not passwords. To recover the original they'd have to try enormous numbers of guesses, hashing each one and looking for a match. For a long random password and a deliberately slow password hash, that's years of work. A short or common password stored with a fast hash like plain SHA-256 is another story: a GPU rig tries billions of guesses a second and finds it in minutes.
Why Collisions Must Exist
A hash function maps infinitely many possible inputs onto finitely many possible outputs. SHA-256 has 2^256 possible outputs — astronomically large, still finite. The pigeonhole principle guarantees that different inputs must collide on the same hash somewhere. These are collisions.
The question isn't whether collisions exist (they have to). The question is whether you can actually find one. A good hash function makes finding collisions computationally infeasible. For SHA-256, you'd need to try roughly 2^128 inputs (thanks to the birthday attack) before expecting a hit. At a trillion hashes per second, that's longer than the age of the universe.
This gap between theoretical existence and practical findability is the entire game in cryptographic security. Collisions exist mathematically. If nobody can find them, the hash function does its job.
A Simple Hash Function
To build intuition, consider a trivial hash function: sum all the bytes of the input, modulo 256.
function simple_hash(data) { sum = 0 for byte in data { sum = (sum + byte) % 256 } return sum}
simple_hash("AB") // (65 + 66) % 256 = 131simple_hash("BA") // (66 + 65) % 256 = 131 - collision!Awful hash function. Finding collisions is trivial — rearrange the bytes. There's no avalanche effect either: nudge one byte by 1 and the output shifts by at most 1. Real hash functions are far hairier, layering bitwise operations, rotations, substitutions, and many rounds of mixing until the output is well and truly scrambled.
Try breaking it yourself. The program below prints the byte-sum hash next to FNV-1a, a simple multiply-and-XOR hash used in plenty of hash tables. Add your own strings to the list and find a new trio that shares a byte-sum hash, then check whether FNV-1a lets any of them collide.
Any anagram collides under the byte sum, and so does any pair of edits that cancel out: "Hdllp" lowers one byte of "Hello" by 1 and raises another by 1, so it lands on the same value. FNV-1a keeps them apart because each byte is multiplied into the running state, so position matters and one changed bit spreads into the high bits.
How Real Hash Functions Process Data
Real hash functions like SHA-256 chop the input into fixed-size blocks and feed each block through a compression function. The compression function eats the current internal state plus the next block of data, churns them through many rounds of arithmetic, and spits out a new internal state. Once every block has been digested, the final state is the hash.
Each round typically shifts bits, rotates values, XORs them together, applies modular addition, and feeds the output through lookup tables or non-linear functions. That layered, repeated mixing is what produces the avalanche effect: a single flipped input bit cascades through round after round until every output bit has felt the impact.
The Role of Hashing in Computing
Hashing shows up everywhere:
- Hash tables use hash functions to compute array indices for O(1) lookups
- Data integrity checks use hashes to spot corruption or tampering
- Password storage uses hashes so the actual password never needs to be stored
- Digital signatures hash a document before signing it — signing the full document would be too slow
- Git identifies every commit, tree, and file by its SHA-1 hash
- Blockchains chain blocks together using hashes
- Deduplication systems use hashes to spot identical chunks of data across huge storage pools
Hashing is one of those rare ideas that runs through every layer of the stack — data structures, filesystems, cryptography, distributed systems. Get it down here and you'll spot it resurfacing in nearly every module that follows.
The next lesson nails down what actually makes a hash function "good," and pulls apart the properties that separate a toy hash from a cryptographically strong one.