Hashing

Translations: English

This page makes heavy use of JavaScript to visualise the concepts discussed. Viewing it without JavaScript will be a strange experience, as the text talks about the visualisations. I strongly recommend either enabling JavaScript, or not wasting your time.

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 foundational, and they are everywhere.

But what is a hash function, and how do they work?

In this post, we're going to demystify hash functions. We're going to start by looking at a simple hash function, then we're going to learn how to test if a hash function is good or not, and then we're going to look at 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 produce a number. If you were to call a hash function multiple times with the same input, it will always return the same number, and that number returned will always be within a promised range. What that range is will depend on the hash function, some use 32-bit integers (so 0 to 4 billion), others go much larger.

If we were to write a dummy hash function in JavaScript, it might look like this:

function hash(input) {
  return 0;
}

Even without knowing how hash functions are used, it's probably no surprise that this hash function is useless. Let's see how we can measure how good a hash function is, and after that we'll do a deep dive on how they're used within hash maps.

# What makes a hash function good?

Because input could be any string, but the number returned is within some promised range, it's possible that two different inputs can return the same number. This is unavoidable, there are an infinite number of possible strings but only a fixed range of outputs from any given hash function. When this happens it is called a "collision," and good hash functions try to minimise how many collisions they produce.

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	Hash output
`hash("to")`	== 3
`hash("the")`	== 2
`hash("café")`	== 0
`hash("de")`	== 6
`hash("versailles")`	== 4
`hash("for")`	== 5
`hash("coffee")`	== 0 (collision!)
`hash("we")`	== 7
`hash("had")`	== 1

There's only 1 collision above, 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.

We can actually visualise this. Below, you can use the slider to cycle through numbers. These represent the outputs of a hash function, modulo the number of squares in a grid. Our grid here has 16 squares, so we do n % 16. We use the resulting number to locate a square on the grid and we make it a bit brighter. We do this many times and we end up with a uniformly bright grid.

This is an idealised example, in reality hash functions aren't going to output a perfectly uniform distribution like this. It'll end up looking more like this instead:

You said that when a hash function outputs the same value for 2 different inputs, that's a collision. But if we have a hash function that outputs values in a big range, and we mapped those to a smaller range with modulo, aren't we going to create lots of collisions on the grid that aren't actually collisions? On a 16-square grid, 1 and 17 both map to the 2nd square.

This is a great observation. You're right, we're going to be creating fake collisions on our grid. It's okay, though, because if the hash function is good we will still see an even distribution. Incrementing every square by 100 is just as good a distribution as incrementing every square by 1. If we have a bad hash function that collides a lot, that will still stand out. We'll see this shortly.

Let's look at something real: 10,000 randomly generated strings hashed with a proper hash function called murmur3. Move the slider back to see how the grid looks with fewer of the items placed on it. Click randomise to generate a new set of 10,000 strings.

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 well distributed. 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 stringSum.

Here it is on the grid. Reminder, this is 10,000 randomly generated strings that we're hashing.

You can see a distinct, lightdark band through the middle. This is not what we want at all, and this is with randomly generated values! The problem gets worse if there's some pattern to the input values, for example the sequence of numbers from 1 to 10,000 as strings.

All of the bright squares for stringSum are concentrated into a small range, while murmur3 still looks like noise.

How about if we hash the top 10,000 most common English words?

We see a clear striping pattern on the stringSum grid. As usual, murmur3 looks like noise. This is the power of a good hash function: no matter the input, the output is evenly distributed. Let's talk about one more way to visualise good hash functions before we talk about hash maps.

# 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.

It's this property that helps hash functions avoid forming patterns in the grid. If small changes in the input result in small changes in the output, you get patterns. Patterns indicate poor distribution, and a higher rate of collisions.

Below, we are visualising the avalanche effect by showing two 8-bit binary numbers. The top number is the input value, and the bottom number is the murmur3 output value. Click an input bit to flip it, or use flip random bit to choose one at random. Changed bits get an outline and become the hash function's colour.

murmur3 does well, though you will notice that sometimes fewer than 50% of the bits flip and sometimes more. This is okay, provided that it is 50% on average.

Let's see how stringSum performs.

Well this is embarassing. The output is equal to the input, and so only a single bit flips each time. This does make sense, because stringSum just sums the numeric value of each character in the string. This example only hashes the equivalent of a single character, which means the output will always be the same as the input.

We can zoom out and look at a histogram of this avalanche effect, showing what percentage of the bits flipped for each of the 10,000 data points in the random, sequential numbers, and popular words datasets. murmur3 shows a consistent normal distribution centered around 50% for all 3 input sets, while stringSum... doesn't.

# Why all of this matters

We've taken the time to understand some of the ways to determine if a hash function is good, but we've not spent any time talking about why it matters. Let's fix that by talking about hash maps.

To understand hash maps, we first must understand what a map is. A map is a data structure that allows you to store key-value pairs. Here's an example 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 ⁠. Then we print out the value associated with the key "hello" on line ⁠, which will be "world".

A more fun real-world use-case would be to find anagrams. An anagram is when two different words contain the same letters, for example "antlers" and "rentals", or "article" and "recital." If you have a list of words and you want to find all of the anagrams, you can sort the letters in each word alphabetically and use that as a key in a map.

let words = [
  "antlers",
  "rentals",
  "sternal",
  "article",
  "recital",
  "flamboyant",
];

let map = new Map();

