Turning strings into bucket numbers

You use dict all the time. You put something in, you get it back fast. Even with a fat dictionary it rarely feels slow.

Roughly what happens:

hash the key - you get a number
number % bucket_count - that picks a slot
drop (key, value) in that slot
to read it back, hash the key again and look in the same slot

Sometimes two keys land in the same slot. That is a collision. Easiest fix: each slot holds a list. Append to the list, scan it on lookup. Python's built-in dict is smarter than this toy version, but same idea.

Here is a tiny hash in Python, plus output so you can sanity-check it.

djb2

Small string hash, easy to read:

PYTHON

def djb2(key: str) -> int:
    hash = 5381
    for char in key:
        hash = ((hash << 5) + hash + ord(char)) & 0xFFFFFFFF
    return hash

Try a couple keys:

PYTHON

print(hex(djb2("cache")))
print(hex(djb2("index")))

Plain Text

0xf355db9
0xfa9159d

Flip one letter and the hash moves:

PYTHON

print(hex(djb2("route")))
print(hex(djb2("rouge")))

Plain Text

0x104cc8b4
0x104cc707

hash to bucket

Raw hash is too big to use as a list index. Modulo it:

PYTHON

def bucket_index(hash: int, size: int) -> int:
    return hash % size


size = 8
for word in ["cache", "index", "ab", "ba"]:
    h = djb2(word)
    print(word, hex(h), "- bucket", bucket_index(h, size))

Plain Text

cache 0xf355db9 - bucket 1
index 0xfa9159d - bucket 5
ab 0x597728 - bucket 0
ba 0x597748 - bucket 0

"ab" and "ba" both end up in bucket 0. Different strings, same slot.

HashMap

One list per bucket. Collisions just mean more items in that list.

PYTHON

class HashMap:
    def __init__(self, size: int = 8):
        self.buckets: list[list[tuple[object, object]]] = [[] for _ in range(size)]

    def _index(self, key) -> int:
        return bucket_index(djb2(str(key)), len(self.buckets))

    def set(self, key, value) -> None:
        i = self._index(key)
        for j, (k, _) in enumerate(self.buckets[i]):
            if k == key:
                self.buckets[i][j] = (key, value)
                return
        self.buckets[i].append((key, value))

    def get(self, key, default=None):
        i = self._index(key)
        for k, v in self.buckets[i]:
            if k == key:
                return v
        return default


m = HashMap(8)
m.set("cache", 42)
m.set("index", 99)
m.set("ab", 1)
m.set("ba", 2)

print(m.get("cache"))
print(m.get("ba"))
print(m.get("missing"))

for i, bucket in enumerate(m.buckets):
    if bucket:
        print(f"bucket[{i}]: {bucket}")

OUTPUT

42
2
None
bucket[0]: [('ab', 1), ('ba', 2)]
bucket[1]: [('cache', 42)]
bucket[5]: [('index', 99)]

get("ba") still finds 2. Hash "ba", bucket 0, walk the list, done.