Vorteil von auf Primzahlen skalierten Hashmaps?

[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

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)
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 von idefix2:

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 von idefix2:

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 von idefix2:

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 von NamenLozer:

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 von himitsu:

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]