Vorteil von auf Primzahlen skalierten Hashmaps?

[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]