Hash tables and dictionaries explained

A hash table stores key and value pairs in an array of slots called buckets. A hash function turns each key into a bucket number, so to find a value you hash its key and go straight to that bucket instead of searching. That makes looking up, adding and deleting take O(1) time on average, however many items there are.

A dictionary (also called a map or associative array) is the same idea seen from the outside: a collection of key and value pairs where you get each value by its key. Python's dict, JavaScript's Map and Java's HashMap are all built on hash tables.

How a hash table works

Say we store students' ages in a table with 8 buckets, numbered 0 to 7. Our hash function adds up the letters of the name, with a = 1, b = 2 and so on to z = 26, then keeps the remainder after dividing by 8 (the "mod 8"):

To find Raj's age later, hash "Raj" again, get 5 and look in bucket 5. There is no scanning through the other names, which is why the time does not grow with the size of the table.

1. Insert: hash the key, then store the pair in that bucket.
2. Look up: hash the key, go to that bucket, and return the value stored with the key.
3. Delete: hash the key, go to that bucket and remove the pair.

Try one yourself. Add up the letter values of a name, find the remainder, then press Mark to check your bucket in the course:

Hash table collisions

Now add Eve: 5 + 22 + 5 = 32, and 32 mod 8 = 0. Bucket 0 already holds Leo. Two keys giving the same hash is a collision, and with more keys than buckets, collisions are certain. There are two main ways to handle them.

Chaining

Each bucket holds a short list. Eve is simply added to the list in bucket 0, after Leo. A lookup for Eve hashes to bucket 0 and checks the two names there. As long as the lists stay short, this is still very fast.

Open addressing and linear probing

Every bucket holds one item. If the bucket is full, the table works out another one, which the AQA A-level specification calls rehashing. The simplest method is linear probing: try the next bucket, then the next, wrapping round at the end. Eve would go in bucket 1. Lookups follow the same path, so a search for Eve checks bucket 0, finds Leo, moves on and finds Eve in bucket 1.

Load factor and resizing

The load factor is how full the table is:

Our table with 3 names in 8 buckets has a load factor of 3/8 = 0.375. As it rises, collisions become more common and lookups slow down. Real hash tables grow when the load factor passes a limit: Java's HashMap uses 0.75 by default. Growing means making a bigger array and re-inserting every item, because each key's bucket depends on the number of buckets.

What makes a good hash function

• Deterministic: the same key always gives the same hash, or you could never find it again.
• Fast: it runs on every insert and lookup.
• Spreads keys evenly: similar keys should land far apart. Our letter-sum function is weak here: any anagrams, such as "Amy" and "May", always collide.

This is also why dictionary keys must not change. Python only allows hashable keys, such as strings, numbers and tuples; a list cannot be a key, because changing it would change its hash and lose the value.

Time complexity

The worst case happens when every key lands in the same bucket, so a lookup has to check them all, like a list. A good hash function and resizing make that very unlikely. Hash tables beat binary search trees for lookups by key, but they keep no order, so finding the smallest key or listing keys in sorted order needs a tree or a sort.

Dictionaries in Python and JavaScript

You will rarely write a hash table yourself. Here is the built-in version in JavaScript, which you can run in the Code Editor:

const phone = new Map();
phone.set("Mia", "07700 900123");
phone.set("Leo", "07700 900456");

console.log(phone.get("Mia"));   // 07700 900123
console.log(phone.has("Raj"));   // false
phone.delete("Leo");
console.log(phone.size);         // 1

In Python the same thing is phone = {"Mia": "07700 900123"}, read with phone["Mia"]. Both keep keys in the order you added them, which Python has guaranteed since version 3.7.

Building one yourself

This small hash table uses the letter-sum function and chaining, so you can watch Eve and Leo share bucket 0:

class HashTable {
  constructor(size = 8) {
    this.buckets = Array.from({ length: size }, () => []);
  }
  hash(key) {
    let sum = 0;
    for (const ch of key.toLowerCase()) sum += ch.charCodeAt(0) - 96;  // a = 1, b = 2, ...
    return sum % this.buckets.length;
  }
  set(key, value) {
    const bucket = this.buckets[this.hash(key)];
    const pair = bucket.find(([k]) => k === key);
    if (pair) pair[1] = value;
    else bucket.push([key, value]);
  }
  get(key) {
    const pair = this.buckets[this.hash(key)].find(([k]) => k === key);
    return pair ? pair[1] : undefined;
  }
}

const ages = new HashTable(8);
ages.set("Mia", 15);
ages.set("Leo", 17);
ages.set("Eve", 16);
console.log(ages.hash("Leo"), ages.hash("Eve"), ages.get("Eve"));   // 0 0 16

Common mistakes

• Saying lookups are always O(1). That is the average. The worst case is O(n).
• Forgetting the original key. A bucket must store the key with the value, or after a collision you cannot tell which value is which.
• Probing the wrong way on lookup. A lookup must follow the same probing steps as the insert, and keep going until it finds the key or an empty bucket.
• Expecting sorted output. Hash tables keep no order of size. Python and JavaScript only keep the order you inserted keys.

Read next

Computer Science · Programming and algorithmsConditional statements in programming: if, else and logicHow conditional statements in programming work: if, elif and else, comparison operators, AND, OR and NOT, truth tables, with Python and JavaScript code.