🔑 HashMap

How a Hash Map Finds a Key

hash the key → mod by bucket count → jump to that slot → walk the short chain

Speed

try: cat, dog, bird, fish, ant, bee, cow, owl — or a missing key like "zebra"

Press Play or Step to look up a key.

char

—

code

—

hash

—

index

—

get(key):
    h = hash(key)                // key → a number
    i = h % buckets.length       // number → an index
    bucket = buckets[i]          // jump — no scanning
    for (k, v) in bucket:        // short chain
        if k === key: return v
    return undefined            // not found

Key comparisons

Bucket

—

Chain length

—

Result

—

Time & Space Complexity

Case	Lookup	Insert	Space
Average (chains stay short)	O(1)	O(1)	O(n)
Worst (everything collides)	O(n)	O(n)	O(n)

You buy time with memory: O(n) extra space to turn an O(n) scan into an O(1) lookup.

Target bucket

Comparing key

Found

Not found