Hash tables: maps, sets and load factor

A hash table stores keys in an ordinary array and works out where each key belongs from the key itself. A hash function turns the key into a number, and the remainder after dividing that number by the array’s length picks a slot, called a bucket. Storing a key and finding it again both go straight to that bucket, so on average neither depends on how many keys the table holds. A set is a hash table of keys alone; a map, or dictionary, keeps a value next to each key. The load factor says how full the table is: the number of keys divided by the number of buckets. Keep it bounded, use a hash function that spreads the keys, and insert, find and delete take O(1) time on average, though a bad hash can push each of them to O(n). This lesson builds the idea from a plain array, runs it on twelve city names and shows where it breaks.

Start from an array: direct addressing

Suppose the keys are small whole numbers, such as the berth numbers 1 to 72 of a railway coach. Then the key can be the index itself: passenger[37] is whoever sits in berth 37. This is direct addressing. Every operation is one array access, O(1) in the worst case and not only on average, and no two keys can ever share a slot.

The price is memory. A direct-address array needs a slot for every key that could occur, not just for the keys that do. Berth numbers need 73 slots. Six-digit codes from 100000 to 999999 need a million, and the run below compares that with a hash set that stores only the codes it has actually seen:

"""Direct addressing (the key is the array index) against a hash set, for six-digit codes 100000 to 999999.

The bytearray has one byte for every possible code, so its size never changes. The set's memory grows with the
number of codes stored. tracemalloc counts the bytes each container allocates; the code numbers themselves are made
before it starts, so only the containers are counted.
"""
import random
import tracemalloc


def traced(build):
    tracemalloc.start()
    built = build()
    size = tracemalloc.get_traced_memory()[0]
    tracemalloc.stop()
    return built, size


seen, array_bytes = traced(lambda: bytearray(1_000_000))
for code in (400001, 560034, 110001):
    seen[code] = 1
print(f"direct address: seen[560034] = {seen[560034]}, seen[560035] = {seen[560035]}, {array_bytes:,} bytes always")

rng = random.Random(6)
codes = rng.sample(range(100_000, 1_000_000), 200_000)
print("distinct codes   set bytes   bytes per code   smaller")
for n in (5, 1_000, 10_000, 20_000, 200_000):
    stored, set_bytes = traced(lambda: set(codes[:n]))
    smaller = "set" if set_bytes < array_bytes else "bytearray"
    print(f"{n:>14,}  {set_bytes:>10,}  {set_bytes / n:>15.1f}   {smaller}")

direct address: seen[560034] = 1, seen[560035] = 0, 1,000,057 bytes always
distinct codes   set bytes   bytes per code   smaller
             5         728            145.6   set
         1,000      32,984             33.0   set
        10,000     524,504             52.5   set
        20,000   2,097,368            104.9   bytearray
       200,000   8,388,824             41.9   bytearray

The bytearray costs the same 1,000,057 bytes whether it marks 3 codes or 900,000. The set grows with its contents: about 33 KB for 1,000 codes, half a megabyte for 10,000 and 2 MB for 20,000, where it has become the bigger of the two. Its cost per code jumps around because a set enlarges its table in big steps rather than one slot at a time. So direct addressing wins when the possible keys form a small, dense range, and it fails when the range is huge and sparse: ten-digit phone numbers or 64-bit user IDs would need billions of slots. Hashing keeps the array but makes its length depend on the number of keys stored instead of the number of keys possible.

Hashing: from any key to a bucket

Hashing replaces “the key is the index” with “the key decides the index”. A hash function accepts a key of any type, whether a name, a tuple or a 64-bit ID, and returns a whole number. The table keeps m buckets and puts the key in bucket hash mod m, so a table of 16 buckets needs 16 slots whatever the keys look like.

The program below builds such a table by hand for twelve city names, using FNV-1a, a small published hash function for text (RFC 9923), first with 16 buckets and then with 32:

