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.

[idefix2]

Zitat:

Würde nicht xor mehr Sinn ergeben?

Entschuldige, natürlich habe ich xor gemeint. Bis auf ganz hinten, das letzte and muss bleiben, wie Du richtig geschrieben hast.

Zitat:

Am sichersten ist es wahrschenlich, auf solche Spielchen ganz zu verzichten

Am sichersten ist es, irgend so etwas zu machen, weil damit die niederwertigen Bits von allen Buchstaben des Strings zum Tragen kommen, oder doch mit einer ungeraden Feldgrösse und modulo-Arithmetik zu operieren. Aber notwendig ist es wahrscheinlich nicht.

Die Hashfunktion von Alzaimar rotiert die Zeichen bei jedem Buchstaben 4-Bit-weise nach links, dadurch bleiben, je nach grösse des Hashfeldes, die Hälfte oder mehr der Buchstaben völlig unberücksichtigt, wenn Du einfach nur die höherwertigen Bits "weg-and-est". Das muss nicht unbedingt schaden, aber mit einem xor über alle vier Bytes des Resultats bist Du ebenso auf der sicheren Seite wie mit einem Feld mit ungerader Grösse und Modulo-Arithmetik, wobei die zweite Variante wahrscheinlich geringfügig langsamer sein wird.

[Namenloser]

So :hi:

dank euch habe ich's jetzt geschafft, meine Hashmap zu implementieren. Erst mal habe ich nur die Basisklasse und zum Testen ein normales String-zu-String-Dictionary erstellt. Die von mir eigentlich benötigte Widestring-Objekt-Variante ist noch nicht dabei, sollte sich aber nun recht einfach implementieren lassen.

Ich habe die Hashmap mitsamt Test-Dateien mal angehängt. Nicht wundern, dass im kompilierten Test-Projekt noch ein paar andere Tests angezeigt werden - diese stammen aus meinem Hauptprojekt, wofür ich die Hashmap eigentlich brauche. Ihr könnt sie also einfach ignorieren.

Würde mich über Feedback freuen!

PS: Hat jemand einen Tipp für eine gute WideString-Hashfunktion? Kann/sollte ich dafür die ELF-Hashfunktion weiterbenutzen, oder muss ich die irgendwie anpassen?

[himitsu]

Was soll denn der Hast so für Spezifikationen?

in meinem himXML steckt ein kleiner mutierter WideString-ELF-Hash (ich glaub das war mal einer ... hatte mir dafür mal eine AnsiHash-Funktion angepaßt, welche ich beim Hagen fand)

siehe (am Ende der himXML.pas)

Delphi-Quellcode:

Class Function TXHelper.CalcHash(Const S: TWideString): LongWord;

allerdings hat diese ein paar spezielle Erweiterungen/Anpassungen, aber das läßt sich ja ändern
- einige bestimmte Steuerzeichen (*?\) schalten das Hashen ab
- es kann ein CaseInsensitiver Hash erstellt werden

PS: http://www.delphipraxis.net/137894-e...nicode-ok.html

[Namenloser]

Danke, ich werd's mir mal anschauen.

[idefix2]

Hallo, hab mir Dein Programm angeschaut, es schaut schon recht gut aus.

Die Hashfunktion kannst Du unverändert für Widestrings übernehmen, sie wird dort genausogut funktionieren.

Folgendes würde ich anders machen:

1. Die Suche nach Primzahlen ist beim verwendeten Algorithmus wirklich ganz überflüssig. Es sollte eine zum Wertebereich des Schlüssels teilerfremde Zahl sein. Im Fall des Stringkey ist der Wertebereich 2 hoch n, jede ungerade Zahl ist dazu teilerfremd. Im Fall eines Integerkeys hängt es vom Wertebereich des Integerkeys ab, der sollte besser kein Vielfaches der Feldgrösse sein - nicht umgekehrt. In fast allen Fällen in der Praxis wird das aber egal sein. Die hier eingesetzten Algorithmen gewinnen durch Primzahlen nichts.

2. Ein Rehash würde ich nicht davon abhängig machen, wie gefüllt die Tabelle schon ist, weil das ist eigentlich für die Performance ziemlich egal, sondern dann machen, wenn eine vorgegebene Anzahl von Kollisionen pro Hashentry überschritten wird: z.B: wenn bei irgend einem hashentry die angehängte Feldliste drei oder vier Elemente überschreitet.

[Namenloser]

Zitat:

Zitat von idefix2 (Beitrag 1035891)

Hallo, hab mir Dein Programm angeschaut, es schaut schon recht gut aus.

Danke, dass du dir den Code angesehen hast und für dein Feedback.

