Hash table in Java: how HashMap works

Problem

The price cache slows down

The product page reads its price from a cache: an SKU → price table that the program keeps in memory. Someone wrote their own PriceTable, with a hash function that is "fast": only the first letter of the SKU.

PriceTable cache = new PriceTable(key -> key.charAt(0));

With 20 products in the test it flies. With the real catalog the page crawls, and the profiler points at get. With 1000 products, each written and read once, the table makes 1,000,000 key comparisons: a thousand per product. A hash table should make one or two.

Every SKU starts with "S". What is happening inside?

The idea

Buckets, hash and the bucket number

In the lesson "Hash codes and hash functions" you saw the table from the outside. Inside it is three things:

an array of buckets;
a hash function that turns the key into an integer;
the bucket number = hash % number of buckets. So every key has exactly one place where you look for it.

Two keys with the same bucket number are a collision. Here collisions live in a chain: every bucket is the start of a linked list of key → value pairs.

String[] keys = { "Boris", "Yana", "Ivan", "Emil" };
int buckets = 8;
for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.floorMod(hash, buckets);
    System.out.println(key + " -> " + hash + " -> bucket " + index);
}

Step by step, in words

Four keys and eight empty buckets, numbered 0 to 7.
"Boris".hashCode() is 64372111. The remainder when divided by 8 is 7: that is the bucket.
"Yana" gives 2748123, bucket 3.
"Ivan" gives 2291258, bucket 2.
"Emil" is also in bucket 3: a collision. The two keys are in one bucket: "Emil" hangs after "Yana" like a chain.
Looking up "Emil": the same number, the same bucket 3. equals with "Yana": no. With "Emil": yes.

get computes the bucket and walks only its chain. If the chains are short, that is O(1), however many keys there are.

See it

Your own table

The hash function for an SKU is the same as Java's hashCode of a string: 31 · h + char for every character. At the end the sign is dropped, so the number is not negative:

static int skuHash(String key) {
    int h = 0;
    for (int i = 0; i < key.length(); i++) {
        h = 31 * h + key.charAt(i);
    }
    return h & 0x7fffffff;
}

A pair is a node with a key, a price and an arrow to the next one in the chain:

class Entry {
    final String key;
    double price;
    Entry next;

    Entry(String key, double price, Entry next) {
        this.key = key;
        this.price = price;
        this.next = next;
    }
}

The table gets its hash function from outside, so you can compare two of them. compares counts the key comparisons:

class PriceTable {
    private final ToIntFunction<String> hash;
    private Entry[] buckets = new Entry[4];
    private int size = 0;
    long compares = 0;

    PriceTable(ToIntFunction<String> hash) {
        this.hash = hash;
    }

    int capacity() {
        return buckets.length;
    }

    private int index(String key) {
        return hash.applyAsInt(key) % buckets.length;
    }

    void put(String key, double price) {
        int i = index(key);
        for (Entry e = buckets[i]; e != null; e = e.next) {
            compares++;
            if (e.key.equals(key)) {
                e.price = price;
                return;
            }
        }
        buckets[i] = new Entry(key, price, buckets[i]);
        size++;
        if (size > buckets.length * 3 / 4) resize();
    }

    private void resize() {
        Entry[] fresh = new Entry[buckets.length * 2];
        for (Entry head : buckets) {
            for (Entry e = head; e != null; e = e.next) {
                int i = hash.applyAsInt(e.key) % fresh.length;
                fresh[i] = new Entry(e.key, e.price, fresh[i]);
            }
        }
        buckets = fresh;
    }

    Double get(String key) {
        int i = index(key);
        for (Entry e = buckets[i]; e != null; e = e.next) {
            compares++;
            if (e.key.equals(key)) return e.price;
        }
        return null;
    }
}

put walks the chain of the bucket. If the key is there, it changes the price. If not, it puts a new pair at the front of the chain: that needs no walk.
get walks the same chain and stops at the key.

Try it

Fill in

The bucket number:

return hash.applyAsInt(key) % ;

The idea

Load factor and growing

The more pairs, the longer the chains. The ratio pairs / buckets is called the load factor. Here, once it goes above 3/4, the table makes twice as many buckets.

The buckets are not copied one to one. The bucket number is hash % number of buckets, and that number has changed. So resize walks every pair and computes its bucket again: this is rehashing. Doubling from 4 to 8, a key from bucket b goes to b or to b + 4, and the chains split.

private int index(String key) {
    return hash.applyAsInt(key) % buckets.length;
}

