AW: Mephisto Phoenix London - Geschwindigkeitsvergleiche + Hash Tables
 

Hi Markus,

Es wäre extrem ungewöhnlich, wenn man das so machen würde, weil man eine Hashtabelle nicht "durchsucht". Der Index, an dem man in der Hashtabelle springt, wird direkt aus dem Hashwert berechnet. Damit hängt der Aufwand sowohl beim Speichern als auch beim Nachschlagen einer Position nicht von der Größe der Hashtabelle ab. Lediglich, wenn man die gesamte Hashtabelle schreibt, etwa zwecks Löschen, dann dauert das proportional zur Größe.

Es wäre aber eine andere Falle denkbar. Wenn die Anzahl der Einträge eine Zweierpotenz ist, dann kann man die entsprechenden untersten Bits des Hashes als Index verwenden. Das ist eine AND-Operation, die auch auf den damaligen CPUs schon schnell war, IIRC 6 Takte beim 68k.

Ist die Anzahl der Einträge keine Zweierpotenz, dann kann man stattdessen eine Division mit Rest machen und den Rest als Index verwenden. Allerdings kostet eine Division etwa 140 Takte. Oder man bastelt eine Lösung, die stattdessen die Treffer ungleichmäßig verteilt, was dann wieder schnell ist, aber die Auslastung in Teilen der Tabelle ungleichmäßig macht und dort zu weniger Effektivität führt.

Ob die Größe der Hashtabelle selber dafür eine Zweierpotenz sein muß, hängt davon ab, ob der einzelne Eintrag die Größe einer Zweierpotenz hat, was von der Engine abhängt. Klar ist aber, wenn 2MB die Anzahl von Einträgen als Zweierpotenz hat, dann kann das für 3MB nicht der Fall sein, weil eine Zweierpotenz mal 1.5 keine Zweierpotenz ergibt.

AW: Mephisto Phoenix London - Geschwindigkeitsvergleiche + Hash Tables
 

Hallo Rasmus,
vielen Dank für die sehr gute Erklärung.

viele Grüße
Markus