for (let word of words) {
  let key = word.split("").sort().join("");

  if (!map.has(key)) {
    map.set(key, []);
  }
  map.get(key).push(word);
}

This code results in a map with the following structure:

{
  "aelnrst": ["antlers", "rentals", "sternal"],
  "aceilrt": ["article", "recital"],
  "aabflmnoty": ["flamboyant"]
}

# Implementing our own simple hash map

Hash maps are one of many map implementations, and there are many ways to implement hash maps. The simplest way, and the way we're going to demonstrate, is to use a list of lists. The inner lists are often referred to as "buckets" in the real-world, so that's what we'll call them here. A hash function is used on the key to determine which bucket to store the key-value pair in, then the key-value pair is added to that bucket.

Let's walk through a simple hash map implementation in JavaScript. We're going to go through it bottom-up, so we'll see some utility methods before getting to the set and get implementations.

class HashMap {
  constructor() {
    this.buckets = [[], [], []];
  }
}

We start off by creating a HashMap class with a constructor that sets up 3 buckets. We use 3 buckets so that this code displays nicely on devices with smaller screens. In reality, you could have however many buckets you want.

class HashMap {
  // ...
  getBucket(key) {
    let h = murmur3(key);
    const index = h % this.buckets.length;
    return this.buckets[index];
  }
}

The getBucket method uses murmur3 on the 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.

class HashMap {
  // ...
  getEntry(bucket, key) {
    for (let 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.

class HashMap {
  // ...
  set(key, value) {
    let bucket = this.getBucket(key);
    let entry = this.getEntry(bucket, key);
    if (entry) {
      entry.value = value;
      return;
    }
    bucket.push({ key, value });
  }
}

The set method is the first one we should recognise from our earlier JavaScript Map examples. It takes a key-value pair and stores it in our hash map. It does this by using the getBucket and getEntry methods we created earlier. 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 }.

class HashMap {
  // ...
  get(key) {
    let bucket = this.getBucket(key);
    let entry = this.getEntry(bucket, key);
    if (entry) {
      return entry.value;
    }
    return null;
  }
}

The get method is very similar to set. It 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.

That was quite a lot of code. What you should take away from it is that our hash map is a list of lists, and a hash function is used to know which of the lists to store and retrieve a given key from.

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 murmur3 as our hash function, you should see good distribution between the buckets. It's expected you'll see some imbalance, but it should generally be quite even.

To get a value out of the hash map, we first hash the key to figure out which bucket the value will be in. Then we have to compare the key we're searching for against all of the keys in the bucket.

It's this search step that we minimise through hashing, and why murmur3 is optimised for speed. The faster the hash function, the faster we find the right bucket to search, the faster our hash map is overall.

This is also why reducing collisions is so crucial. If we did decide to use that dummy hash function from all the way at the start of this article, the one that returns 0 all the time, we'll put all of our key-value pairs into the first bucket. Finding anything would mean we have to check all of the values in the hash map. With a good hash function, with good distribution, we reduce the amount of searching we have to do to 1/N, where N is the number of buckets.

Let's see how stringSum does.

Interestingly, stringSum seems to distribute values quite well. You notice a pattern, but the overall distribution looks good.

Finally! A win for stringSum. I knew it would be good for something.

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 stringSum doesn't have a good avalanche effect. This doesn't end well.

# Real-world collisions

Let's look at 2 real-world data sets: IP addresses and English words. What I'm going to do is take 100,000,000 random IP addresses and 466,550 English words, hash all of them with both murmur3 and stringSum, and see how many collisions we get.

Collisions, as a count and percentage of each dataset.
Dataset	murmur3	stringSum
IP addresses	1,156,959 1.157%	99,999,566 99.999%
English words	25 0.005%	464,220 99.5%

When we use hash maps for real, we aren't usually storing random values in them. We can imagine counting the number of times we've seen an IP address in rate limiting code for a server. Or code that counts the occurrences of words in books throughout history to track their origin and popularity. stringSum sucks for these applications because of its extremely high collision rate.

# Manufactured collisions

Now it's murmur3's turn for some bad news. It's not just collisions caused by similarity in the input we have to worry about. Check this out.

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 murmur3. Hash functions have to always return the same output for a specific input, so it's possible to find collisions by brute force.

I'm sorry, 141 trillion? Like... 141 and then 12 zeroes?

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. An HTTP request looks like this:

GET / HTTP/1.1
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.com

You don't have to understand all of the words, just that the first line is the path being requested and all of the other lines are headers. Headers are Key: Value pairs, so HTTP servers tend to use maps to store them. Nothing stops us from passing any headers we want, so we can be really mean and pass headers 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 that are specific to HTTP servers: ignoring jibberish header keys and limiting the number of headers you store, for example. But modern hash functions like murmur3 offer a more generalised solution: seeding.

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 murmur3, this seed is a number.

So far, we'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.

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.

Let's see how it looks on the grids.

It's not great, right? It is definitely an improvement, but it's not at all close to the nice uniform distribution we're used to seeing from murmur3.

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 slider to change the seed. You should see murmur3 and xxHash32 modestly improve, while wyhash32 and fasthash32 do much better.

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.

# 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!

# 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, we've touched on only 1 of the thousands of use-cases for hash functions, and we haven't talked about how exactly modern hash functions actually work.

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.

delroth, Manon, Aaron, Charlie

And everyone who helped me find murmur3 hash collisions:

Indy, Aaron, Max