void put(String key, double price) {
    int i = index(key);
    for (Entry e = buckets[i]; e != null; e = e.next) {
        compares++;
        if (e.key.equals(key)) {
            e.price = price;
            return;
        }
    }
    buckets[i] = new Entry(key, price, buckets[i]);
    size++;
    if (size > buckets.length * 3 / 4) resize();
}

private void resize() {
    Entry[] fresh = new Entry[buckets.length * 2];
    for (Entry head : buckets) {
        for (Entry e = head; e != null; e = e.next) {
            int i = hash.applyAsInt(e.key) % fresh.length;
            fresh[i] = new Entry(e.key, e.price, fresh[i]);
        }
    }
    buckets = fresh;
}

Step by step, in words

A price cache with 4 buckets. The bucket of a key is its hash % 4.
SKU-1003: 1091696434 % 4 = 2. SKU-1001: % 4 = 0. Empty buckets: no comparisons.
SKU-1007 also lands in bucket 2: a collision. put compares it with SKU-1003 (not the same key) and puts it at the front of the chain.
SKU-1005 joins SKU-1001 in bucket 0. Now there are 4 pairs, more than 3/4 of 4 buckets: the chains are getting long.
resize makes 8 buckets. Every key is counted again with % 8: it stays at its number or moves 4 up.
The new table: every chain is one pair long, so a get makes one comparison. Resizing costs n, but it happens rarely.

PriceTable cache = new PriceTable(Main::skuHash);
cache.put("SKU-1003", 24.9);
cache.put("SKU-1001", 12.5);
cache.put("SKU-1007", 8.99);
cache.printBuckets();
System.out.println("---");
cache.put("SKU-1005", 45.5);
cache.printBuckets();

0: SKU-1001
1:
2: SKU-1007 SKU-1003
3:
---
0: SKU-1001
1:
2: SKU-1003
3:
4: SKU-1005
5:
6: SKU-1007
7:

Growing costs as much as the number of pairs. But it happens rarely: at 4, 8, 16… pairs, like the growing array in amortized complexity. On average put stays O(1).

Try it

How many buckets?

The table starts with 4 buckets. Seven products go in one after another:

PriceTable cache = new PriceTable(Main::skuHash);
StringBuilder caps = new StringBuilder();
for (int n = 2001; n <= 2007; n++) {
    cache.put("SKU-" + n, 10);
    caps.append(cache.capacity()).append(" ");
}
System.out.println(caps.toString().trim());

Answer

4 4 4 4 8 8 8

4 4 4 8 8 8 16

4 8 16 16 16 16 16

The idea

A bad hash: the table becomes a list

Back to the cache. The "first letter" hash gives 83 (the code of "S") for every SKU. 83 % 4, 83 % 8, 83 % 1024: with any number of buckets the number is the same. All pairs are in one chain, and the table is a linked list where every put and every get walks through all of them.

Growing does not help: it splits chains only when the keys have different hashes. A hash function must depend on the whole key and scatter close keys (SKU-10000, SKU-10001) far from each other.

static long compares(PriceTable cache, int n) {
    for (int i = 0; i < n; i++) cache.put("SKU-" + (10000 + i), 1 + i);
    for (int i = 0; i < n; i++) cache.get("SKU-" + (10000 + i));
    return cache.compares;
}

System.out.println("first letter: " + compares(new PriceTable(key -> key.charAt(0)), 1000));
System.out.println("whole SKU: " + compares(new PriceTable(Main::skuHash), 1000));

first letter: 1000000
whole SKU: 2593

Run both tables in the browser:

Hash of the whole SKU O(n)
Hash of the first letter O(n²)

Algorithm	n = 10	n = 1,000	n = 100,000
Hash of the whole SKU	10	2,593	211,990
Hash of the first letter	100	1,000,000	≈ 10,000,000,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

With 1000 products the lazy hash makes 1,000,000 comparisons, and the hash of the whole SKU makes 2593: under three per product. The lazy one is O(n) per operation and O(n²) in total: n products, each written and read once, make exactly n² comparisons.

More precisely, if you are curious

Open addressing (linear probing). Instead of chains, every pair lives in the array itself. If slot hash % n is taken, you try the next one, then the one after, until you find a free slot or the key. get follows the same path and stops at an empty slot. The upside is that everything is in one array and the processor reads it in order. The downsides: taken slots gather into clusters and every cluster grows faster and faster, so the table must stay emptier (it grows already at about half or 2/3). Removing cannot just clear the slot, because that would cut the path to the keys after it: it leaves a "deleted" mark.

What the languages do:

