Skills101

AdvancedData Structures & Algorithms · Lesson 22 of 25 · Updated ·

How Hashing Works — Hash Functions, Collisions and Load Factor

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

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.

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])
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.

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)
[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

OperationAverageWorst case
insert / lookup / deleteO(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.

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)));
    }
}
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.
seen = {(0, 1): "visited"}
print(seen[(0, 1)])
key = [0, 1]
print(seen.get(tuple(key)))
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 what you learned

📝 Quiz: How Hashing Works5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →