Why Is Everyone on Hook 3? Hash Functions

Pick a recipe that turns a name into a hook number without crowding the hooks: three recipes tried on one coat check, the three things a good one has to do, and the multiply-by-31 recipe your language's own hash codes use.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Name what makes a good hash function: the same key always gets the same number, it's fast, and it spreads keys evenly
  • Work out a key's bucket with a simple hash function, and spot keys that collide

Key takeaways

  • A good hash function gives the same key the same number every time, runs fast, and spreads keys evenly over the buckets.
  • A recipe that ignores part of the key, such as its length only or its letters in any order, sends different keys to the same bucket.
  • Multiplying the running total by a number such as 31 before adding each letter makes the position of every letter count.
  • C# and Python give a string a new hash code each time a program runs, so a hash code is never saved to use another day.

Before this: Finding Maya's Coat Without a Ticket: Hash Tables, where a recipe turns a name into a hook number.

The coat check from the last lesson is doing well, so the venue opens a second one with 16 hooks. On opening night the manager wants a recipe that's quick to work out in your head, and picks the number of letters in the name. By 8 p.m., five coats hang on hook 3, two on hook 4, and 13 hooks are empty. At 11 p.m., "It's under Zoe" means checking hook 3 one coat at a time: the slow line is back, because of the recipe.

A hash table is only as fast as its recipe. You'll meet hash functions whenever you use your own objects as dictionary keys (Java's hashCode, C#'s GetHashCode, Python's __hash__), in interview questions, and in the rare, baffling bug where a dictionary can't find a key you know you put in. This lesson finds out what makes a recipe good, by trying some.

What would you try?

Here are eight guests, a coat check with 16 hooks, and three recipes someone might reach for:

  • By length: the number of letters, mod 16. It's the quickest to work out in your head.
  • By sum: the letters' codes added up, mod 16: the recipe from the last lesson.
  • By times 31: start at 0; for each letter, multiply what you have by 31, add the letter's code, and keep the remainder mod 16. A colleague swears by it.

The code runs all three and counts how many different hooks each one uses:

string[] names = { "Amy", "May", "Maya", "Leo", "Priya", "Zoe", "Noah", "Eli" };
int hooks = 16;

int ByLength(string name)
{
    return name.Length % hooks;
}

int BySum(string name)
{
    int total = 0;
    foreach (char letter in name)
    {
        total += letter;
    }
    return total % hooks;
}

int ByTimes31(string name)
{
    int hash = 0;
    foreach (char letter in name)
    {
        hash = (hash * 31 + letter) % hooks;
    }
    return hash;
}

void Show(string recipe, Func<string, int> hookFor)
{
    bool[] used = new bool[hooks];
    List<string> parts = new List<string>();
    int different = 0;
    foreach (string name in names)
    {
        int hook = hookFor(name);
        parts.Add(name + " " + hook);
        if (!used[hook])
        {
            used[hook] = true;
            different++;
        }
    }
    Console.WriteLine(recipe + ": " + string.Join(", ", parts) + " (" + different + " different hooks)");
}

Show("By length", ByLength);
Show("By sum", BySum);
Show("By times 31", ByTimes31);
By length: Amy 3, May 3, Maya 4, Leo 3, Priya 5, Zoe 3, Noah 4, Eli 3 (3 different hooks)
By sum: Amy 7, May 7, Maya 8, Leo 0, Priya 5, Zoe 14, Noah 6, Eli 10 (7 different hooks)
By times 31: Amy 13, May 5, Maya 12, Leo 6, Priya 15, Zoe 0, Noah 8, Eli 2 (8 different hooks)
String[] names = { "Amy", "May", "Maya", "Leo", "Priya", "Zoe", "Noah", "Eli" };
int hooks = 16;

int byLength(String name) {
    return name.length() % hooks;
}

int bySum(String name) {
    int total = 0;
    for (char letter : name.toCharArray()) {
        total += letter;
    }
    return total % hooks;
}

int byTimes31(String name) {
    int hash = 0;
    for (char letter : name.toCharArray()) {
        hash = (hash * 31 + letter) % hooks;
    }
    return hash;
}

void show(String recipe, Function<String, Integer> hookFor) {
    boolean[] used = new boolean[hooks];
    List<String> parts = new ArrayList<>();
    int different = 0;
    for (String name : names) {
        int hook = hookFor.apply(name);
        parts.add(name + " " + hook);
        if (!used[hook]) {
            used[hook] = true;
            different++;
        }
    }
    IO.println(recipe + ": " + String.join(", ", parts) + " (" + different + " different hooks)");
}

