How Hashing Works

Imagine you have a list of a million records and you need to find one by name. Going through them one by one is slow — on average you'd check half a million records. Even a smarter approach like binary search still takes about 20 comparisons.

What if you could jump directly to the right record in one step?

That is what hashing does. Instead of searching for where a key lives, you calculate where it lives. A hash function is a formula that takes your key — a name, a number, anything — and turns it into an array index. You go straight to that index. No searching.

The whole idea in one line: key → hash function → index → look there.

Why We Need Hashing at All

Suppose you store user records in a plain array:

users = [
  { key: "alice", email: "alice@mail.com" },
  { key: "bob",   email: "bob@mail.com" },
  { key: "carol", email: "carol@mail.com" },
  ...and 999,997 more...
]

To find Carol, you start at index 0 and check each key. On average, 500,000 comparisons. That is way too slow for a system with thousands of lookups per second.

How a Hash Function Works

For string keys, one simple approach is to add up the character codes of each letter:

function simpleHash(key, tableSize):
    total = 0
    for each character c in key:
        total = total + charCode(c)
    return total mod tableSize

Let's trace this for the key "cat" with table size 10:

So "cat" goes in slot 2. Next time someone looks up "cat", we run the same formula, get 2, and go straight to slot 2.

Shrinking the Number Down with Modulo

The hash formula might produce a big number — say 4,738,291. But if our table only has 100 slots, we use the modulo operator to bring it into range:

4738291 mod 100 = 91

Modulo gives us the remainder after dividing. The result is always between 0 and tableSize - 1.

What Makes a Good Hash Function

1. Deterministic — Same key always gives the same index. If hash("alice") gives 7 today, it must give 7 every time.

1. Spreads values evenly — Keys should land in different slots as much as possible. If everything piles into the same 10 slots, those slots get slow to search through.

1. Fast to compute — The whole point is to avoid slow searching. If computing the hash is slow, you've gained nothing.

A Problem with the Simple Sum

The simple character-sum approach has one bad flaw: anagrams like "cat", "act", and "tac" all have the same character sum (99 + 97 + 116 = 312), so they all land in the same slot — even though they are different words.

A better approach multiplies each character by a different number based on its position:

function betterHash(key, tableSize):
    total = 0
    for i = 0 to length(key) - 1:
        total = total + charCode(key[i]) * (31 to the power of i)
    return total mod tableSize

Now "cat" and "act" produce different totals because position matters.

Collisions Are Unavoidable

No matter how good your hash function is, collisions will happen. If you have 100 slots and you insert 101 keys, at least two must share a slot — there simply are not enough slots for every key to have its own.

In practice collisions start happening sooner than you'd expect. With 100 slots, you'll likely see your first collision around your 13th or 14th insertion. It's similar to the birthday problem — in a room of 23 people, there's a 50% chance two share a birthday, even though there are 365 days.

There are two main ways to handle collisions:

1. Chaining — Each slot holds a small list. When two keys land on the same slot, both go into that slot's list. Looking up a key means hashing to the slot, then checking the list.

1. Open addressing — When a slot is taken, you look for the next empty slot nearby. Looking up a key means hashing to the slot, then checking nearby slots if the first one does not match.

Chaining is simpler and more common for beginners. We'll build a full hash map using chaining in the next lesson.

The Load Factor

The load factor measures how full your table is:

load factor = number of entries / table size

A load factor of 0.75 means the table is 75% full. As the table fills up, collisions happen more often and lookups slow down. Most hash maps automatically resize — double the table size and move everything over — when the load factor gets too high. The typical threshold is 0.75.

Example 1: Hashing integers

tableSize = 10
hash(42)  = 42 mod 10 = 2
hash(17)  = 17 mod 10 = 7
hash(102) = 102 mod 10 = 2    // collision with 42!
hash(35)  = 35 mod 10 = 5

Example 2: Collision pile-up with a small table

Insert: apple, banana, cherry, date, fig, grape
Table size: 5
​
Suppose the hash values work out to:
  apple    -> 2
  banana   -> 0
  cherry   -> 2  (collision with apple)
  date     -> 3
  fig      -> 2  (collision with apple and cherry)
  grape    -> 4
​
Using chaining:
​
Index 0: [banana]
Index 1: (empty)
Index 2: [apple] -> [cherry] -> [fig]
Index 3: [date]
Index 4: [grape]
​
Looking up "fig" means: hash to slot 2, then walk 3 nodes.
This is why we resize when the table gets too full.