Jenkins' Hash
Created: 19.03.2010 21:18 UTC

Ich schreibe grade aus Langeweile meine eigene ObjC-Runtime (und sie funktioniert auch schon) und habe daher mal ein paar Benchmarks gemacht in Sachen Hashtables, Hashfunktionen, Sondierung und Größen und dabei eine interessante Entdeckung gemacht: Normalerweise geht man ja davon aus, daß man am besten als Größe für die Hashtable eine Primzahl nimmt und dann den Hash modulo der Größe nimmt, um so möglichst wenig Kollisionen zu bekommen. Nun, bei Jenkins' Hash verhält es sich anders: Eine Power of 2 als Größe nehmen und den Hash mit (Größe - 1) zu ANDen ergibt deutlich weniger Kollisionen. Also wenn ihr Jenkins' Hash nehmt (der übrigens wegen seines Avalanche-Verhaltens sehr gut für Hashtables ist): Macht euch garnicht die Mühe, nur Primzahlen als Größe zu nehmen und dann Modulo zu verwenden. Power of 2 und dann mit (Größe - 1) ANDen geht nicht nur schneller, sondern erzeugt auch noch weniger Kollisionen.