Java HashMap: chains. The number of buckets is a power of 2 (16 at first), load factor 0.75. The high bits are mixed into the hash (h ^ (h >>> 16)), because with a power-of-2 mask only the low bits would count otherwise. A chain with more than 8 pairs becomes a red-black tree if there are at least 64 buckets (otherwise the table grows first). So even with many collisions a lookup is O(log n), not O(n).
C# Dictionary<TKey, TValue>: also chains, but in arrays: _buckets holds the number of the first pair, and the pairs in _entries have a next index. The number of buckets is a prime (3, 7, 17, 37, 89…), and it grows when the array of pairs is full. There is no tree like in Java. Against deliberate collisions it relies on string hashes that differ on every run.
Python dict: open addressing, but not linear probing: the next slot is computed by a formula that also uses the high bits of the hash. The table is a power of 2 and grows once it is more than 2/3 full. The pairs live in a separate dense array in insertion order, and the table holds only indexes into it. That is why dict keeps insertion order (guaranteed since Python 3.7).
JavaScript Map: the specification requires iteration in insertion order and lookups that are on average better than linear, but does not say how. V8 uses an ordered hash table: buckets with chains, and the pairs live in an array in insertion order. JavaScript gives no hash of your own for objects: an object key is compared by reference.

Try it

Find the bug

Someone rewrote resize. The four products go in, but two of them are later "missing":

private void resize() {
    Entry[] fresh = new Entry[buckets.length * 2];
    for (Entry head : buckets) {
        for (Entry e = head; e != null; e = e.next) {
            int i = hash.applyAsInt(e.key) % buckets.length;
            fresh[i] = new Entry(e.key, e.price, fresh[i]);
        }
    }
    buckets = fresh;
}

PriceTable cache = new PriceTable(Main::skuHash);
cache.put("SKU-1003", 24.9);
cache.put("SKU-1001", 12.5);
cache.put("SKU-1007", 8.99);
cache.put("SKU-1005", 45.5);
Double p1003 = cache.get("SKU-1003");
System.out.println("SKU-1003: " + (p1003 == null ? "none" : p1003));
Double p1001 = cache.get("SKU-1001");
System.out.println("SKU-1001: " + (p1001 == null ? "none" : p1001));
Double p1007 = cache.get("SKU-1007");
System.out.println("SKU-1007: " + (p1007 == null ? "none" : p1007));
Double p1005 = cache.get("SKU-1005");
System.out.println("SKU-1005: " + (p1005 == null ? "none" : p1005));

SKU-1003: 24.9
SKU-1001: 12.5
SKU-1007: none
SKU-1005: none

Which line has the bug?

Pick the line with the bug.

Exercise

A product stops being sold

Solve this one in your own editor.

Removing from the cache. Add a method remove(key) to PriceTable that removes the pair and returns whether there was one. Be careful: the pair may be first in the chain (then the bucket points to the next one) or in the middle (then the previous pair points to the next one). Put SKU-1001, SKU-1005, SKU-1009 and SKU-1012 with prices €10.5, €11.5, €12.5 and €13.5; after growing to 8 buckets three of them are in bucket 0, and SKU-1009 is in the middle of the chain. Remove SKU-1009 and read all four:

SKU-1001: 10.5
SKU-1005: 11.5
SKU-1009: none
SKU-1012: 13.5
products: 3

More tasks

Linear probing. Write a ProbeTable without chains: when a slot is taken, try the next one. Grow when the table is half full. How many comparisons does it make with 1000 SKUs?
Shrinking. After a sale the cache is left with 10 products and 4096 buckets. When would you shrink the table?
A better lazy hash. The hash "sum of the character codes" looks at the whole key. Try it with SKU-10000 to SKU-10999. Why are there still many collisions? (Hint: SKU-10019 and SKU-10091.)

Test

Check yourself

1. The table has 8 buckets. A key hashes to 1091696436. Which bucket is it in?Bucket 0Bucket 4Bucket 6

2. Why does growing the table compute every key again, instead of just copying the buckets?It does not: the buckets are copiedBecause the hash of the key changesBecause the bucket number is hash % number of buckets, and the number of buckets has changed

3. The hash function returns the first letter of the SKU, and every SKU starts with "S". What does get cost with n products?O(1): it is a hash tableO(n): they are all in one bucket and get walks the whole chainO(log n)

4. What is true about the Python dict?It keeps collisions in chains like HashMapIt looks for another free slot in the same array (open addressing) and keeps insertion orderIt sorts the keys alphabetically

Hash table

Cookies