Vorteil von auf Primzahlen skalierten Hashmaps?

[Namenloser]

Hallo,

ich implementiere zur Zeit eine Hashmap. Ich habe mir die Hashmap von alzaimar schon angeschaut, allerdings funktioniert die nur für normale Strings, ich brauche das ganze aber für WideStrings. Leider gibt es keinen Vorfahren, von dem man ableiten könnte und Copy-Paste mag ich nicht - dann lieber gleich ordentlich. Also habe ich angefangen, selbst eine Hashmap zu programmieren.

Da ich nicht furchtbar viel Ahnung von Hashmaps habe, benutze ich alzaimars Code aber teilweise als Referenz - und da ist mir aufgefallen, dass die Hashmap-Größe immer auf eine Primzahl hochskaliert wird. Auf Wikipedia konnte ich nur den nicht näher spezifizierten Hinweis finden, dass das bei manchen Hashs von Vorteil sein soll.

Nachdem ich jetzt mithilfe eines selbst geschriebenen Python-Scripts schon verschiedene Tests durchgeführt habe, konnte ich aber keinen Vorteil erkennen. Deshalb die Frage an die Informatiker unter euch: Was ist der Vorteil, wenn die Größe der Hashmap eine Primzahl ist?

Danke.

[s.h.a.r.k]

Soweit ich das noch weiß, hat das mit dem Problem der Kollision zu tun, wobei das ja wiederrum von der Schlüsselberechnung abhängig ist.

[idefix2]

A Priori hat eine Primzahlgrösse keine Vorteile, es hängt von den verwendeten Hashfunktionen ab.

Aufgabe einer guten Hashfunktion ist es, die vorhandenen Daten möglichst gleichmässig auf die Hashtabelle aufzuteilen, damit nicht an manchen Hashfunktionswerten viele Datensätze hängen und an anderen keine. Es gibt Algorithmen, die für eine optimale Verteilung primzahl-grosse Tabellen brauchen (ist schon lange her, dass ich mich bei meinem Studium am Rande damit beschäftigt habe). Wenn aber keine derartige Hashfunktion verwendet wird, kann u.U. eine unrunde Hashtabellengrösse sogar Nachteile hinsichtlich der gleichmässigen Verteilung bringen.

edit: Ich glaube, mich zu erinnern, dass das aber nur ein Thema ist, wenn eine "Familie" von Hashfunktionen verwendet wird, um die Erzeugung von Listen zu vermeiden: Bei einer Kollision wird nicht an dem Knoten eine Liste gebildet, sondern mit Hilfe von weiteren Hashfunktionen nach einem freien Platz in der Hashtabelle gesucht. Solche "Hashfunktionsfamilien" brauchen oft primzahlgrosse Tabellen, um zu verhindern, dass "Ballungen" von Werten entstehen, die sich negativ auf die Performance auswirken.

edit 2: Weil mich das Thema Hashtabellen zufällig gerade auch betrifft, habe ich ein bisschen nachgeforscht und einen ganz interessanten Link: http://www.partow.net/programming/hashfunctions/ [OT: warum mir der Editor die URL-Tags nicht anbietet, versteh ich nicht] gefunden. Es zahlt sich aus, sich das anzuschauen, wenn man in das Thema einsteigen will.

[Namenloser]

Hallo,

erst mal Danke euch beiden für eure Antworten.

Ich hatte schon vermutet, dass es irgendwas mit der gleichmäßigen Verteilung zu tun hat, aber in meinen Tests konnte ich eben keinen Unterschied nachvollziehen.

1. Wie bekomme ich denn heraus, ob ein Hash-Algorithmus nur bei einer Primzahl-Größe gute Werte liefert? Hashfunktionsfamilien habe ich nicht vor zu benutzen, das wäre für meinen Zweck wahrscheinlich Overkill.

2. alzaimars Klasse berechnet immer erst einen 32 Bit breiten Hash und "kürzt" diesen dann mithilfe des

Delphi-Quellcode:

mod

-Operators. Ist das eine gute Lösung? Bzw. wäre das vielleicht so ein Fall, wo eine primzahl-große Hashmap von Vorteil ist?

3. Als Alternative fiele mir noch Bitmasking ein, was im Falle einer 2^n-großen Hashmap ja sowieso dasselbe wäre, wenn man immer die niederwertigsten Bits maskiert. Da wiederum stellt sich die Frage, was denn besser ist: Immer die niederwertigsten Bits maskieren, oder verteilt über den gesamten Hash Bits herauspicken?

Soweit erst mal meine Fragen.
Danke auch für den Link, ich werde mir das mal zu Gemüte führen. Vielleicht beantworten sich ja einige meiner Fragen schon dadurch.

[xZise]

Zitat:

Zitat von NamenLozer (Beitrag 1034672)

[...]2. alzaimars Klasse berechnet immer erst einen 32 Bit breiten Hash und "kürzt" diesen dann mithilfe des

Delphi-Quellcode:

mod