void main() {
    show("By length", this::byLength);
    show("By sum", this::bySum);
    show("By times 31", this::byTimes31);
}
By length: Amy 3, May 3, Maya 4, Leo 3, Priya 5, Zoe 3, Noah 4, Eli 3 (3 different hooks)
By sum: Amy 7, May 7, Maya 8, Leo 0, Priya 5, Zoe 14, Noah 6, Eli 10 (7 different hooks)
By times 31: Amy 13, May 5, Maya 12, Leo 6, Priya 15, Zoe 0, Noah 8, Eli 2 (8 different hooks)
names = ["Amy", "May", "Maya", "Leo", "Priya", "Zoe", "Noah", "Eli"]
hooks = 16


def by_length(name):
    return len(name) % hooks


def by_sum(name):
    total = 0
    for letter in name:
        total += ord(letter)
    return total % hooks


def by_times_31(name):
    hash_value = 0
    for letter in name:
        hash_value = (hash_value * 31 + ord(letter)) % hooks
    return hash_value


def show(recipe, hook_for):
    used = [False] * hooks
    parts = []
    different = 0
    for name in names:
        hook = hook_for(name)
        parts.append(f"{name} {hook}")
        if not used[hook]:
            used[hook] = True
            different += 1
    print(f"{recipe}: {', '.join(parts)} ({different} different hooks)")


show("By length", by_length)
show("By sum", by_sum)
show("By times 31", by_times_31)
By length: Amy 3, May 3, Maya 4, Leo 3, Priya 5, Zoe 3, Noah 4, Eli 3 (3 different hooks)
By sum: Amy 7, May 7, Maya 8, Leo 0, Priya 5, Zoe 14, Noah 6, Eli 10 (7 different hooks)
By times 31: Amy 13, May 5, Maya 12, Leo 6, Priya 15, Zoe 0, Noah 8, Eli 2 (8 different hooks)
const names = ["Amy", "May", "Maya", "Leo", "Priya", "Zoe", "Noah", "Eli"];
const hooks = 16;

function byLength(name) {
  return name.length % hooks;
}

function bySum(name) {
  let total = 0;
  for (const letter of name) {
    total += letter.charCodeAt(0);
  }
  return total % hooks;
}

function byTimes31(name) {
  let hash = 0;
  for (const letter of name) {
    hash = (hash * 31 + letter.charCodeAt(0)) % hooks;
  }
  return hash;
}

function show(recipe, hookFor) {
  const used = new Array(hooks).fill(false);
  const parts = [];
  let different = 0;
  for (const name of names) {
    const hook = hookFor(name);
    parts.push(`${name} ${hook}`);
    if (!used[hook]) {
      used[hook] = true;
      different++;
    }
  }
  console.log(`${recipe}: ${parts.join(", ")} (${different} different hooks)`);
}

show("By length", byLength);
show("By sum", bySum);
show("By times 31", byTimes31);
By length: Amy 3, May 3, Maya 4, Leo 3, Priya 5, Zoe 3, Noah 4, Eli 3 (3 different hooks)
By sum: Amy 7, May 7, Maya 8, Leo 0, Priya 5, Zoe 14, Noah 6, Eli 10 (7 different hooks)
By times 31: Amy 13, May 5, Maya 12, Leo 6, Priya 15, Zoe 0, Noah 8, Eli 2 (8 different hooks)
const names: string[] = ["Amy", "May", "Maya", "Leo", "Priya", "Zoe", "Noah", "Eli"];
const hooks = 16;

function byLength(name: string): number {
  return name.length % hooks;
}

function bySum(name: string): number {
  let total = 0;
  for (const letter of name) {
    total += letter.charCodeAt(0);
  }
  return total % hooks;
}

function byTimes31(name: string): number {
  let hash = 0;
  for (const letter of name) {
    hash = (hash * 31 + letter.charCodeAt(0)) % hooks;
  }
  return hash;
}

function show(recipe: string, hookFor: (name: string) => number): void {
  const used: boolean[] = new Array(hooks).fill(false);
  const parts: string[] = [];
  let different = 0;
  for (const name of names) {
    const hook = hookFor(name);
    parts.push(`${name} ${hook}`);
    if (!used[hook]) {
      used[hook] = true;
      different++;
    }
  }
  console.log(`${recipe}: ${parts.join(", ")} (${different} different hooks)`);
}

