Data structure 3 of 12

Hash maps

A hash map stores pairs: a key and its value. Give it the key and it goes straight to the value, without searching. That one trick removes the slow inner loop from a huge number of problems.

A 3-minute conversation: Sam asks, Priya explains

0:00 / 2:41

Follow along on the page Pause on “your turn” questions

Sam Hash maps. I know them as dictionaries.
Priya Then this lesson is about why they're fast, and the two jobs you'll use them for most. A hash map stores pairs: a key and its value. Give it the key and it goes straight to the value, without searching.
Priya Picture a post room with a hundred pigeonholes. A simple rule turns any name into a hole number. To deliver, apply the rule and drop the letter in. To collect, apply the same rule and look in one hole.
Sam What can be a key?
Priya Anything hashable: numbers, strings, tuples. Not lists. And keys are unique, so setting a key again replaces its value.
Sam What's inside?
Priya An array of buckets. A hash function turns the key into a number, and that number modulo the array's size picks a bucket. Two keys can land in the same bucket. That's a collision, and the bucket just holds a short list, so the map checks each key in it.
Sam So it's not always instant?
Priya On average it is, because buckets stay short. In the rare worst case, everything collides and it's linear.
Sam The costs?
Priya Set, read, delete and "is this key here?" are all constant on average. Visiting every pair is linear. And finding the key with the biggest value is linear too, because a map keeps no order.
Priya Your turn. You catch yourself searching a list for something you saw earlier, inside a loop. What should you do instead?
Priya Store it in a map the first time you see it, then look it up. The inner loop disappears.
Sam How do I read a missing key safely?
Priya In Python, dot get with a default. In Java, getOrDefault. In TypeScript, the double question mark. Counter and defaultdict save typing in Python.
Sam The players?
Priya First, a hash map built by hand, with eight buckets, so you can see a collision happen: keys three and eleven share bucket three. Then counting things: the old count or zero, plus one. Then grouping things by a key, where each key maps to a growing list.
Sam Memory hook?
Priya The post room. Key in, value out, no searching. Seen it before? Store it the first time; look it up the second.
Sam Problems?
Priya Number of good pairs, where each new copy pairs with every earlier copy. Find lucky integer, counting first and checking after. And k-th distinct string, where the map counts but the array keeps the order.
Sam Mistakes?
Priya Reading a missing key. Using a list as a key. Relying on order. Changing the map while looping over it. And in Java, comparing boxed Integers with double equals.
Sam Next?
Priya Lesson four, hash sets: keys with no values.

1. What it is

A post room with 100 pigeonholes. A simple rule turns any name into a hole number (say, add up its letters and keep the last two digits). To deliver a letter, apply the rule and drop it in. To collect, apply the same rule and look in one hole. Nobody walks along all 100.

A hash map (Python dict, TypeScript Map, Java HashMap) maps each key to a value: a name to a phone number, a word to how many times it appears, a number to the index where you saw it. Keys are unique; setting an existing key replaces its value.

Fast: add, update, read, delete and "is this key here?", all O(1) on average.
The cost: extra memory, and no order you can rely on for sorting (Python keeps insertion order, but not sorted order).
Keys must be hashable: numbers, strings and tuples, not lists.

2. How it sits in memory

Inside, a hash map is an array of buckets. A hash function turns the key into a number, and that number modulo the array's size picks the bucket. Two keys can land in the same bucket (a collision); the bucket then holds a short list, and the map checks each entry's key.

As long as buckets stay short, every operation touches one bucket: O(1) on average. When the map gets too full it doubles its buckets and re-files everything, just like a growing list. In the rare worst case, when every key collides, one bucket holds everything and operations become O(n).

3. Operations and what they cost

Operation	Python	Cost
Set a value	`m[k] = v`	`O(1)` average
Read a value	`m[k]` (error if missing), `m.get(k, default)`	`O(1)` average
Is the key there?	`k in m`	`O(1)` average
Delete	`del m[k]`, `m.pop(k)`	`O(1)` average
Visit every pair	`for k, v in m.items()`	`O(n)`
Find the key with the largest value	`max(m, key=m.get)`	`O(n)`: a map doesn't keep values sorted

When to reach for oneWhenever you catch yourself searching a list for something you saw earlier, store it in a map the first time instead.

4. In Python, TypeScript and Java

The same three moves (set, read with a default, count) in each language.

ages = {"ana": 31, "ben": 27}
    ages["cy"] = 40                  # add
    ages["ben"] = 28                 # replace
    print(ages.get("dee", 0))        # 0: a default instead of an error
    print("ana" in ages)             # True
    for name, age in ages.items():   # every pair
        print(name, age)

    from collections import Counter, defaultdict
    counts = Counter("banana")       # {'b': 1, 'a': 3, 'n': 2}
    groups = defaultdict(list)       # a missing key starts as []
    groups["a"].append("apple")