Ich habe die Hashmap inzwischen noch etwas überarbeitet und unter anderem die Widestring-Map implementiert. Leider ist die ca. 4-5 mal so langsam wie die Ansi-Variante :( Ist es normal, dass Widestrings so viel langsamer sind? Wenn ich den Benchmark durch den SamplingProfiler laufen lasse, erzeugt ntdll.dll 57% der CPU-Last, was denke ich darauf zurückzuführen ist, dass WideStrings von Windows gemanaged werden. Die Exe selbst belegt nur ca 20%, wovon 50% die System.pas-Funktion mit WStrCmp und Co einnehmen.

Hat jemand eine Idee, wie man den Code vielleicht noch optimieren könnte?

Zitat:

Zitat von idefix2 (Beitrag 1035891)

Folgendes würde ich anders machen:

1. Die Suche nach Primzahlen ist beim verwendeten Algorithmus wirklich ganz überflüssig. Es sollte eine zum Wertebereich des Schlüssels teilerfremde Zahl sein. Im Fall des Stringkey ist der Wertebereich 2 hoch n, jede ungerade Zahl ist dazu teilerfremd. Im Fall eines Integerkeys hängt es vom Wertebereich des Integerkeys ab, der sollte besser kein Vielfaches der Feldgrösse sein - nicht umgekehrt. In fast allen Fällen in der Praxis wird das aber egal sein. Die hier eingesetzten Algorithmen gewinnen durch Primzahlen nichts.

Primzahlen benutze ich in meiner Komponente ja auch nicht, nur die von alzaimar macht das. Meine Hashmap verdoppelt immer ihre Größe ab einer gewissen Schwelle und nutzt diesen Code um den Hash zu verlürzen:

Delphi-Quellcode:

function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
var
  Tmp: Cardinal;
begin
  Tmp := CalculateHash(AKey);
  Result := (Tmp  
              xor (Tmp shr 8)
              xor (Tmp shr 16)
              xor (tmp shr 24))
            and
              FMask;
end;

Zitat:

Zitat von idefix2 (Beitrag 1035891)

2. Ein Rehash würde ich nicht davon abhängig machen, wie gefüllt die Tabelle schon ist, weil das ist eigentlich für die Performance ziemlich egal, sondern dann machen, wenn eine vorgegebene Anzahl von Kollisionen pro Hashentry überschritten wird: z.B: wenn bei irgend einem hashentry die angehängte Feldliste drei oder vier Elemente überschreitet.

Die Methode habe ich von alzaimars Hashmap übernommen. Prinzipiell würde ich die Größe auch von der Anzahl an Kollisionen abhängig machen, das Problem ist nur, diese zu ermitteln, da die Kollisionen über eine verkettete Liste gehandhabt werden. Man müsste dann bei jeder Änderung die Liste komplett durchlaufen, um zu prüfen, wie viele Einträge dort abgelegt sind.

[himitsu]

Zitat:

Zitat von NamenLozer (Beitrag 1035897)

Ist es normal, dass Widestrings so viel langsamer sind?

ja

AnsiString und ab Delphi 2009 auch UnicodeString:
- delphieigener Typ
- Referenzzählung
- "optimierte" Speicherverwaltung über den Delphi-MemoryManager (neuerdings FastMM)

WideString:
- Umleitung auf WinAPI
- keine Referenzzählung
- (unbekannte) Speicherverwaltung über OleAuth32.dll

SysAllocStringLen
SysReAllocStringLen
SysFreeString
SysStringLen


Wozu Cardinal, wenn du am Ende alles quasi auf 1 Byte runterkürzt, bzw. den schönen Hash zerxorst?

würde es maximal so machen:

Delphi-Quellcode:

function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
begin
  Result := CalculateHash(AKey) and FMask;
end;

[Namenloser]

Hallo himitsu,

Zitat:

Zitat von himitsu (Beitrag 1035899)

Wozu Cardinal, wenn du am Ende alles quasi auf 1 Byte runterkürzt, bzw. den schönen Hash zerxorst?

würde es maximal so machen:

Delphi-Quellcode:

function THashMap.GetShrunkHash(AKey: Pointer): cardinal;
begin
  Result := CalculateHash(AKey) and FMask;
end;

Das ist ab Post #6 erörtert.

[edit]
Habe mal eben schnell einen Test durchgeführt:
Ohne XOR:

Code:

---------------- Adding 100.000 items:
Namenlozer's hashmap:
Write: 0,218s
Read:  0,094s
Total: 111001
Hashmap size: 131072

---------------- Adding 1.000.000 items:
Namenlozer's hashmap:
Write: 2,511s
Read:  1,155s
Total: 1111001
Hashmap size: 1048576

---------------- Adding 10.000.000 items:
Namenlozer's hashmap:
Write: 30,997s
Read:  23,775s
Total: 11111001
Hashmap size: 8388608

Mit XOR:

Code:

---------------- Adding 100.000 items:
Namenlozer's hashmap:
Write: 0,218s
Read:  0,078s
Total: 111001
Hashmap size: 131072

---------------- Adding 1.000.000 items:
Namenlozer's hashmap:
Write: 2,294s
Read:  1,014s
Total: 1111001
Hashmap size: 1048576

---------------- Adding 10.000.000 items:
Namenlozer's hashmap:
Write: 27,768s
Read:  21,575s
Total: 11111001
Hashmap size: 8388608

Also wie du siehst, scheint das XOR keinen negativen, sondern eher einen positiven Effekt zu haben.
[/edit]
[edit]
Ich habe die Performance jetzt deutlich erhöht, indem ich den WideString stellenweise durch einen selbstimplementierten, etwas frickeligen (die verbuggte Implementierung von Record-Methoden in Turbo Delphi hat ihren Teil dazu beigetragen) Pseudo-Unicode-String ersetzt habe.

Code:

---------------- Adding 100.000 items:
Namenlozer's hashmap:
Write: 0,062s
Read:  0,063s
Total: 111000
Hashmap size: 131072

---------------- Adding 1.000.000 items:
Namenlozer's hashmap:
Write: 0,780s
Read:  0,608s
Total: 1111000
Hashmap size: 1048576

---------------- Adding 10.000.000 items:
Namenlozer's hashmap:
Write: 8,643s
Read:  6,755s
Total: 11111000
Hashmap size: 8388608

Wie man sieht, hat sich die Performance um mehr als das dreifache erhöht!
Zwar ist das ganze immer noch langsamer als die Ansi-Variante, aber ich denke, die Abweichung ist jetzt akzeptabel.
[/edit]