Hashing: How Dictionaries Find Things Instantly

The question hashing answers

Suppose you have 10 lakh student records and you need to look up a roll number.

With an unsorted array, you scan: O(n), up to ten lakh comparisons. With a sorted array and binary search: O(log n), about 20 comparisons — much better, but you had to sort first, and every insertion afterwards costs O(n).

Hashing gives you something better: find, insert and delete in roughly O(1), on average, with no sorting at all.

The idea is genuinely clever, and once you see it you will understand why dict and set are everywhere in Python.

The core idea

Arrays already have O(1) lookup — if you know the index. The problem with a roll number like "CS21B047" is that it is not an index.

So: compute an index from the key.

A hash function takes a key and returns a number. Take that number modulo the table size, and you have an index into an array.

key "CS21B047"  --hash-->  8834712  --mod 10-->  index 2

table:
 0: -
 1: -
 2: ("CS21B047", "Rahul")
 3: -
 ...

To look the key up again, you run the same hash function, get the same index, and jump straight there. No searching. One hash computation and one array access.

That is the entire trick. Everything else is dealing with the ways it goes wrong.

def simple_hash(key, table_size):
    total = 0
    for ch in key:
        total += ord(ch)          # ord gives the character's numeric code
    return total % table_size

names = ["Rahul", "Priya", "Amit", "Sneha", "Vikram"]
for n in names:
    print(n.ljust(8), "-> bucket", simple_hash(n, 7))

This hash function is deliberately weak — summing character codes means "abc" and "cba" collide. Real hash functions mix the position of each character in as well. But the shape is right: key in, index out, same answer every time.

Collisions

Two different keys can hash to the same index. This is not a bug you can eliminate — it is unavoidable. If you have 10 buckets and 11 keys, at least two must share.

There are two standard ways to handle it.

Chaining. Each bucket holds a small list. Colliding keys are appended to that list. On lookup, hash to the bucket and then scan its short list. This is the easier method to understand and to implement.

Open addressing. Keep one key per slot. On collision, probe forward to the next free slot by a fixed rule. Lookup follows the same probing sequence.

class HashTable:
    def __init__(self, size=7):
        self.size = size
        self.buckets = [[] for _ in range(size)]   # chaining

    def _index(self, key):
        total = 0
        for ch in str(key):
            total = total * 31 + ord(ch)           # mixing in position
        return total % self.size

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:                     # key exists - update it
                pair[1] = value
                return
        bucket.append([key, value])

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:
                return pair[1]
        return None

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket.pop(i)
                return True
        return False

ht = HashTable(5)
ht.put("Rahul", 88)
ht.put("Priya", 92)
ht.put("Amit", 74)
ht.put("Sneha", 81)

for i, b in enumerate(ht.buckets):
    print("bucket", i, ":", b)

print()
print("Marks of Priya:", ht.get("Priya"))
print("Marks of Nobody:", ht.get("Nobody"))
ht.put("Priya", 95)
print("Priya after update:", ht.get("Priya"))
ht.remove("Amit")
print("Amit after removal:", ht.get("Amit"))

Run it and look at the bucket printout. Some buckets hold two entries, some hold none. That unevenness is normal.

Why lookup is "about" O(1)

If keys spread evenly across b buckets, each bucket holds roughly n/b entries. Keep b growing with n and that average stays a small constant — so a lookup is one hash plus a scan of a very short list. That is O(1) average.

The worst case is O(n): if every key hashes to the same bucket, the table degenerates into one long list. Good hash functions and automatic resizing make this vanishingly unlikely with ordinary data, but the guarantee is average, not absolute. This is why we say "about" O(1).

Read that table's last two rows carefully. Hash tables are unbeatable at "is this key present" and useless at "what is the smallest key" or "give me everything in order". Choosing a structure means knowing which questions you will ask.

Python's dict and set

You do not have to build hash tables — Python gives you two, and they are excellent.

# A dict maps keys to values
marks = {"Rahul": 88, "Priya": 92, "Amit": 74}

print("Priya's marks:", marks["Priya"])
print("Is Sneha present?", "Sneha" in marks)
print("Safe lookup:", marks.get("Sneha", "not enrolled"))

marks["Sneha"] = 81
print("After adding Sneha:", marks)

# Counting frequencies - the classic dict use
text = "the quick brown fox jumps over the lazy dog the end"
counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1
print("Word counts:", counts)

# A set stores unique values with O(1) membership tests
roll_numbers = [12, 7, 12, 19, 7, 25]
unique = set(roll_numbers)
print("Unique rolls:", sorted(unique))
print("Is 19 present?", 19 in unique)
print("Duplicates existed?", len(roll_numbers) != len(unique))

x in some_set is O(1). x in some_list is O(n). That single difference turns many O(n^2) solutions into O(n) ones.

When hashing beats sorting

Use hashing when you ask membership questions ("have I seen this before?"), count frequencies, group items by a key, or need fast insert and delete with no ordering requirement.

Use sorting when you need items in order, need the smallest or largest, need range queries ("all marks between 60 and 80"), or need to output results in a predictable sequence.

Here is the classic comparison — find duplicates:

rolls = [104, 217, 350, 104, 892, 217, 401]

# Approach A: nested loops - O(n^2)
dup_a = []
for i in range(len(rolls)):
    for j in range(i + 1, len(rolls)):
        if rolls[i] == rolls[j] and rolls[i] not in dup_a:
            dup_a.append(rolls[i])
print("Nested loops found:", sorted(dup_a))

# Approach B: a set - O(n)
seen = set()
dup_b = set()
for r in rolls:
    if r in seen:
        dup_b.add(r)
    seen.add(r)
print("Set approach found:", sorted(dup_b))

print("Same answer, but B does one pass instead of n*n comparisons.")

Both give the same result on 7 items. On 1,00,000 items, approach A does about five billion comparisons and approach B does one lakh. That is the difference hashing makes.

What can be a key

A key must be hashable, which in practice means immutable. Numbers, strings and tuples work. Lists and dictionaries do not, because if you changed a list after using it as a key, its hash would change and the entry would become unreachable.

Common mistakes

Using a list as a dictionary key. TypeError: unhashable type: 'list'. Convert it to a tuple first.

Expecting a fixed order. Python dictionaries preserve insertion order, not sorted order. Never assume keys come out sorted; use sorted(d) when you need that.

Using d[key] for a key that might not exist. That raises KeyError. Use d.get(key, default) or check with in first.

Modifying a dict while iterating over it. Adding or removing keys mid-loop raises RuntimeError. Iterate over list(d.keys()) if you must change the dict.

Keeping a list where a set belongs. If your only use of a collection is membership testing, a list makes every check O(n) for no benefit.

Practice

Try the hashing exercises on the practice page — frequency counting and duplicate detection are the ones to start with.