# How Hashing Works — Hash Functions, Collisions and Load Factor

Source: https://skills101.in/learn/dsa/dsa-how-hashing-works — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

Hash maps (`dict` in Python, `HashMap` in Java) are the most useful data structure in interviews: they turn many O(n²) solutions into O(n). Interviewers then ask the natural follow-up — **"how does a hash map work inside?"** This lesson answers it, and builds a small hash map so you can see every step.

## 1. The idea: compute where the key lives

An array gives O(1) access **if you know the index**. A hash table turns any key into an index:

1. A **hash function** turns the key into a number: `hash("asha")`.
2. That number is reduced to a bucket: `index = hash % number_of_buckets`.
3. The value is stored in that bucket. To look it up later, compute the same index again — no searching.

![A hash table with 5 buckets: vikram goes to bucket 0, neha to 2, asha and meena both to bucket 3 forming a chain, and ravi to bucket 4; the hash here is the sum of letter codes mod 5](https://skills101.in/learn-img/dsa/hash-buckets.svg)

A good hash function is **fast**, always gives the **same** number for the same key, and spreads different keys **evenly** over the buckets.

## 2. Collisions

Two different keys can land in the **same bucket** — above, `asha` (413) and `meena` (518) both give 3 when divided by 5. That is a **collision**, and it is unavoidable: there are far more possible keys than buckets. There are two classic ways to handle it.

### Chaining

Each bucket holds a small list. A collision just adds to the list; a lookup scans that one short list.

```python
class ChainedMap:
    def __init__(self, buckets=5):
        self.b = [[] for _ in range(buckets)]

    def _index(self, key):
        return sum(ord(ch) for ch in key) % len(self.b)   # a toy hash, for the demo

    def put(self, key, value):
        chain = self.b[self._index(key)]
        for pair in chain:
            if pair[0] == key:          # key already there: update it
                pair[1] = value
                return
        chain.append([key, value])

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

m = ChainedMap()
for name, marks in [("ravi", 71), ("asha", 85), ("meena", 90), ("vikram", 62), ("neha", 77)]:
    m.put(name, marks)
m.put("asha", 88)
print(m.get("asha"), m.get("meena"), m.get("arjun"))
print([len(chain) for chain in m.b])
```

```text
88 90 None
[1, 0, 1, 2, 1]
```

### Open addressing (linear probing)

No lists: if the bucket is taken, try the **next** bucket, then the next, until a free one is found. Lookups follow the same path. Python's `dict` uses a form of open addressing.

```python
def probe_insert(table, key):
    i = sum(ord(ch) for ch in key) % len(table)
    while table[i] is not None:          # taken: try the next slot
        i = (i + 1) % len(table)
    table[i] = key
    return i

t = [None] * 7
print([probe_insert(t, k) for k in ["ab", "ba", "ca", "ac"]])
print(t)
```

```text
[6, 0, 1, 2]
['ba', 'ca', 'ac', None, None, None, 'ab']
```

`"ab"` and `"ba"` have the same letter sum, so `"ba"` collides at slot 6 and moves to slot 0 (wrapping around); `"ca"` and `"ac"` are pushed along as well.

## 3. Load factor and resizing

The **load factor** is `items / buckets`. As it grows, chains get longer (or probe sequences get longer) and lookups slow down. So hash tables **resize**: when the load factor passes a limit — **0.75 in Java's HashMap** — they allocate about twice as many buckets and re-insert every key (**rehashing**).

- A single resize costs O(n), but it happens rarely, so the **amortised** cost of an insert stays O(1).
- If you know the size in advance, create the map with that capacity to skip the resizes.

## 4. Complexity, honestly

| Operation | Average | Worst case |
|---|---|---|
| insert / lookup / delete | **O(1)** | O(n) |

The worst case happens when many keys collide into one bucket — a bad hash function, or deliberately chosen keys. Java 8+ limits the damage: when one bucket's chain grows past 8 entries, it becomes a **balanced tree**, so even the worst case is O(log n) for that bucket.

## 5. Java: hashCode() and equals() must agree

`HashMap` uses `hashCode()` to pick the bucket and `equals()` to find the key inside it. If you override one, override **both**: equal objects **must** have equal hash codes, or the map will look in the wrong bucket.

```java
import java.util.*;

public class Main {
    record Point(int x, int y) {}          // a record writes equals() and hashCode() for you

    static class BadPoint {                // equals() without hashCode(): broken in a HashSet
        int x, y;
        BadPoint(int x, int y) { this.x = x; this.y = y; }
        @Override public boolean equals(Object o) {
            return o instanceof BadPoint p && p.x == x && p.y == y;
        }
    }

    public static void main(String[] args) {
        Set<Point> good = new HashSet<>();
        good.add(new Point(1, 2));
        System.out.println(good.contains(new Point(1, 2)));

        Set<BadPoint> bad = new HashSet<>();
        bad.add(new BadPoint(1, 2));
        System.out.println(bad.contains(new BadPoint(1, 2)));
    }
}
```

```text
true
false
```

`BadPoint` uses the default `hashCode()` (based on the object's identity), so two equal points usually land in different buckets and `contains` says `false`.

**Also:** never change a field that the hash code depends on while the object is inside a `HashMap` or `HashSet` — it would sit in the wrong bucket and become impossible to find.

## 6. Which keys can be hashed?

- Python: only **immutable** values — `str`, `int`, `tuple` — can be dict keys or set items. A `list` can't (`TypeError: unhashable type: 'list'`); convert it to a `tuple`.
- Use a tuple key for pairs and grid cells: `seen[(r, c)] = True`.

```python
seen = {(0, 1): "visited"}
print(seen[(0, 1)])
key = [0, 1]
print(seen.get(tuple(key)))
```

```text
visited
visited
```

## Common mistakes

- Saying a hash map lookup is "always O(1)" — it is O(1) **on average**; the worst case is O(n) (or O(log n) per bucket in Java 8+).
- Overriding `equals()` in Java without `hashCode()`.
- Using a mutable object (a list, or an object you later change) as a key.
- Relying on the iteration order of `HashMap` — it is not sorted and not insertion order (use `LinkedHashMap` or `TreeMap`).

## Quick recap

- Hash function → number → `% buckets` → index; the same key always gives the same bucket.
- Collisions are normal: chaining keeps a list per bucket; open addressing probes the next slots.
- Load factor = items / buckets; past the limit (0.75 in Java) the table doubles and rehashes.
- Average O(1), worst O(n). In Java, `equals()` and `hashCode()` must agree.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-how-hashing-works