Hash Functions

The problem

You're building a coat check at a busy theater. A thousand guests arrive, hand you a coat, and later come back for it. If you just pile the coats up, finding one guest's coat means digging through the whole heap — a fresh search every single time.

So you buy a wall of numbered hooks. Now the real question is the hard one: when a guest named ria_codes hands you a coat, which hook do you hang it on? You need a rule that turns a name into a hook number — and gives you back the same number when she returns.

A first attempt

The easy rule: keep a running list, and give each new guest the next free hook. ria_codes gets hook 0, fahim gets hook 1, and so on.

But now retrieval is broken again. When ria_codes comes back, which hook was hers? You don't know — so you scan the list to find her name, then read off the hook. That scan is O(n), exactly the pile-of-coats problem you were trying to escape. Assigning numbers in arrival order tells you nothing about where to look later.

The fix has to come from the name itself. The number must be computed from the key, not handed out in sequence.

The insight

What if the name is the address? Take the characters of ria_codes, mash them into a single number with arithmetic, then fold that number down to a valid hook. Same name in, same number out — every time, without any list to consult.

That rule is a hash function: a deterministic function that maps a key of any size to a fixed-size number, its hash code. Reduce that code modulo the number of hooks and you get a slot. The name computes its own address.

How it works

Here's the mixing, character by character, for a tiny 8-hook wall:

key = "cat",  acc starts at 7
 'c' (99):   acc = 7*31 + 99   = 316
 'a' (97):   acc = 316*31 + 97 = 9893
 't'(116):   acc = 9893*31 +116 = 306799
 slot = 306799 % 8 = 7   ← "cat" hangs on hook 7

Change one letter and the whole number swerves — that avalanche is what scatters keys across the hooks instead of clumping them.

The code

A classic string hash: fold each character into an accumulator, then reduce to a slot.

def hash_code(key: str) -> int:
    h = 7
    for ch in key:
        h = (h * 31 + ord(ch)) & 0xFFFFFFFF  # keep it 32-bit
    return h

def slot(key: str, table_size: int) -> int:
    return hash_code(key) % table_size

function hashCode(key: string): number {
  let h = 7;
  for (const ch of key) {
    h = (Math.imul(h, 31) + ch.charCodeAt(0)) | 0; // 32-bit wrap
  }
  return h >>> 0; // treat as unsigned
}

function slot(key: string, tableSize: number): number {
  return hashCode(key) % tableSize;
}

int hashCode(String key) {
    int h = 7;
    for (int i = 0; i < key.length(); i++) {
        h = h * 31 + key.charAt(i); // int overflow wraps naturally
    }
    return h;
}

int slot(String key, int tableSize) {
    return Math.floorMod(hashCode(key), tableSize);
}

#include <stddef.h>

unsigned int hash_code(const char *key) {
    unsigned int h = 7;
    for (const char *p = key; *p; p++) {
        h = h * 31u + (unsigned char)*p; // unsigned wraps by spec
    }
    return h;
}

size_t slot(const char *key, size_t table_size) {
    return hash_code(key) % table_size;
}

#include <string>
#include <cstddef>

unsigned int hash_code(const std::string &key) {
    unsigned int h = 7;
    for (unsigned char ch : key) {
        h = h * 31u + ch; // unsigned wraps by spec
    }
    return h;
}

std::size_t slot(const std::string &key, std::size_t table_size) {
    return hash_code(key) % table_size;
}

Computing the code touches every character once, so hashing a key of length k is O(k). For short keys we treat that as effectively constant — which is why a hash-table lookup is called O(1).

Complexity

When to use it

Practice

Recap

• A hash function deterministically turns a key into a fixed-size number, which you fold modulo the table size into a slot — the key computes its own address.
• Good hashes are fast and spread keys uniformly; multiplying by a prime makes position matter so anagrams don't collide.
• Collisions are mathematically inevitable; the hash's job is to make them rare, and the table's job is to resolve them.