"""Twelve city names in a hash table of 16 buckets, then the same names in 32 buckets.

The hash is 32-bit FNV-1a over each name's UTF-8 bytes, written out so that every computer and every run puts the
names in the same buckets. Python's own hash() of a string is salted with a random value in each process, so it would
place them differently every time the program starts.
"""


def fnv1a_32(text):
    h = 0x811C9DC5
    for byte in text.encode("utf-8"):
        h ^= byte
        h = (h * 0x01000193) & 0xFFFFFFFF
    return h


cities = ["Mumbai", "Delhi", "Bengaluru", "Chennai", "Kolkata", "Pune",
          "Jaipur", "Lucknow", "Kochi", "Indore", "Patna", "Surat"]


def place(names, buckets):
    table = [[] for _ in range(buckets)]
    for name in names:
        table[fnv1a_32(name) % buckets].append(name)
    return table


for buckets in (16, 32):
    table = place(cities, buckets)
    print(f"{buckets} buckets, {len(cities)} names, load factor {len(cities) / buckets:.3f}")
    for i, names in enumerate(table):
        if names:
            print(f"  bucket {i:2}: {', '.join(names)}")
    empty = sum(1 for b in table if not b)
    print(f"  empty buckets: {empty}, longest bucket: {max(len(b) for b in table)}")

moved = [name for name in cities if fnv1a_32(name) % 32 != fnv1a_32(name) % 16]
print(f"moved when the table doubled: {len(moved)} of {len(cities)}, each from bucket i to i + 16")

16 buckets, 12 names, load factor 0.750
  bucket  2: Mumbai, Indore
  bucket  3: Chennai
  bucket  6: Kolkata, Jaipur
  bucket  7: Kochi, Patna
  bucket  8: Bengaluru, Lucknow, Surat
  bucket 13: Delhi
  bucket 15: Pune
  empty buckets: 9, longest bucket: 3
32 buckets, 12 names, load factor 0.375
  bucket  2: Mumbai, Indore
  bucket  6: Kolkata
  bucket  7: Kochi, Patna
  bucket  8: Bengaluru, Lucknow, Surat
  bucket 19: Chennai
  bucket 22: Jaipur
  bucket 29: Delhi
  bucket 31: Pune
  empty buckets: 24, longest bucket: 3
moved when the table doubled: 4 of 12, each from bucket i to i + 16

Three things stand out in the output.

1. Collisions are normal. Twelve names in 16 buckets left 9 buckets empty while Bengaluru, Lucknow and Surat share bucket 8. Two different keys in the same bucket make a collision, and with a dozen keys spread over a few dozen buckets some are almost certain. The next lesson is about handling them.
2. The load factor fell from 0.750 to 0.375 when the table doubled. It is also the average number of keys per bucket.
3. Doubling moves only some keys. A key in bucket i of 16 lands in bucket i or i + 16 of 32, decided by one more bit of its hash. Four names moved; the three in bucket 8 stayed together because their hashes agree in that bit as well.

Python’s built-in hash() would work here too, but its value for a string is salted with a random number chosen when each Python process starts, so the buckets would change from run to run. The example uses FNV-1a so that it prints the same buckets on every computer.

Maps and sets are one structure

A set and a map are the same table with different contents. A set stores keys and answers “is this key here?”. A map stores a value beside each key and answers “what is stored under this key?”. Both offer three core operations, and all three start by hashing the key to find its bucket:

• insert (or update): go to the bucket; replace the value if the key is there, otherwise add the key;
• find: go to the bucket and compare the key with the keys stored there;
• delete: go to the bucket and remove the key if it is there.

Every mainstream standard library has both: Python’s dict and set, Java’s HashMap and HashSet, C++’s unordered_map and unordered_set, JavaScript’s Map and Set, and Go’s built-in map. Go has no separate set type, so a Go map whose values go unused plays that part. A later lesson of this module puts the five side by side.

