Hash Table — Talent Factory

Choose a key set, a hash function and a table size, and see how the keys spread across the buckets. The hash table uses chaining.

The principle

A hash table stores a key k in bucket h(k). If several keys land in the same bucket (a collision), they are chained in a list there (chaining). A search costs as many comparisons as the bucket has entries. That is only fast if the keys spread evenly.

The simulation compares three hash functions:

Hash function	Formula	Notes
Division	h(k) = k mod m	Simple, but sensitive to the choice of m
Multiplication method	h(k) = ⌊m · (k·A mod 1)⌋ with A = (√5 − 1)/2	m may be a power of two
Universal hashing	h(k) = ((a·k + b) mod p) mod m	a, b random: no key set is bad for all choices

What the simulation shows

Scenario 2 has 10,000 keys that all end in 123 (i · 1000 + 123). With k mod 10 they all land in the same bucket: only 1 of 10 buckets is used and the search degenerates into a linear search. Using m = 100 or m = 1000 does not help either, because all three values divide 1000. Only a table size that is coprime to the keys, such as the prime 10,007, spreads them well. The multiplication method and universal hashing also spread well with m = 1024.

Python code

import math
import random


def hash_division(key, m):
    return key % m


A = (math.sqrt(5) - 1) / 2                    # Knuth's constant


def hash_multiplication(key, m):
    return int(m * ((key * A) % 1))


P = 2**31 - 1                                 # prime
a, b = random.randrange(1, P), random.randrange(P)


def hash_universal(key, m):
    return ((a * key + b) % P) % m


class HashTable:
    def __init__(self, m, hash_func):
        self.m, self.hash_func = m, hash_func
        self.buckets = [[] for _ in range(m)]  # chaining: one list per bucket

    def insert(self, key):
        bucket = self.buckets[self.hash_func(key, self.m)]
        if key not in bucket:
            bucket.append(key)

    def search(self, key):
        return key in self.buckets[self.hash_func(key, self.m)]

    def distribution(self):
        return [len(bucket) for bucket in self.buckets]

Try it out:

keys = [i * 1000 + 123 for i in range(10_000)]
for m, f in [(10, hash_division), (10007, hash_division), (1024, hash_multiplication)]:
    table = HashTable(m, f)
    for k in keys:
        table.insert(k)
    d = table.distribution()
    print(m, f.__name__, "occupied buckets:", sum(1 for c in d if c), "largest bucket:", max(d))