const ages = new Map<string, number>([["ana", 31], ["ben", 27]]);
    ages.set("cy", 40);                       // add
    ages.set("ben", 28);                      // replace
    console.log(ages.get("dee") ?? 0);        // 0
    console.log(ages.has("ana"));             // true
    for (const [name, age] of ages) console.log(name, age);

    const counts = new Map<string, number>();
    for (const c of "banana") counts.set(c, (counts.get(c) ?? 0) + 1);

Map<String, Integer> ages = new HashMap<>(Map.of("ana", 31, "ben", 27));
    ages.put("cy", 40);                               // add
    ages.put("ben", 28);                              // replace
    System.out.println(ages.getOrDefault("dee", 0));  // 0
    System.out.println(ages.containsKey("ana"));      // true
    for (Map.Entry<String, Integer> e : ages.entrySet()) System.out.println(e.getKey() + " " + e.getValue());

    Map<Character, Integer> counts = new HashMap<>();
    for (char c : "banana".toCharArray()) counts.merge(c, 1, Integer::sum);

5. Core operations, step by step

First a tiny hash map built by hand, so the "magic" disappears; then the two jobs you will use one for most often.

A · A hash map by hand (buckets and collisions)

What it doesStores each pair in the bucket chosen by the key's hash; reads by checking only that bucket.

Picture itPigeonholes: the rule picks the hole, and a hole can hold a few letters.

CostO(1) average per put or get; O(n) if every key collides.

The code. Eight buckets, each a list of [key, value] pairs. The language's own map does the same with a far better hash.

class TinyMap:
    def __init__(self):
        self.buckets = [[] for _ in range(8)]

    def put(self, key, value):
        b = self.buckets[hash(key) % 8]
        for pair in b:
            if pair[0] == key:
                pair[1] = value
                return
        b.append([key, value])

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

class TinyMap {
  buckets: [number, string][][] = Array.from({ length: 8 }, () => []);

  put(key: number, value: string): void {
    const b = this.buckets[key % 8];
    for (const pair of b) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    b.push([key, value]);
  }

  get(key: number): string | null {
    const b = this.buckets[key % 8];
    for (const [k, v] of b) {
      if (k === key) {
        return v;
      }
    }
    return null;
  }
}

static class TinyMap {
    List<List<Object[]>> buckets = new ArrayList<>();
    TinyMap() { for (int i = 0; i < 8; i++) buckets.add(new ArrayList<>()); }

    void put(int key, String value) {
        List<Object[]> b = buckets.get(key % 8);
        for (Object[] pair : b) {
            if ((int) pair[0] == key) {
                pair[1] = value;
                return;
            }
        }
        b.add(new Object[]{key, value});
    }

    String get(int key) {
        List<Object[]> b = buckets.get(key % 8);
        for (Object[] pair : b) {
            if ((int) pair[0] == key) {
                return (String) pair[1];
            }
        }
        return null;
    }
}

Line by line.

Line	What it does	Why
`b = self.buckets[hash(key) % 8]`	The rule picks one bucket.	Integers hash to themselves in Python, so key 11 goes to bucket 3, the same as key 3: a collision.
`if pair[0] == key`	Is this pair our key?	A bucket can hold several keys; compare each one.
`pair[1] = value`	Same key: replace.	Keys are unique; setting again overwrites.
`b.append([key, value])`	New key: add to the bucket.	Buckets stay short when the hash spreads keys well.

Watch it run. Put 3 → cat, 11 → dog, 5 → emu and 3 → cow, then get 11, 3 and 7.

Watch out for:

Thinking a map is always O(1). It is O(1) on average because buckets stay short. A terrible hash (or an attacker) can make one bucket hold everything.

B · Count things

What it doesMaps each item to how many times it has appeared.

Picture itA tally sheet: find the item's line, add one mark; a new item gets a new line.

CostO(n) time, O(k) space for k different items.

The code. Read the old count with a default of 0, add one, store it back.

def count_words(words):
    counts = {}
    for w in words:
        counts[w] = counts.get(w, 0) + 1
    return counts

function countWords(words: string[]): Map<string, number> {
  const counts = new Map<string, number>();
  for (const w of words) {
    counts.set(w, (counts.get(w) ?? 0) + 1);
  }
  return counts;
}

static Map<String, Integer> countWords(String[] words) {
    Map<String, Integer> counts = new LinkedHashMap<>();
    for (String w : words) {
        counts.put(w, counts.getOrDefault(w, 0) + 1);
    }
    return counts;
}

