# Hashing for Speed

> Why a hash map turns an O(n) scan into an O(1) average lookup: buckets and hash functions explained plainly, frequency counting, the one-pass two-sum, set membership and de-duplication, plus the gotchas - unhashable keys, worst-case collisions, and unordered results.


---

# Hashing for Speed

The single most useful trick in everyday programming isn't a clever algorithm - it's a data structure. A
**hash map** (Python's `dict`, JavaScript's `Map`, Java's `HashMap`) lets you look something up in roughly
**constant time** no matter how much data you've stored, where a plain list forces you to scan item by item.
Learn to reach for it, and a whole class of "this is too slow" problems just evaporate.

This guide starts with *why* that constant-time lookup is even possible - the bucket-and-hash idea underneath
- and then puts it to work on three patterns you'll use constantly: counting things, finding pairs in one
pass, and testing membership / removing duplicates. Every example is runnable Python.

## How to read this

Read in order. Phase 1 builds the mental model of why lookups are fast, which makes the patterns in Phases 2
and 3 feel obvious instead of magical. If you've just read
[Two Pointers & the Sliding Window](/guides/two-pointers-and-sliding-window), you'll see the hash map solve
the same two-sum problem from a completely different angle - and without needing sorted input.

## The phases

1. **[Why Hash Maps Are Fast](01-why-hash-maps-are-fast.md)** · 🟢 Basic - scanning a list vs a hash lookup,
   and the buckets-plus-hash-function idea that makes O(1) average lookup possible.
2. **[Frequency Counting & Two-Sum](02-frequency-counting-and-two-sum.md)** · 🟡 Intermediate - counting
   occurrences with a dictionary, then the classic two-sum solved in a single pass.
3. **[Sets, Membership & Dedup](03-sets-membership-and-dedup.md)** · 🟢 Basic - the set for fast membership
   and de-duplication, and the gotchas: unhashable keys, worst-case collisions, and unordered results.


---

# Why Hash Maps Are Fast

Before the patterns, the mental model. If you understand *why* a hash map lookup is fast, you'll know exactly
when reaching for one turns a slow program into an instant one - and when it won't help.

## The slow way: scanning a list

Suppose you have a list and you want to know whether some value is in it. With a list, there's no shortcut:
you check the first element, then the next, then the next, until you find it or run out. That's linear time,
`O(n)` - double the list, double the work in the worst case.

```python runnable
def scan_contains(items, target):
    for x in items:          # check every element until a match
        if x == target:
            return True
    return False

nums = [10, 20, 30, 40, 50]
print(scan_contains(nums, 40))
print(scan_contains(nums, 99))
```
```console
True
False
```
*What just happened:* finding `40` took four comparisons; confirming `99` is absent took all five - the loop
had to look at everything to be sure. On a list of a million items, a worst-case lookup is a million
comparisons. Do that lookup inside another loop and you're at a billion operations, the classic accidental
`O(n²)`.

## The fast way: a hash lookup

A hash map skips the scan entirely. Ask a Python `dict` for a key and it jumps more or less straight to the
answer, regardless of how many entries it holds.

```python runnable
prices = {"apple": 30, "banana": 10, "cherry": 50}

print(prices["banana"])         # direct lookup, no scanning
print("cherry" in prices)       # membership test, also direct
print(prices.get("mango", 0))   # missing key -> default instead of error
```
```console
10
True
0
```
*What just happened:* none of these three operations looked at every entry. Each went (on average) straight
to the spot where that key's value lives. That's the whole selling point: lookup, insert, and membership are
all `O(1)` on average - constant time that barely changes as the map grows.

## Why it works: buckets and a hash function

Here's the idea underneath, without the heavy math. A hash map keeps an internal array of slots called
**buckets**. To store a key, it runs the key through a **hash function** - a routine that turns the key into
a number - and uses that number to pick a bucket. To look the key up later, it hashes the key again, lands
on the same bucket, and finds the value already sitting there. No scanning, because the key itself tells you
where to look.

```python runnable
# Python exposes the hash function it uses for dict/set keys:
print(hash("apple"))
print(hash("banana"))

# A toy version of "which bucket?": squash the hash into a small range.
def bucket_index(key, num_buckets):
    return hash(key) % num_buckets

for key in ["apple", "banana", "cherry"]:
    print(key, "->", bucket_index(key, 8))
```
```console
```
*What just happened:* `hash(...)` turns each key into a big integer (the exact numbers vary between Python
runs, which is why the console above is left blank - yours will differ). Taking that integer modulo the
bucket count squashes it into a valid slot index, `0` to `7` here. Real hash maps do exactly this: hash the
key, mod into a bucket, store or fetch there. The lookup cost doesn't depend on how many keys exist, only on
computing one hash - hence `O(1)` on average.

📝 **Terminology.** The words differ by language but the structure is the same: Python calls it a `dict`,
JavaScript a `Map` (or plain object), Java a `HashMap`, C++ an `unordered_map`, Go just `map`, Rust a
`HashMap`. All of them are hash maps: keys hashed into buckets for near-constant-time access.

⚠️ **Gotcha.** "On average" is doing real work in that sentence. When two different keys hash into the *same*
bucket - a **collision** - the map has to store both there and do a tiny local scan to tell them apart. A few
collisions are normal and cheap. A pathological pile-up of collisions is what makes the rare worst case slow,
which we'll come back to in Phase 3.

```quiz
[
  {
    "q": "Why is checking `value in some_list` O(n) but `key in some_dict` O(1) on average?",
    "choices": ["Lists are stored on disk", "A dict hashes the key straight to its bucket, while a list must scan element by element", "Dicts are always smaller than lists", "The `in` keyword is optimized only for dicts"],
    "answer": 1,
    "explain": "A list has no way to know where a value is, so it scans. A dict hashes the key to a bucket and jumps there, independent of size."
  },
  {
    "q": "What is the job of the hash function in a hash map?",
    "choices": ["To sort the keys", "To turn a key into a number that selects which bucket the value goes in", "To compress the stored values", "To count how many keys exist"],
    "answer": 1,
    "explain": "The hash function maps a key to a number; the map uses that number (mod the bucket count) to decide where the key/value lives, enabling direct access."
  }
]
```


---

# Frequency Counting & Two-Sum

With the "why" in hand, here are the two hash-map patterns you'll reach for most. Both share one move:
**remember what you've already seen so you never have to look back through the data.**

## Pattern one: counting occurrences

How many times does each item appear? A dictionary from item to count answers it in a single pass. Each item
you meet, bump its count by one; use `.get(key, 0)` so the first sighting starts from zero instead of raising
a `KeyError`.

```python runnable
def char_counts(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return counts

print(char_counts("mississippi"))
```
```console
{'m': 1, 'i': 4, 's': 4, 'p': 2}
```
*What just happened:* one walk through the string. `counts.get(ch, 0)` reads the running total (or `0` if
this character is new), adds one, and stores it back. By the end every character maps to how often it
appeared - `i` and `s` four times each. This is `O(n)`: one lookup-and-update per character, each `O(1)` on
average.

💡 **Key point.** The standard library has this exact pattern prepackaged as `collections.Counter` - so in
real code you'd write `Counter("mississippi")`. Writing the loop by hand once is worth it to see there's no
magic: it's just a dict and `+= 1`.

## Pattern two: two-sum in a single pass

The classic interview problem: given a list of numbers and a target, return the indices of the two numbers
that add up to the target. The brute force checks every pair - `O(n²)`. The
[two-pointer version](/guides/two-pointers-and-sliding-window) gets it to `O(n)` but *requires sorting first*
(and sorting scrambles the original indices). The hash map does it in one pass with no sorting at all.

The insight: as you walk the list, for each number `x` you know exactly what its partner must be -
`target - x`, call it the **complement**. So instead of searching for the partner, ask a hash map "have I
already seen `target - x`?" If yes, you've found the pair. If no, remember `x` (and its index) and move on.

```python runnable
def two_sum(nums, target):
    seen = {}                       # value -> index where we saw it
    for i, x in enumerate(nums):
        need = target - x           # the complement that would complete the pair
        if need in seen:
            return (seen[need], i)
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([1, 2, 3], 100))
```
```console
(0, 1)
(1, 2)
None
```
*What just happened:* for `[2, 7, 11, 15]` with target `9`: see `2`, its complement `7` isn't in `seen` yet,
so remember `2`. See `7`, its complement `2` *is* in `seen` - return `(0, 1)`. For `[3, 2, 4]` target `6`,
the pair is `2 + 4`, found at indices `(1, 2)`. Target `100` has no pair, so `None`. Each number is looked
at once, and each "have I seen the complement?" check is an `O(1)` hash lookup - the whole thing is `O(n)`.

⚠️ **Gotcha.** Store each number in `seen` *after* checking for its complement, not before. Check first,
then insert. If you insert `x` first and the target happens to be `2 * x`, the number would match itself and
report a bogus pair of one element counted twice.

## The one-pass two-sum, in other languages

The pattern travels cleanly: a hash map from value to index, one loop, check-then-insert. Each language
brings its own map type and its own way of saying "not found."

[[codegroup One-Pass Two-Sum]]

```python
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return (seen[need], i)
        seen[x] = i
    return None
```

```javascript
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}
```

```typescript
function twoSum(nums: number[], target: number): [number, number] | null {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i], i);
  }
  return null;
}
```

```java
static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) return new int[]{seen.get(need), i};
        seen.put(nums[i], i);
    }
    return null;
}
```

```cpp
// returns {-1, -1} when no pair is found
std::pair<int, int> two_sum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {-1, -1};
}
```

```go
func twoSum(nums []int, target int) (int, int, bool) {
    seen := make(map[int]int)
    for i, x := range nums {
        need := target - x
        if j, ok := seen[need]; ok {
            return j, i, true
        }
        seen[x] = i
    }
    return 0, 0, false
}
```

```rust
use std::collections::HashMap;

fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &x) in nums.iter().enumerate() {
        let need = target - x;
        if let Some(&j) = seen.get(&need) {
            return Some((j, i));
        }
        seen.insert(x, i);
    }
    None
}
```

[[/codegroup]]

Every version trades a little memory (the `seen` map) for a lot of speed (`O(n²)` down to `O(n)`). That
trade - **remember more so you can scan less** - is the beating heart of nearly every hash-map speedup.

```quiz
[
  {
    "q": "In the one-pass two-sum, what is the \"complement\" the code looks up in the hash map?",
    "choices": ["The next number in the list", "target - x, the value that would complete the pair with the current number", "The largest number seen so far", "The index of x"],
    "answer": 1,
    "explain": "For a current number x, the only partner that reaches the target is target - x. Checking whether that complement was already seen finds the pair in one pass."
  },
  {
    "q": "Why must you check for the complement BEFORE inserting the current number into the map?",
    "choices": ["To save memory", "So a number isn't matched with itself when the target equals twice that number", "Because insertion is slower than lookup", "It doesn't matter which order you use"],
    "answer": 1,
    "explain": "If you insert x first and target == 2*x, the lookup would find x itself and report a fake pair. Check-then-insert prevents an element from pairing with itself."
  },
  {
    "q": "What does the hash-map two-sum gain over the two-pointer version?",
    "choices": ["It uses less memory", "It works on unsorted input without sorting, preserving the original indices", "It is O(log n)", "It never needs a loop"],
    "answer": 1,
    "explain": "The two-pointer approach needs sorted data (which scrambles indices). The hash map runs in one O(n) pass on unsorted input and returns the original positions."
  }
]
```


---

# Sets, Membership & Dedup

The last piece is the **set**. A set is just a hash map that stores keys and no values - so it inherits the
same `O(1)` average membership test, minus the bookkeeping of associated data. Whenever the only question is
*"have I seen this before?"*, a set is the right tool.

## Membership: "is this in the collection?"

Testing membership against a set is constant time, the same buckets-and-hash idea from Phase 1. Against a
list it would be a linear scan.

```python runnable
banned = {"root", "admin", "guest"}   # a set literal

print("admin" in banned)
print("alice" in banned)
```
```console
True
False
```
*What just happened:* each `in` test hashed the string and checked one bucket - no walking the collection.
For a handful of names it hardly matters, but for a blocklist of a million entries checked on every request,
set-vs-list is the difference between instant and sluggish.

## De-duplication that preserves order

Need the unique items, in the order they first appeared? Walk once, keeping a set of what you've already
emitted. The set answers "seen it?" in `O(1)`; the result list keeps the original order.

```python runnable
def dedupe(items):
    seen = set()
    result = []
    for x in items:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

print(dedupe([3, 1, 3, 2, 1, 1, 5]))
```
```console
[3, 1, 2, 5]
```
*What just happened:* the first time each value shows up it's added to both `seen` and `result`; every later
repeat is caught by `x not in seen` and skipped. One pass, order preserved. (If you *don't* care about
order, `list(set(items))` is the one-liner - but it may reorder the elements, for reasons we hit at the
bottom of this phase.)

## Finding the first duplicate

Same set, slightly different question: what's the first value that repeats? Return it the moment you see a
value already in the set.

```python runnable
def first_duplicate(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_duplicate([2, 4, 3, 4, 5, 2]))
```
```console
4
```
*What just happened:* `2`, `4`, `3` all go into `seen` as first sightings. The next `4` is already there, so
it's returned immediately - the scan stops early instead of running to the end. `2` also repeats later, but
`4`'s repeat comes first.

## Gotcha 1: keys (and set members) must be hashable

A hash map can only hash things that don't change - so **mutable** values like lists and dicts can't be keys
or set members. Immutable ones (numbers, strings, tuples) are fine.

```python runnable
seen = set()
seen.add((1, 2))          # a tuple is immutable -> hashable, fine
print((1, 2) in seen)

try:
    seen.add([1, 2])      # a list is mutable -> unhashable
    print("added a list?!")
except TypeError:
    print("Cannot add a list: unhashable type")
```
```console
True
Cannot add a list: unhashable type
```
*What just happened:* the tuple `(1, 2)` hashes fine and goes in. Trying to add the list `[1, 2]` raises a
`TypeError` for an unhashable type - because a list can change after insertion, its hash would go stale and
the map could never find it again. The fix when you need a list-like key is to convert it to a tuple first.

## Gotcha 2: the worst case really is O(n)

"`O(1)` average" is a promise about the *typical* case. If many keys collide into the same bucket, the map
degrades toward a linear scan of that bucket. In normal use this never bites - hash functions spread keys
well - but it's why the guarantee is "average," not "always." For adversarial input (a service where users
control keys), it's a real, if rare, concern.