The load factor and resizing

A table that never grew would fill up: n keys in m buckets average n / m per bucket, and every find would compare against more keys as n rose. So a hash table keeps its load factor α = n / m below a limit and resizes when an insertion would cross it. It allocates a larger array, usually about twice as long, and inserts every key again, since each key’s bucket depends on m. Java’s HashMap documents its policy: the default load factor is 0.75, and when the entries outnumber load factor × capacity, the table is rebuilt with about twice as many buckets. Python and Go resize automatically as well, without promising a particular rule.

A single resize costs O(n), yet the cost per insertion stays O(1) on average. Doubling from m to 2m buckets copies about m keys, and it only happens after enough insertions to fill the previous table, so over a run of n insertions the copies add up to a series such as 12 + 24 + 48 + …, which totals less than twice the final number of keys. An average taken over a whole sequence of operations like this is called an amortised cost. When the final size is known in advance, tell the table at the start, with reserve(n) in C++ or HashMap.newHashMap(n) in Java, and it never needs to resize.

Expected O(1), worst case O(n)

The expected bounds rest on two assumptions: the load factor stays bounded, and the hash function spreads the keys so that no bucket collects more than a few. When the second assumption fails, the keys pile into one bucket and the table behaves like a list that also pays for hashing. The program below counts comparisons instead of timing them, so its numbers are the same on every computer:

"""How many key comparisons a lookup costs: a list, a dict whose keys hash well, and a dict whose keys all collide.

Each key counts the times Python compares it with another key (__eq__). A dict first compares the stored hash
codes, which are plain numbers, and calls __eq__ only when two hash codes are equal.
"""


class Ticket:
    comparisons = 0

    def __init__(self, number, spread=True):
        self.number = number
        self.spread = spread

    def __hash__(self):
        # spread=False is a hash function that gives every key the same code.
        return self.number if self.spread else 7

    def __eq__(self, other):
        Ticket.comparisons += 1
        return isinstance(other, Ticket) and self.number == other.number


def counted(action):
    Ticket.comparisons = 0
    action()
    return Ticket.comparisons


for n in (500, 1_000, 2_000):
    as_list = [Ticket(i) for i in range(n)]
    good = {Ticket(i): i for i in range(n)}
    missing = Ticket(-1)
    bad = {}
    build_bad = counted(lambda: bad.update((Ticket(i, spread=False), i) for i in range(n)))
    print(f"n = {n:,}")
    print(f"  find a missing key in a list:       {counted(lambda: missing in as_list):>9,} comparisons")
    print(f"  find a missing key, good hash:      {counted(lambda: missing in good):>9,} comparisons")
    print(f"  find a missing key, every hash 7:   {counted(lambda: Ticket(-1, spread=False) in bad):>9,} comparisons")
    print(f"  build the dict, every hash 7:       {build_bad:>9,} comparisons")

n = 500
  find a missing key in a list:             500 comparisons
  find a missing key, good hash:              0 comparisons
  find a missing key, every hash 7:         500 comparisons
  build the dict, every hash 7:         124,750 comparisons
n = 1,000
  find a missing key in a list:           1,000 comparisons
  find a missing key, good hash:              0 comparisons
  find a missing key, every hash 7:       1,000 comparisons
  build the dict, every hash 7:         499,500 comparisons
n = 2,000
  find a missing key in a list:           2,000 comparisons
  find a missing key, good hash:              0 comparisons
  find a missing key, every hash 7:       2,000 comparisons
  build the dict, every hash 7:       1,999,000 comparisons

Searching a list compares the missing key with every element: 2,000 comparisons for 2,000 keys. A dict whose keys hash well makes none, because it first compares the stored hash codes, which are plain numbers, and calls __eq__ only when two codes match. When every key hashes to 7, a lookup has to compare with every stored key, exactly like the list, and building the dict compares each new key with all the earlier ones: 499,500 comparisons for 1,000 keys, which is n(n − 1)/2. Doubling n multiplies the count by four, the signature of quadratic work. Hash functions that bad do get written, and an attacker can sometimes choose keys that collide on purpose; a later lesson of this module covers both.