-Operators. Ist das eine gute Lösung? Bzw. wäre das vielleicht so ein Fall, wo eine primzahl-große Hashmap von Vorteil ist?[...]

Moin, wenn ich mich richtig erinnere gibt es verschiedene Familien von Hashfunktionen. Und eine Arbeitet so.

Ich glaube es ist das hier.

MfG
Fabian

[idefix2]

Wenn Du nur eine Hashfunktion und keine Familie verwendest, ist die Grösse des Hash Arrays ziemlich sicher völlig egal. Primzahlen bringen da keinen Vorteil (aber auch keinen Nachteil). Die Funktion, die in Alzaimars Hashfunktion verwendet wird, verteilt Dir die Bits ohnehin recht gleichmässig über die vollen 32 Bit. Ich denke, es wäre schneller und um nichts schlechter, Hashmaps der Grösse 2 hoch n zu verwenden und die Hash Adresse einfach zu maskieren, statt modulo Primzahl zu operieren. Letzteres würfelt die Bits natürlich nocheinmal gründlich durcheinander, aber ich glaube nicht, dass das die Verteilung verbessert. Ich würde mir einmal die Verteilung der Werte an Hand von Echtdaten anschauen.

edit: Natürlich fallen beim Maskieren die höherwertigen Bits ganz weg und werden nicht berücksichtigt, aber nachdem die niederwertigen Bits bei dem Algorithmus recht gleichmässig verteilt sein sollten, wird letztlich die Verteilung auch nicht schlechter sein, als wenn man mittels Modulo ungerade Zahl (es muss keine Primzahl sein, weil jede ungerade Zahl ist teilerfremd zu 2 hoch n) alle Bits berücksichtigt. Ausserdem könnte man die höherwerigen Bits berücksichtigen, in dem man z.B. für einen 10 Bit breiten index
x and (x shr 8) and (x shr 16) and (x shr 24) and 1023
verwendet, da spielen dann alle Bits mit.

[Namenloser]

Zitat:

Zitat von idefix2 (Beitrag 1034678)

Wenn Du nur eine Hashfunktion und keine Familie verwendest, ist die Grösse des Hash Arrays ziemlich sicher völlig egal. Primzahlen bringen da keinen Vorteil (aber auch keinen Nachteil). Die Funktion, die in Alzaimars Hashfunktion verwendet wird, verteilt Dir die Bits ohnehin recht gleichmässig über die vollen 32 Bit. Ich denke, es wäre schneller und um nichts schlechter, Hashmaps der Grösse 2 hoch n zu verwenden und die Hash Adresse einfach zu maskieren, statt modulo Primzahl zu operieren. Letzteres würfelt die Bits natürlich nocheinmal gründlich durcheinander, aber ich glaube nicht, dass das die Verteilung verbessert. Ich würde mir einmal die Verteilung der Werte an Hand von Echtdaten anschauen.

Danke für deine Einschätzung.

Zitat:

Zitat von idefix2 (Beitrag 1034678)

Ausserdem könnte man die höherwerigen Bits berücksichtigen, in dem man z.B. für einen 10 Bit breiten index
x and (x shr 8) and (x shr 16) and (x shr 24) and 1023
verwendet, da spielen dann alle Bits mit.

Sicher mit dem

Delphi-Quellcode:

and

? Denn bei

Delphi-Quellcode:

and

ist die Wahrscheinlichkeit, 0 (oder fast 0) als Ergebnis zu erhalten doch ziemlich groß. Würde nicht

Delphi-Quellcode:

xor

mehr Sinn ergeben?

[xZise]

Vermutlich was von beiden ;) Das letzte

Delphi-Quellcode:

and

muss ja sein, damit man nur die untersten 10 bit verwendet.

Aber bei den Restlichen bin ich mir unsicher ob es

Delphi-Quellcode:

xor

tut.

MfG
Fabian

[Namenloser]

Zitat:

Zitat von xZise (Beitrag 1034688)

Vermutlich was von beiden ;) Das letzte

Delphi-Quellcode:

and

muss ja sein, damit man nur die untersten 10 bit verwendet.

Das letzte

Delphi-Quellcode:

and

muss natürlich bleiben ;)

Zitat:

Zitat von xZise (Beitrag 1034688)

Aber bei den Restlichen bin ich mir unsicher ob es

Delphi-Quellcode:

xor

tut.

Am sichersten ist es wahrschenlich, auf solche Spielchen ganz zu verzichten, und davon auszugehen, dass der Hash die Bits gut durchgeschüttelt hat.

[alzaimar]

Hi
Essentiell ist natürlich die Hash-Funktion. Wieso ich Primzahlen als Hashgröße verwende, liegt mit ziemlicher Sicherheit daran, as ich zunächst mit Integer-Hashmaps gearbeitet habe. Ich meine mich zu erinnern, dann auch bei Strings eine Verbesserung ggü einer willkürlichen Verdopplung gemessen habe. Das ist aber mittlerweile so lange her, das ich es nicht mehr genau weiss.

Probiers doch einfach aus.