Hashing & Prefix Sums: guided lesson

the story

Hash table

Every tool here exists because something was too slow or broke without it. Here is what.

1953 · Hans Peter Luhn; Gene Amdahl, Elaine M. McGraw (née Boehme), Nathaniel Rochester, Arthur Samuel (IBM); Arnold Dumey; W. Wesley Peterson

In January 1953 Hans Peter Luhn wrote an internal IBM memo that put keys into numbered buckets and chained the overflow — one of the first uses of linked lists. At about the same time, Gene Amdahl, Elaine McGraw (née Boehme), Nathaniel Rochester and Arthur Samuel used hashing in an assembler for the IBM 701; Amdahl is credited with open addressing with linear probing. Arnold Dumey gave the first published description in 1956, and W. Wesley Peterson's 1957 paper studied open addressing in depth. Knuth's The Art of Computer Programming, Vol. 3 (§6.4), tells the full story.

the problem it solved

Finding a record by its key in about one step, instead of scanning everything or keeping the data sorted.

why it matters: without it

Every "have I seen this?" or "what's stored under this key?" would cost O(n), or O(log n) with sorted structures — caches, compilers and deduplication would all slow down by orders of magnitude.

sources: IEEE Spectrum — Hans Peter Luhn and the Birth of the Hashing Algorithm (2018) ↗ · Peterson — Addressing for Random-Access Storage (IBM J. Res. Dev., 1957) ↗ · Knuth — The Art of Computer Programming, Vol. 3, §6.4 Hashing (history) ↗ · Wikipedia — Hash table: History (Luhn's memo, the IBM 701 assembler, Dumey, Peterson) ↗ · Pro Git — Git Internals: Git Objects (objects stored by hash under .git/objects) ↗

also in this chapter: Java's HashMap (resize + treeify) · Prefix sums (1D) · 2D prefix sums (summed-area table) · Prefix sum + HashMap

the idea

The idea in 30 seconds

A hash function turns a key into an array index, so finding a key is one jump instead of a scan: O(1) on average.

A prefix sum array stores running totals once, so the sum of any range is prefix[r+1] − prefix[l]: O(1) per question.

Together they solve "count subarrays with sum k" in one pass: remember every prefix sum you've seen in a HashMap.

picture this

Hashing is how Git stores your files: it hashes each object's content, and the first two hex digits of that hash pick one of 256 folders under .git/objects/. Finding an object is one jump into one small folder, never a search through all of them. A prefix sum is a cricket scorecard's running total: runs scored between over 10 and over 20 = total after 20 − total after 10.

watch it

HashMap.put in 3D: hash, bucket, chain

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

HashMap.put in 3D: hash, bucket, chain

Each key is hashed to a bucket. Collisions chain up; equal keys overwrite instead of duplicating.

loading simulation…

javajava.util.*

1class ChainedHashMap<K, V> {2    private static final double LOAD_FACTOR = 0.75;3 4    private static class Node<K, V> {5        final K key;6        V value;7        Node<K, V> next;8 9        Node(K key, V value) {10            this.key = key;11            this.value = value;12        }13    }14 15    private Node<K, V>[] table;16    private int size = 0;17 18    ChainedHashMap(int initialCapacity) {19        table = newTable(initialCapacity);20    }21 22    /** hashCode → bucket index. The mask drops the sign bit so the index is never negative. */23    static int indexFor(Object key, int capacity) {24        return (key.hashCode() & 0x7fffffff) % capacity;25    }26 27    public void put(K key, V value) {28        int index = indexFor(key, table.length);29        for (Node<K, V> node = table[index]; node != null; node = node.next) {30            if (node.key.equals(key)) {31                node.value = value; // same key → overwrite, size unchanged32                return;33            }34        }35        append(index, new Node<>(key, value)); // new key → add to the chain36        size++;37        if (size > table.length * LOAD_FACTOR) resize(); // too full?38    }39 40    public V get(K key) {41        for (Node<K, V> node = table[indexFor(key, table.length)]; node != null; node = node.next) {42            if (node.key.equals(key)) return node.value;43        }44        return null;45    }46 47    /** Double the table and move every entry to its bucket in the new table. */48    private void resize() {49        Node<K, V>[] old = table;50        table = newTable(old.length * 2);51        for (Node<K, V> head : old) {52            for (Node<K, V> node = head; node != null; node = node.next) {53                append(indexFor(node.key, table.length), new Node<>(node.key, node.value));54            }55        }56    }57 58    private void append(int index, Node<K, V> fresh) {59        if (table[index] == null) {60            table[index] = fresh;61            return;62        }63        Node<K, V> tail = table[index];64        while (tail.next != null) tail = tail.next;65        tail.next = fresh;66    }67 68    public int size() { return size; }69 70    public int capacity() { return table.length; }71 72    @SuppressWarnings("unchecked")73    private static <K, V> Node<K, V>[] newTable(int capacity) {74        return (Node<K, V>[]) new Node[capacity];75    }76}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

Load factor 0.75: resize and rehash

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

Load factor 0.75: resize and rehash

Start small and watch the table double. Every entry moves, because its bucket depends on the capacity.

loading simulation…

javajava.util.*

1class ChainedHashMap<K, V> {2    private static final double LOAD_FACTOR = 0.75;3 4    private static class Node<K, V> {5        final K key;6        V value;7        Node<K, V> next;8 9        Node(K key, V value) {10            this.key = key;11            this.value = value;12        }13    }14 15    private Node<K, V>[] table;16    private int size = 0;17 18    ChainedHashMap(int initialCapacity) {19        table = newTable(initialCapacity);20    }21 22    /** hashCode → bucket index. The mask drops the sign bit so the index is never negative. */23    static int indexFor(Object key, int capacity) {24        return (key.hashCode() & 0x7fffffff) % capacity;25    }26 27    public void put(K key, V value) {28        int index = indexFor(key, table.length);29        for (Node<K, V> node = table[index]; node != null; node = node.next) {30            if (node.key.equals(key)) {31                node.value = value; // same key → overwrite, size unchanged32                return;33            }34        }35        append(index, new Node<>(key, value)); // new key → add to the chain36        size++;37        if (size > table.length * LOAD_FACTOR) resize(); // too full?38    }39 40    public V get(K key) {41        for (Node<K, V> node = table[indexFor(key, table.length)]; node != null; node = node.next) {42            if (node.key.equals(key)) return node.value;43        }44        return null;45    }46 47    /** Double the table and move every entry to its bucket in the new table. */48    private void resize() {49        Node<K, V>[] old = table;50        table = newTable(old.length * 2);51        for (Node<K, V> head : old) {52            for (Node<K, V> node = head; node != null; node = node.next) {53                append(indexFor(node.key, table.length), new Node<>(node.key, node.value));54            }55        }56    }57 58    private void append(int index, Node<K, V> fresh) {59        if (table[index] == null) {60            table[index] = fresh;61            return;62        }63        Node<K, V> tail = table[index];64        while (tail.next != null) tail = tail.next;65        tail.next = fresh;66    }67 68    public int size() { return size; }69 70    public int capacity() { return table.length; }71 72    @SuppressWarnings("unchecked")73    private static <K, V> Node<K, V>[] newTable(int capacity) {74        return (Node<K, V>[]) new Node[capacity];75    }76}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 9