Two rules every key must follow

1. Equal keys must have equal hashes. Python’s data model calls this the only required property of a hash, and Java’s Object.hashCode contract says that two objects equal under equals must return the same hash code. Break it and two equal keys can land in different buckets, so a find for one never meets the other. Python blocks the most common way to break it: a class that defines __eq__ without __hash__ gets no hash at all and cannot be a key.
2. A stored key must not change. Its bucket was chosen from its value at the moment it was inserted. Change that value afterwards and lookups hash the new value to a different place, while the old value no longer compares equal.

"""Two rules every key must follow: equal keys have equal hashes, and a stored key never changes."""


class Seat:
    """A seat whose hash is computed from its fields, like a well-behaved key."""

    def __init__(self, coach, berth):
        self.coach, self.berth = coach, berth

    def __eq__(self, other):
        return (self.coach, self.berth) == (other.coach, other.berth)

    def __hash__(self):
        return hash((self.coach, self.berth))


booked = {Seat("S4", 37): "Asha"}
print("lookup with an equal, separate Seat:", booked.get(Seat("S4", 37)))

seat = next(iter(booked))
seat.berth = 38  # the key changes while it is stored
print("after the key changed, lookup S4-38:", booked.get(Seat("S4", 38)))
print("after the key changed, lookup S4-37:", booked.get(Seat("S4", 37)))
print("but the entry is still there:      ", [(s.coach, s.berth, name) for s, name in booked.items()])


class OnlyEq:
    """Defines equality but not a hash: Python then makes it unhashable."""

    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        return self.n == other.n


for key in ([4, 2], OnlyEq(1), (4, 2)):
    try:
        print(f"{type(key).__name__:>6} as a key:", {key: True}[key])
    except TypeError as error:
        print(f"{type(key).__name__:>6} as a key: TypeError: {error}")

lookup with an equal, separate Seat: Asha
after the key changed, lookup S4-38: None
after the key changed, lookup S4-37: None
but the entry is still there:       [('S4', 38, 'Asha')]
  list as a key: TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
OnlyEq as a key: TypeError: cannot use 'OnlyEq' as a dict key (unhashable type: 'OnlyEq')
 tuple as a key: True

The booking stored under berth 37 is found by a different but equal Seat object. Once its berth is changed to 38 while it sits in the dict, neither 37 nor 38 finds it, although the entry is still there. That is why Python refuses lists as keys and accepts tuples, which cannot change. Java’s Map documentation gives the same warning: a map’s behaviour is not specified when a key changes in a way that affects equals while it is in the map.

No order to rely on

A hash table places keys wherever their hashes send them, so the order of its buckets says nothing about the keys. Languages differ in what they promise when you loop over one:

• Python’s dict keeps insertion order, guaranteed since Python 3.7: updating a key keeps its place, and a key that is deleted and added again goes to the end. A set records no order, and a set of strings comes out in a different order from run to run because string hashes are salted.
• JavaScript’s Map and Set iterate in insertion order.
• Java’s HashMap promises no order, not even that the order stays the same over time.
• Go’s specification leaves map iteration order unspecified and not guaranteed to repeat from one loop to the next.

"""Iteration order: a dict keeps insertion order; a set of strings follows the string hashes, which change per run.

Each set below is printed by a fresh Python process started with a fixed PYTHONHASHSEED, so the three lines are the
same every time this file runs, but they differ from each other, as separate runs of an ordinary program would.
"""
import os
import subprocess
import sys

