Hash Maps and Hash Sets

What is a hash map?

A hash map (also called a hash table, dictionary or map) stores key → value pairs and finds the value for a key almost instantly, however many pairs it holds. Python's dict, JavaScript's Map, Java's HashMap and C++'s std::unordered_map are all hash maps. A hash set is the same idea with keys only: it answers "have I seen this before?" in O(1).

Think of a school library with 26 shelves, one per letter. To find Wings of Fire, you don't scan every shelf: you go straight to shelf W and look through the few books there. A hash map does the same thing, except the "first letter" is a number computed from the key.

How it works

A hash map is an array of buckets. To store a key:

1. A hash function turns the key into a large number. The same key always gives the same number.
2. That number, modulo the number of buckets, picks a bucket: index = hash(key) % buckets.
3. The pair goes into that bucket.

Looking a key up repeats steps 1 and 2 and then checks only that one bucket. That's why lookups don't slow down as the map grows.

Our hash function treats a string like a number written in base 31: h = h × 31 + code of next character for each character. Multiplying by a prime mixes the characters so that similar keys (like "ab" and "ba") land in different places.

Collisions

Two different keys can land in the same bucket. This is called a collision, and it is unavoidable: there are far more possible keys than buckets. The simplest fix, used below, is separate chaining: each bucket holds a small list of every pair that landed there, and a lookup checks the few pairs in that list.

Load factor and resizing

The load factor is number of keys ÷ number of buckets. As it rises, chains get longer and lookups slow down. So when the load factor passes a threshold (0.75 below, the same as Java's HashMap), the map doubles its bucket array and re-hashes every key into the new array. Like a dynamic array's growth, this occasional O(n) step averages out to O(1) per insert.

Notice in the output below that banana and cherry shared bucket 3 when there were 4 buckets, but after resizing to 8, banana moved to bucket 7. A key's bucket depends on the bucket count, which is why resizing must re-hash everything.

Operations and their cost

The worst case happens when many keys land in the same bucket, for example with a poor hash function. Good hash functions and resizing keep chains short, so in practice you get the average case.

Building one yourself

The implementation below uses separate chaining (each bucket is a list of [key, value] pairs), starts with 4 buckets and doubles them when the load factor goes above 0.75. put updates the value if the key already exists, which is how every real map behaves.

class HashMap:
    def __init__(self, capacity=4):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _hash(self, key):
        h = 0
        for ch in key:
            h = (h * 31 + ord(ch)) % 1_000_000_007
        return h

    def _index(self, key):
        return self._hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value          # existing key: update in place
                return False
        bucket.append([key, value])      # new key: add to the chain
        self.size += 1
        if self.size / len(self.buckets) > 0.75:
            self._resize()
        return True

    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return None

    def contains(self, key):
        return any(k == key for k, _ in self.buckets[self._index(key)])

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _resize(self):
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        for bucket in old:
            for k, v in bucket:
                self.buckets[self._index(k)].append([k, v])


def yes_no(flag):
    return "true" if flag else "false"


m = HashMap()
for key, value in (("apple", 3), ("banana", 5), ("cherry", 7), ("mango", 2), ("kiwi", 4), ("grape", 6)):
    before = len(m.buckets)
    m.put(key, value)
    note = f" (resized {before} -> {len(m.buckets)})" if len(m.buckets) != before else ""
    print(f"put({key}, {value}): bucket {m._index(key)} of {len(m.buckets)}{note}")
print("get(banana):", m.get("banana"))
m.put("apple", 10)
print("get(apple) after update:", m.get("apple"))
print("contains(lemon):", yes_no(m.contains("lemon")))
print("remove(cherry):", yes_no(m.remove("cherry")))
print("size:", m.size)
for i, bucket in enumerate(m.buckets):
    if bucket:
        print(f"bucket {i}: " + " -> ".join(f"{k}={v}" for k, v in bucket))

put(apple, 3): bucket 2 of 4
put(banana, 5): bucket 3 of 4
put(cherry, 7): bucket 3 of 4
put(mango, 2): bucket 2 of 8 (resized 4 -> 8)
put(kiwi, 4): bucket 0 of 8
put(grape, 6): bucket 3 of 8
get(banana): 5
get(apple) after update: 10
contains(lemon): false
remove(cherry): true
size: 5
bucket 0: kiwi=4
bucket 2: apple=10 -> mango=2
bucket 3: grape=6
bucket 7: banana=5

Hash maps in the standard libraries

Plain JavaScript objects ({}) also work as maps for string keys, but Map keeps insertion order for every key type, has a size, and can't collide with built-in names like constructor.

Patterns that use hash maps

• Counting: how many times does each word, character or number appear?
• Have I seen this? Detect duplicates, or find the complement in Two Sum, with a set or map of values seen so far.
• Grouping: collect items by a key, such as words grouped by their sorted letters (anagrams).
• Caching (memoisation): store results of expensive calls so repeated calls are instant.
• Indexing: map an id to its record so you don't search a list each time.

Common mistakes

• Using mutable keys. If a key changes after insertion its hash changes, and the map can no longer find it. Python refuses list keys for this reason; in Java, don't mutate objects used as keys.
• Expecting an order. Python dict and JavaScript Map keep insertion order, but Java HashMap and C++ unordered_map don't. Use LinkedHashMap or std::map (sorted) if order matters.
• Reading a missing key carelessly. d[k] raises KeyError in Python, m.get(k) returns null in Java, and m[k] in C++ silently inserts a default value.
• Defining equality without hashing. In Java, overriding equals without hashCode breaks HashMap: equal keys must have equal hashes.

When to use a hash map

Use a hash map whenever you look things up by a key: counting, de-duplicating, grouping, caching, or replacing a nested loop that searches for a matching item. That last one is the big win: an O(n) search inside an O(n) loop becomes an O(1) lookup, turning O(n²) into O(n).

Don't use one when you need the keys in sorted order or need "the smallest key greater than x". A balanced binary search tree (TreeMap in Java, std::map in C++) handles those in O(log n). The Binary search trees guide explains how.