Wählen Sie Schlüsselmenge, Hash-Funktion und Tabellengrösse und sehen Sie, wie sich die Schlüssel auf die Buckets verteilen. Die Hashtabelle arbeitet mit Chaining.
Das Prinzip
Eine Hashtabelle speichert einen Schlüssel k im Bucket h(k). Landen mehrere Schlüssel im selben Bucket (Kollision), werden sie dort in einer Liste verkettet (Chaining). Eine Suche kostet so viele Vergleiche, wie der Bucket Einträge hat. Das ist nur dann schnell, wenn sich die Schlüssel gleichmässig verteilen.
Die Simulation vergleicht drei Hash-Funktionen:
| Hash-Funktion | Formel | Besonderheit |
|---|---|---|
| Division | h(k) = k mod m | Einfach, aber empfindlich gegenüber der Wahl von m |
| Multiplikationsmethode | h(k) = ⌊m · (k·A mod 1)⌋ mit A = (√5 − 1)/2 | m darf eine Zweierpotenz sein |
| Universal Hashing | h(k) = ((a·k + b) mod p) mod m | a, b zufällig: Keine Schlüsselmenge ist für alle Wahlen schlecht |
Was die Simulation zeigt
Szenario 2 hat 10 000 Schlüssel, die alle auf 123 enden (i · 1000 + 123). Bei k mod 10 landen alle im selben Bucket: Es ist nur 1 von 10 Buckets belegt und die Suche degeneriert zur linearen Suche. Auch m = 100 oder m = 1000 helfen nicht, denn alle drei Werte teilen die 1000. Erst eine zu den Schlüsseln teilerfremde Grösse wie die Primzahl 10 007 verteilt gut. Multiplikationsmethode und Universal Hashing verteilen auch mit m = 1024 gut.
Python-Code
import math
import random
def hash_division(key, m):
return key % m
A = (math.sqrt(5) - 1) / 2 # Knuth-Konstante
def hash_multiplication(key, m):
return int(m * ((key * A) % 1))
P = 2**31 - 1 # Primzahl
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: pro Bucket eine Liste
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]
Ausprobieren:
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__, "belegte Buckets:", sum(1 for c in d if c), "grösster Bucket:", max(d))