fares = {"Pune": 520, "Agra": 610, "Goa": 980, "Ooty": 455, "Puri": 700}
print("dict, as inserted:      ", list(fares))
fares["Agra"] = 650
print("after updating Agra:    ", list(fares))
del fares["Pune"]
fares["Pune"] = 530
print("after re-adding Pune:   ", list(fares))

show_set = 'print(list({"Pune", "Agra", "Goa", "Ooty", "Puri"}))'
for seed in ("3", "4", "5"):
    env = {**os.environ, "PYTHONHASHSEED": seed}
    done = subprocess.run([sys.executable, "-c", show_set], env=env, capture_output=True, text=True, check=True)
    print(f"set, PYTHONHASHSEED={seed}: ", done.stdout.strip())
print("sorted, every run:      ", sorted(fares))

dict, as inserted:       ['Pune', 'Agra', 'Goa', 'Ooty', 'Puri']
after updating Agra:     ['Pune', 'Agra', 'Goa', 'Ooty', 'Puri']
after re-adding Pune:    ['Agra', 'Goa', 'Ooty', 'Puri', 'Pune']
set, PYTHONHASHSEED=3:  ['Agra', 'Pune', 'Ooty', 'Goa', 'Puri']
set, PYTHONHASHSEED=4:  ['Pune', 'Ooty', 'Agra', 'Puri', 'Goa']
set, PYTHONHASHSEED=5:  ['Ooty', 'Pune', 'Puri', 'Goa', 'Agra']
sorted, every run:       ['Agra', 'Goa', 'Ooty', 'Pune', 'Puri']

// The same five-key map, iterated 50 times in one run: the language specification leaves the order unspecified,
// and the runtime starts each loop at a random place. Sorting the keys gives one order every time.
package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

func main() {
	fares := map[string]int{"Pune": 520, "Agra": 610, "Goa": 980, "Ooty": 455, "Puri": 700}
	orders := map[string]bool{}
	for range 50 {
		var order []string
		for city := range fares {
			order = append(order, city)
		}
		orders[strings.Join(order, " ")] = true
	}
	fmt.Printf("50 loops over one 5-key map: %d different orders\n", len(orders))
	fmt.Println("sorted keys:", slices.Sorted(maps.Keys(fares)))
}

from session import run, versions

versions("go version")
run("go run map_order.go")

# go version go1.27.1 darwin/arm64
$ go run map_order.go
50 loops over one 5-key map: 5 different orders
sorted keys: [Agra Goa Ooty Pune Puri]

The three sets were printed by three Python processes whose hash seeds were fixed with PYTHONHASHSEED, and each one lists the same five cities in its own order. Go goes further and varies the order inside a single run: 50 loops over the same five keys produced 5 different orders in the recorded run. Whenever output has to come out in a particular order, for a report, a test’s expected output or a file another program reads, sort the keys at the point of output: sorted(d) in Python, slices.Sorted(maps.Keys(m)) in Go.

Hash map, sorted structure or direct-address array?

Some examples of each. Counting how often each of the 26 letters appears in a word is a direct-address job: an array of 26 counters, indexed by the letter’s position in the alphabet. Looking up an account by email address is a hash map’s job, since emails have no small range and nobody asks for them in order. Listing every session that expires within the next minute is a range question, which a hash map cannot answer without examining every entry, while a sorted map such as Java’s TreeMap or C++’s std::map jumps to the first match and reads on. When both kinds of question matter, real systems keep both structures over the same data.

Practise: find the first repeated booking

def first_repeated_booking_id(ids):
    """The first ID met for the second time when reading ids from the start, or None when all differ."""
    # Replace this line with your code.
    return None

from first_repeat import first_repeated_booking_id


def test_small_cases():
    """returns the first ID whose second copy comes first, or None"""
    assert first_repeated_booking_id([]) is None
    assert first_repeated_booking_id(["A12"]) is None
    assert first_repeated_booking_id(["A12", "B07", "C33"]) is None
    assert first_repeated_booking_id(["A12", "B07", "A12"]) == "A12"
    assert first_repeated_booking_id(["A12", "B07", "B07", "A12"]) == "B07"
    assert first_repeated_booking_id(["K", "L", "K", "L", "L"]) == "K"