## Gotcha 3: don't rely on set ordering

A Python `dict` preserves **insertion order** (guaranteed since Python 3.7). A `set` does **not** - its
iteration order follows the internal bucket layout, which you shouldn't depend on.

```python runnable
nums = {30, 10, 20, 50, 40}   # a set, not sorted, not insertion-ordered
print(nums)
print(sorted(nums))           # ask explicitly if you want an order
```
```console
{50, 20, 40, 10, 30}
[10, 20, 30, 40, 50]
```
*What just happened:* the set prints in some bucket-driven order that is neither sorted nor the order written
- and that exact ordering is an implementation detail you should never build logic on. When order matters,
be explicit: use `sorted(...)` for sorted output, or the order-preserving `dedupe` from earlier for
first-seen order. (Your printed line for the set above may differ from what's shown here, which is exactly
the point.)

💡 **Key point.** Reach for a **set** when you only need "seen it or not," a **dict** when you need to
associate a value (a count, an index, an object) with each key, and a **list** when order and duplicates both
matter. Picking the right one is most of what makes hash-based code fast *and* correct.

```quiz
[
  {
    "q": "Why can't a Python list be used as a set member or dict key?",
    "choices": ["Lists are too big", "Lists are mutable, so their hash could change and the map could no longer find them - they're unhashable", "Lists are slower than tuples", "It's only a style rule, not enforced"],
    "answer": 1,
    "explain": "Hash-based structures need a stable hash. A mutable list could change after insertion, invalidating its hash, so Python forbids it with `TypeError: unhashable type`."
  },
  {
    "q": "You need the unique items from a list, in the order they first appeared. What's the safest approach?",
    "choices": ["list(set(items)) - it always keeps order", "Walk once with a `seen` set, appending each first-seen item to a result list", "Sort the list, then remove neighbors", "There's no way to preserve order"],
    "answer": 1,
    "explain": "`list(set(...))` may reorder because set iteration order isn't guaranteed. A `seen` set plus a result list keeps O(1) membership checks while preserving first-seen order."
  }
]
```