Line by line.

Line	What it does	Why
`counts.get(w, 0) + 1`	The old count, or 0 if this is the first time, plus one.	counts[w] += 1 raises KeyError the first time a word appears.
`counts[w] = ...`	Store the new count.	O(1) average.

Watch it run. Count ["red", "blue", "red", "green", "red"].

Watch out for:

counts[w] += 1 on a plain dict. Fails on the first occurrence. Use get with a default, Counter or defaultdict(int).

C · Group things by a key

What it doesMaps each key to a list of the items that share it.

Picture itSorting post into pigeonholes by surname initial: every letter for an 'M' goes in the M hole.

CostO(n) time and space.

The code. The key decides the group; the value is a list that grows.

def group_by_first_letter(words):
    groups = {}
    for w in words:
        key = w[0]
        if key not in groups:
            groups[key] = []
        groups[key].append(w)
    return groups

function groupByFirstLetter(words: string[]): Map<string, string[]> {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = w[0];
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key)!.push(w);
  }
  return groups;
}

static Map<Character, List<String>> groupByFirstLetter(String[] words) {
    Map<Character, List<String>> groups = new LinkedHashMap<>();
    for (String w : words) {
        char key = w.charAt(0);
        if (!groups.containsKey(key)) {
            groups.put(key, new ArrayList<>());
        }
        groups.get(key).add(w);
    }
    return groups;
}

Line by line.

Line	What it does	Why
`key = w[0]`	Decide which group the word belongs to.	Change this one line to group by length, by sorted letters (anagrams), and so on.
`if key not in groups: groups[key] = []`	First item of a new group: make its list.	defaultdict(list) does this for you.
`groups[key].append(w)`	Add the word to its group.

Watch it run. Group ["apple", "bean", "avocado", "beet", "corn"] by first letter.

Watch out for:

Using a list as the key. Lists aren't hashable. Convert to a tuple or a string first (e.g. the sorted letters joined).

6. How to remember it

Memory hook: "The post room"A rule turns any key into a pigeonhole number. Deliver and collect by the rule, never by searching. Two names can share a hole; the clerk checks the name on each envelope.

Picture

A wall of pigeonholes, a few holding two or three envelopes.

Chant

"Key in, value out, no searching."

Key rule

Seen it before? Store it the first time; look it up the second.

7. Problems solved with it

Three easy problems where a map turns a slow search into a lookup.

LC 1512 · Number of Good Pairs

The problemA pair (i, j) is good if nums[i] == nums[j] and i < j. Return the number of good pairs.

What it doesFor each number, every earlier copy of it makes a new good pair; a map remembers how many copies came before.

CostO(n) time instead of O(n²) for checking every pair.

The code. Add the count so far, then increase it.

def num_identical_pairs(nums):
    seen = {}
    pairs = 0
    for x in nums:
        pairs += seen.get(x, 0)
        seen[x] = seen.get(x, 0) + 1
    return pairs

function numIdenticalPairs(nums: number[]): number {
  const seen = new Map<number, number>();
  let pairs = 0;
  for (const x of nums) {
    pairs += seen.get(x) ?? 0;
    seen.set(x, (seen.get(x) ?? 0) + 1);
  }
  return pairs;
}

static int numIdenticalPairs(int[] nums) {
    Map<Integer, Integer> seen = new HashMap<>();
    int pairs = 0;
    for (int x : nums) {
        pairs += seen.getOrDefault(x, 0);
        seen.put(x, seen.getOrDefault(x, 0) + 1);
    }
    return pairs;
}

Line by line.

Line	What it does	Why
`pairs += seen.get(x, 0)`	Each earlier copy of x pairs with this one.	Read the count before adding x itself, or x would pair with itself.
`seen[x] = seen.get(x, 0) + 1`	Now count this copy.

Watch it run. [1, 2, 3, 1, 1, 3].

Watch out for:

Two nested loops. Correct but O(n²). The map version counts all pairs in one pass.

LC 1394 · Find Lucky Integer in an Array

The problemA lucky integer appears exactly as many times as its value. Return the largest lucky integer, or −1.

What it doesCounts every number, then checks each (value, count) pair.

CostO(n).

The code. Count first; decide after.

def find_lucky(arr):
    counts = {}
    for x in arr:
        counts[x] = counts.get(x, 0) + 1
    best = -1
    for value, times in counts.items():
        if value == times:
            best = max(best, value)
    return best

function findLucky(arr: number[]): number {
  const counts = new Map<number, number>();
  for (const x of arr) {
    counts.set(x, (counts.get(x) ?? 0) + 1);
  }
  let best = -1;
  for (const [value, times] of counts) {
    if (value === times) {
      best = Math.max(best, value);
    }
  }
  return best;
}