def test_ids_of_other_types():
    """works for any hashable IDs, such as numbers"""
    assert first_repeated_booking_id([5, 3, 8, 3, 5]) == 3
    assert first_repeated_booking_id([0, 0]) == 0


def test_long_log():
    """finishes on 60,000 IDs whose only repeat is the last one"""
    ids = [f"PNR{i:06d}" for i in range(60_000)]
    ids.append("PNR000017")
    assert first_repeated_booking_id(ids) == "PNR000017"

/** The first ID met for the second time when reading ids from the start, or null when all differ. */
export function firstRepeatedBookingId(ids) {
  // Replace this line with your code.
  return null;
}

import { test, assert } from 'mysmartcopilot:test';
import { firstRepeatedBookingId } from './first_repeat.mjs';

test('returns the first ID whose second copy comes first, or null', () => {
  assert.equal(firstRepeatedBookingId([]), null);
  assert.equal(firstRepeatedBookingId(['A12']), null);
  assert.equal(firstRepeatedBookingId(['A12', 'B07', 'C33']), null);
  assert.equal(firstRepeatedBookingId(['A12', 'B07', 'A12']), 'A12');
  assert.equal(firstRepeatedBookingId(['A12', 'B07', 'B07', 'A12']), 'B07');
  assert.equal(firstRepeatedBookingId(['K', 'L', 'K', 'L', 'L']), 'K');
});

test('works for numbers as IDs', () => {
  assert.equal(firstRepeatedBookingId([5, 3, 8, 3, 5]), 3);
  assert.equal(firstRepeatedBookingId([0, 0]), 0);
});

test('finishes on 60,000 IDs whose only repeat is the last one', () => {
  const ids = Array.from({ length: 60000 }, (_, i) => `PNR${String(i).padStart(6, '0')}`);
  ids.push('PNR000017');
  assert.equal(firstRepeatedBookingId(ids), 'PNR000017');
});

Interview questions

What is a hash table’s load factor, and why does the table resize? The load factor is the number of stored keys divided by the number of buckets, so it is also the average number of keys per bucket. Lookups stay fast only while it stays small: with chaining, a search for a missing key looks at about that many keys. A table therefore resizes when an insertion would push the load factor past a limit, such as Java’s default of 0.75. It allocates about twice as many buckets and inserts every key again, because a key’s bucket depends on the number of buckets. One resize costs O(n), but because the size doubles, the copying adds up to less than twice the number of keys over all insertions, so each insertion costs O(1) amortised.

Why must two equal keys have the same hash code, and what goes wrong if they do not? A table finds a key by hashing it and searching only the bucket that hash selects. If two equal keys could hash differently, a lookup with one of them would search the wrong bucket and miss an entry stored under the other, and a set could end up holding the same key twice. Both Python’s data model and Java’s hashCode contract require equal objects to have equal hashes. The reverse is not required: two different keys may share a hash, which is a collision, and the table settles it by comparing the keys with equality.

Key takeaways

• A hash table is an array plus a hash function: the key’s hash, reduced modulo the number of buckets, chooses the bucket where the key is stored and later found.
• The load factor α = n / m is the average number of keys per bucket. Tables resize, usually by doubling, to keep it below a limit, which keeps insertion O(1) amortised.
• Expected O(1) needs a bounded load factor and a hash that spreads the keys; when every key collides, a lookup compares with all n keys and building the table takes O(n²) comparisons.
• Equal keys must have equal hashes, and a stored key must never change.
• Only some languages promise an iteration order. Sort the keys whenever output order matters.
• Pick direct addressing for small dense key ranges, a hash map for exact lookups and a sorted structure for order and ranges.