show("By length", byLength);
show("By sum", bySum);
show("By times 31", byTimes31);
By length: Amy 3, May 3, Maya 4, Leo 3, Priya 5, Zoe 3, Noah 4, Eli 3 (3 different hooks)
By sum: Amy 7, May 7, Maya 8, Leo 0, Priya 5, Zoe 14, Noah 6, Eli 10 (7 different hooks)
By times 31: Amy 13, May 5, Maya 12, Leo 6, Priya 15, Zoe 0, Noah 8, Eli 2 (8 different hooks)

The times-31 recipe keeps the remainder after every letter, not only at the end. That gives the same hook as working out the whole number first, and it keeps the number small. Without it, C# and Java would overflow their int after a few letters, JavaScript would start losing digits, and only Python's int, which never overflows, would get it right.

Three rows of 16 numbered hooks, one row per recipe, with the eight names hung on them: by length, five names crowd onto hook 3 and only 3 hooks are used; by sum, Amy and May share hook 7 and 7 hooks are used; by times 31, every name has a hook of its own

And one more, without code: a random hook for every coat. It would spread the coats beautifully. Hold that thought.

What went wrong, and what went right

  • By length throws away almost everything about the name. Most names are 3 to 5 letters long, so they crowd onto hooks 3, 4 and 5, and 13 hooks stay empty. Two keys that land on the same bucket are a collision, and this recipe makes them by the handful.
  • By sum uses every letter but ignores their order. "Amy" and "May" are the same three letters, so they add up to the same total and collide on hook 7. Any two names that are anagrams of each other always collide.
  • A random hook spreads the coats perfectly, and loses every one of them. At 11 p.m. the recipe gives Maya a new random hook, not the one her coat is on.
  • By times 31 makes the position of every letter count. The first letter gets multiplied by 31 once for every letter after it, so swapping two letters changes the result. "Amy" goes to hook 13 and "May" to hook 5.

Three things a good recipe does

Put the four tries side by side, and the rules for a good recipe fall out of them:

  1. The same key always gets the same number. The random hook breaks this one, and a broken hash function loses things. A recipe can't use the time, a random number, or anything else that changes. In your textbook this is called being deterministic.
  2. It's fast. The recipe runs on every put and every get, so it has to take a handful of steps, not a search of its own. All four tries pass this one.
  3. It spreads keys evenly over the buckets. By length and by sum break this one, and a crowded hook is a search again. The whole point is that each hook holds about one coat.

The first two are easy. The third is where recipes differ, and where times 31 wins.

Why 31? Multiplying by an odd number spreads the totals out well, and multiplying by 31 is quick for a computer to do. It's also Java's choice: String.hashCode() is this same recipe, without the remainder.

Try it. Add "Lia" and "Ali" to the names: the same three letters again. By sum, both join Noah on hook 6. By times 31, Lia gets hook 4 and Ali hook 14, two hooks nobody else is using. No recipe avoids every collision (with more names than hooks, some must share), and the next lesson shows how a hash table copes when they do.

Your language's hash functions

You'll rarely write a hash function for text: each language has its own, and its dictionaries use it.

  • C#: every object has GetHashCode(), which gives its hash code, a whole number.
  • Java: every object has hashCode().
  • Python: the built-in hash(value).
  • JavaScript and TypeScript: no hash function you can call. Map and Set hash their keys inside, where you can't see.

A hash code is the full number a hash function gives. The table then keeps its remainder to pick a bucket, exactly as the coat check did.

Where the languages differ: in C# and Python, a string's hash code changes every time the program starts, while Java's stays the same. C# and Python do that on purpose: an attacker who knows the recipe could send a web server thousands of keys that all collide, and slow it to a crawl. Within one run, the same string always gets the same number, which is all a hash table needs. So never save a hash code to a file or a database, expecting it to match the next time.

In your textbook: the hash functions that store passwords (such as SHA-256) are a different family. They're built to be slow and impossible to run backward. The ones in this lesson are built to be fast, and they only need to spread keys out.

Check yourself

2 questions to try on the lesson page.

So what

A hash table's speed comes from its recipe. When your own objects become keys, you'll be the one choosing what goes into their hash code, and now you know the three things it has to get right.

Key terms

Cheat sheets