static int findLucky(int[] arr) {
    Map<Integer, Integer> counts = new HashMap<>();
    for (int x : arr) {
        counts.put(x, counts.getOrDefault(x, 0) + 1);
    }
    int best = -1;
    for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
        if (e.getKey().equals(e.getValue())) {
            best = Math.max(best, e.getKey());
        }
    }
    return best;
}

Line by line.

Line	What it does	Why
`for value, times in counts.items()`	Look at every distinct number once.	Iterating the map, not the array, checks each value once.
`if value == times`	Is it lucky?
`best = max(best, value)`	Keep the largest lucky one.	Map order isn't sorted, so compare.

Watch it run. [1, 2, 2, 3, 3, 3].

Watch out for:

Returning the first lucky number found. Maps don't iterate in sorted order. Keep the maximum.

LC 2053 · Kth Distinct String in an Array

The problemA string is distinct if it appears exactly once. Return the k-th distinct string in the original order, or "".

What it doesCounts every string, then walks the array in order counting distinct ones.

CostO(n).

The code. The map answers "how many?"; the original array keeps the order.

def kth_distinct(arr, k):
    counts = {}
    for s in arr:
        counts[s] = counts.get(s, 0) + 1
    for s in arr:
        if counts[s] == 1:
            k -= 1
            if k == 0:
                return s
    return ""

function kthDistinct(arr: string[], k: number): string {
  const counts = new Map<string, number>();
  for (const s of arr) {
    counts.set(s, (counts.get(s) ?? 0) + 1);
  }
  for (const s of arr) {
    if (counts.get(s) === 1) {
      k -= 1;
      if (k === 0) {
        return s;
      }
    }
  }
  return "";
}

static String kthDistinct(String[] arr, int k) {
    Map<String, Integer> counts = new HashMap<>();
    for (String s : arr) {
        counts.put(s, counts.getOrDefault(s, 0) + 1);
    }
    for (String s : arr) {
        if (counts.get(s) == 1) {
            k -= 1;
            if (k == 0) {
                return s;
            }
        }
    }
    return "";
}

Line by line.

Line	What it does	Why
`for s in arr: counts[s] = ...`	First pass: count.	You can't call a string distinct until you've seen them all.
`for s in arr`	Second pass in the original order.	Iterating the map would lose the order the problem asks for.
`k -= 1; if k == 0`	Count down the distinct strings.

Watch it run. ["d", "b", "c", "b", "c", "a"], k = 2.

Watch out for:

Walking the map instead of the array. The k-th must follow the original order.

More practice, solved on the pattern pages

#	Problem	Level	Where
1	Two Sum	Easy	Solved step by step on 16 · Hash Map & Set
383	Ransom Note	Easy	Solved step by step on 16 · Hash Map & Set
242	Valid Anagram	Easy	Solved step by step on 16 · Hash Map & Set
169	Majority Element	Easy	Solved step by step on 16 · Hash Map & Set
205	Isomorphic Strings	Easy	Solved step by step on 16 · Hash Map & Set
49	Group Anagrams	Medium	Solved step by step on 16 · Hash Map & Set

8. Common mistakes

Reading a missing keym[k] raises KeyError in Python (TypeScript returns undefined, Java null). Use get(k, default), getOrDefault or ??.

Mutable keysA list can't be a dict key. Use a tuple or a string. In Java, don't change an object after using it as a key.

Relying on orderPython dicts keep insertion order, Java's HashMap doesn't. Neither keeps keys sorted: sort them yourself when order matters.

Changing a map while looping over itAdding or deleting keys inside for k in m raises an error. Loop over list(m) or collect changes first.

Comparing Integer values with == in JavaBoxed integers above 127 are different objects. Use .equals or unbox to int.

9. Self-check quiz

Looking up a key in a hash map with a million entries costs…

The hash picks one bucket, and buckets stay short.

Two keys hash to the same bucket. What happens?

That's a collision. The bucket holds both; lookups compare keys.

Which safely counts word w in a plain Python dict?

The first time a word appears, counts[w] doesn't exist yet.

You want to use a pair of numbers as a key. Which works?

Keys must be hashable, which means unchangeable. Tuples are; lists and sets aren't.

10. Where it shows up next

16 · Hash Map & Set: the pattern page, with Two Sum, anagrams and grouping.
01 · Prefix Sum: a map of running sums answers "how many subarrays add up to k?".
03 · Sliding Window: a map counts what's inside the window.
07 · Top K: count with a map, then pick the most frequent with a heap.

Next structure: 04 · Hash sets, a hash map with keys and no values.