Hash Map

Watch keys get hashed character-by-character, mapped to buckets, and chained on collision. O(1) average lookup, demystified.

Hash Map

A hash map stores key-value pairs in a bucket array. A hash function maps any key to a bucket index in O(1). Collisions use separate chaining, each bucket is a linked list.

djb2(key): h=5381; for c in key: h = (h×33) XOR ord(c);

index = djb2(key) % capacity

💡Simplification: This shows chains as linked lists. In Java's HashMap, chains automatically convert to a red-black TreeMap once length > 8.

Key

Value

Target

Load Factor0/8 = 0.00

Capacity: 8Entries: 0Used: 0/8Max Chain: 0

Hash Trace, djb2

Run SET / GET / DELETE to see the hash computation…

[0]

null

[1]

null

[2]

null

[3]

null

[4]

null

[5]

null

[6]

null

[7]

null

PseudocodeSET

function set(key, value):

  h = djb2(key) % capacity

  for e in buckets[h]:

    if e.key == key:

      e.value = value // update

      return

  buckets[h].append({key, value})

n++

  if n/capacity >= 0.75: resize()

Console Output

0 entries

>Run an operation to see output…