You benefit from hash functions every day. They're used in databases to optimise queries, they're used in data structures to make things faster, they're used in security to keep data safe. Almost every interaction you have with a computer will involve hash functions in one way or another.
Hash functions are everywhere... But what is a hash function, and how do they work?
In this post, I'm going to demystify hash functions. I'll start by showing you a simple hash function, then show you how to test if a hash function is good or not, and then I'll demonstrate a real-world use of hash functions: the hash map.
# What is a hash function?
Hash functions are functions that take an input, usually a string, and return a number. If you call the same hash function with the same input multiple times, it will always return the same number. Hash functions also promise that any number they return will be within a promised range. Different hash functions have different ranges, but it's common to see 32-bit integers used as the return value. These have a range between 0 and 4,294,967,295.
In theory, this is a hash function:
function hash(input) {
return 0;
}Even without knowing what hash functions are used for, though, it should come as no surprise that one is useless. We don't need to rely on gut instinct, though. Let's see how we can objectively measure how good a hash function is.
# What makes a hash function good?
The number of possible inputs to a hash function vastly outnumbers the possible outputs. Think about it, there are an almost infinite number of unique strings but only a little more than 4 billion unique integers representable with 32-bits. So, inevitably, some inputs hash to the same output. These are called "collisions", and a good hash function tries its best to minimise the likelihood of them.
If we wrote a hash function that returned a number in the range 0 to 7, and we gave it 9 unique inputs, we're guaranteed at least 1 collision.
| Input | Equals | Hash output |
|---|---|---|
hash( | == | |
hash( | == | |
hash( | == | |
hash( | == | |
hash( | == | |
hash( | == | |
hash( | == | |
hash( | == | |
hash( | == |
These 9 inputs only product 1 collision, but other sets of 9 inputs could produce multiple collisions. A good hash function tries to have the lowest number of collisions it can on average.
Let's visualise these collisions. Below, you can use the
This is an idealised example, in reality hash functions won't output perfectly sequential numbers like this. It'll end up looking more like this:
But the idea is the same: a good hash function, with enough inputs, should produce a fairly uniform grid.
You're right, we're going to be creating "fake" collisions on our grid. It's okay, though, because incrementing every square by 100 is just as good as incrementing every square by 1. Bad hash functions stand out, we'll see that shortly.
Let's look at something real: 10,000 randomly generated strings hashed with a
proper hash function called
This is what a good hash function looks like. It isn't perfect, there's bright bits and dark bits, but broadly speaking it's quite uniform. It looks a bit like TV static.
What would our grid look like if we used a bad hash function?
// This is a bad hash function.
function hash(input) {
let hash = 0;
for (let c of input) {
hash += c.charCodeAt(0);
}
return hash % 1000000;
}This function loops through input and sums the numeric values of each
character. It then makes sure that the value is between 0 and 1000000 by using
the modulo operator. Let's call this hash function
Here it is on the grid. Reminder, this is 10,000 randomly generated strings that we're hashing.
You can see a distinct,
All of the bright squares for
How about if we hash 10,000 common English words from public-domain books?
We see a clear striping pattern on the
# The avalanche effect
Another way hash functions get evaluated is on something called the "avalanche effect." This refers to how many bits in the output value change when just a single bit of the input changes. To say that a hash function has a good avalanche effect, a single bit flip in the input should result in an average of 50% the output bits flipping.
Below, I'm visualising the avalanche effect by showing two 8-bit binary
numbers. The top number is the input value, and the bottom number is the
Let's see how
Well this is embarassing. Because
Let's zoom out and look at the avalanche effect of these hash functions as a histogram. I counted the bit flips across all 3 datasets: random strings, numbers from 1 to 10,000, and top 10,000 English words. The x-axis shows how many bits flipped in the output as a percentage, and the y-axis shows how often that many bits were flipped.
The
# Why all of this matters
The "map" data structure maps keys to values. Here's how they look in JavaScript:
const map = new Map();
map.set("hello", "world");
console.log(map.get("hello"));Here we take a key-value pair ("hello" → "world") and store it in the map
on line "hello" on line "world".
There are many different ways to implement the map data structure, but one of the most popular is the "hash map." Hash maps need a hash function with a uniform distribution in order to be fast. To understand why, let's implement a simple one.
To start off, a constructor:
class HashMap {
constructor() {
this.buckets = [[], [], []];
}
}The only state our hash map needs is these "buckets." We're going to store
items of the form { key, value } in these buckets. I'm using 3 buckets so
that this code displays nicely on devices with smaller screens. In reality, you
could have however many buckets you want. Real-world hash maps even dynamically
change how many buckets they have as you add more items, but we aren't going
to worry about that here.
We map a key to a bucket by hashing the key, like so:
class HashMap {
// ...
getBucket(key) {
const hash = murmur3(key);
const index = hash % this.buckets.length;
return this.buckets[index];
}
}The getBucket method uses key
passed in to find a bucket to use. This is the only place in our hash map code
that a hash function is used.
Once we have a bucket, we have to find the entry with the exact key we're looking for.
class HashMap {
// ...
getEntry(bucket, key) {
for (const entry of bucket) {
if (entry.key === key) {
return entry;
}
}
return null;
}
}The getEntry method takes a bucket and a key and scans the bucket until
it finds an entry with the given key. If no entry is found, null is returned.
Putting these methods together, we can now add values to our hash map.
class HashMap {
// ...
set(key, value) {
const bucket = this.getBucket(key);
const entry = this.getEntry(bucket, key);
if (entry) {
entry.value = value;
return;
}
bucket.push({ key, value });
}
}The set method It takes a key-value pair and stores it in our hash map. If an
entry is found, its value is overwritten. If no entry is found, the key-value
pair is added to the map. In JavaScript, { key, value } is shorthand for { key: key, value: value }.
Then getting values back out of the hash map is done in a very similar way.
class HashMap {
// ...
get(key) {
const bucket = this.getBucket(key);
const entry = this.getEntry(bucket, key);
if (entry) {
return entry.value;
}
return null;
}
}The get method uses uses getBucket and getEntry to find the entry related
to the key passed in, just like set does. If an entry is found, its value
is returned. If one isn't found, null is returned.
Here's a visual representation of this hash map in action. Press the +
button to add a new key-value pair using our set method. To keep the
visualisation simple, if a bucket were to "overflow," the buckets are all
reset.
Because we're using
For a different perspective on that, imagine we used that useless hash function
from way back at the start. The one that always returned 0. That would put
every key-value pair into the first bucket, and finding an item in our hash map
would require us to scan through every single item in the worst case. With a
good hash function, we only have to scan total_items / num_buckets on
average.
Let's see how
Interestingly,
Not so fast, Haskie. We need to talk about a serious problem. The distribution
looks okay on these sequential numbers, but we've seen that
Let's take the same 3 datasets we've been using throughout: 10,000 random
strings, the numbers from 1 to 10,000 as strings, and the top 10,000 English
words. We'll hash all of them with both
| Dataset | ||
|---|---|---|
| Random strings | 0% | 93% |
| Numbers 1–10,000 | 0% | 99.09% |
| English words | 0% | 89.95% |
So while it may look good that
# Manufactured collisions
Now it's
What's happening here? Why do all of these jibberish strings hash to the same number?
I hashed 141 trillion random strings to find values that hash to the number
1228476406 when using
Yes, and it only took me 25 minutes. Computers are fast.
Bad actors having easy access to collisions can be devastating if your software builds hash maps out of user input. Take HTTP headers, for example. They look like this:
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.comThey're Key: Value pairs, so people tend to use hash maps to store them. We
can pass any headers we want, so we can be really mean and use keys we know
will cause collisions. This can significantly slow down the server.
This isn't theoretical, either. If you search "HashDoS" you'll find a lot more examples of this. It was a really big deal in the mid-2000s.
There are a few ways to mitigate this. For example, you could only accept valid
header keys into your map. This works for HTTP headers, but if you're storing
other data in your map you may not be able to do this.
Earlier in this post we showed some examples of hash function implementations.
Those implementations took a single argument: input. Lots of modern hash
functions take a 2nd parameter: seed (sometimes called salt). In the case
of
So far, I've been using 0 as the seed. Let's see what happens with the
collisions I've collected when we use a seed of 1. The following sequence of
keys is the exact same sequence from before that all hashed to 1228476406
with seed 0.
Just like that, 0 to 1, these strings no longer all hash to the same number. This is the purpose of the seed: it randomises the output of the hash function in an unpredictable way. How it achieves this is beyond the scope of this article, all hash functions do this in their own way.
I think you're right. Let's see how it looks on a grid.
It is definitely an improvement, but it's not at all close to the nice uniform
distribution we're used to seeing from
How well seeding works seems to differ between hashing functions. I generated
collisions for a few more well-known hash functions and the component below
allows you to drag the
Seeded hash functions still return the same output for the same input, it's
just that the input is a combination of input and seed. Things that collide
with one seed are very unlikely to collide when using a different seed. It's
common to generate a random number to use as the seed when the process starts,
so that every time you run your program the seed is different. If you don't
know the seed, it is now much harder to cause harm.
# What does a hash function look like
I've gone through the whole post here without ever showing you the internals
of
// https://github.com/garycourt/murmurhash-js/blob/master/murmurhash3_gc.js
export default function murmur3(key, seed) {
var remainder, bytes, h1, h1b, c1, c2, k1, i;
remainder = key.length & 3;
bytes = key.length - remainder;
h1 = seed;
c1 = 0xcc9e2d51;
c2 = 0x1b873593;
i = 0;
while (i < bytes) {
k1 =
((key.charCodeAt(i) & 0xff)) |
((key.charCodeAt(++i) & 0xff) << 8) |
((key.charCodeAt(++i) & 0xff) << 16) |
((key.charCodeAt(++i) & 0xff) << 24);
++i;
k1 = ((((k1 & 0xffff) * c1) + ((((k1 >>> 16) * c1) & 0xffff) << 16))) & 0xffffffff;
k1 = (k1 << 15) | (k1 >>> 17);
k1 = ((((k1 & 0xffff) * c2) + ((((k1 >>> 16) * c2) & 0xffff) << 16))) & 0xffffffff;
h1 ^= k1;
h1 = (h1 << 13) | (h1 >>> 19);
h1b = ((((h1 & 0xffff) * 5) + ((((h1 >>> 16) * 5) & 0xffff) << 16))) & 0xffffffff;
h1 = (((h1b & 0xffff) + 0x6b64) + ((((h1b >>> 16) + 0xe654) & 0xffff) << 16));
}
k1 = 0;
switch (remainder) {
case 3: k1 ^= (key.charCodeAt(i + 2) & 0xff) << 16;
case 2: k1 ^= (key.charCodeAt(i + 1) & 0xff) << 8;
case 1: k1 ^= (key.charCodeAt(i) & 0xff);
k1 = (((k1 & 0xffff) * c1) + ((((k1 >>> 16) * c1) & 0xffff) << 16)) & 0xffffffff;
k1 = (k1 << 15) | (k1 >>> 17);
k1 = (((k1 & 0xffff) * c2) + ((((k1 >>> 16) * c2) & 0xffff) << 16)) & 0xffffffff;
h1 ^= k1;
}
h1 ^= key.length;
h1 ^= h1 >>> 16;
h1 = (((h1 & 0xffff) * 0x85ebca6b) + ((((h1 >>> 16) * 0x85ebca6b) & 0xffff) << 16)) & 0xffffffff;
h1 ^= h1 >>> 13;
h1 = ((((h1 & 0xffff) * 0xc2b2ae35) + ((((h1 >>> 16) * 0xc2b2ae35) & 0xffff) << 16))) & 0xffffffff;
h1 ^= h1 >>> 16;
return h1 >>> 0;
}# Playground
As is tradition, I've made a playground for you to write your own hash functions and see them visualised with the grids seen in this article. Try it in the hashing playground!
Enjoyed this? Sign up to get notified of new posts.
# Conclusion
We've covered what a hash function is, some ways to measure how good it is, what happens when it's not good, and some of the ways they can be broken by bad actors.
The universe of hash functions is a large one, and we've really only scratched the surface in this post. We haven't spoken about cryptographic vs non-cryptographic hashing, and we've touched on only 1 of the thousands of use-cases for hash functions.
Some further reading I recommend if you're really enthusiastic about this topic and want to learn more:
- https://github.com/rurban/smhasher this repository is the gold standard for testing how good hash functions are. They run a tonne of tests against a wide number of hash functions and present the results in a big table. It will be difficult to understand what all of the tests are for, but this is where the state of the art of hash testing lives.
- https://djhworld.github.io/hyperloglog/ this is an interactive piece on a data structure called HyperLogLog. It's used to efficiently count the number of unique elements in very, very large sets. It uses hashing to do it in a really clever way.
- https://www.gnu.org/software/gperf/ is a piece of software that, when given the expected set of things you want to hash, can generate a "perfect" hash function automatically.
Feel free to join the discussion on Hacker News!
Wanna tell me what you thought of the post? This form sends a notification directly to my phone.
# Acknowledgements
Thanks to everyone who read early drafts and provided invaluable feedback.
And everyone who helped me find