Was ist die schnellste Hash-Funktion für Zeiger?

Question

Auf Hashtabellen basierende Container sind ein sehr schnelles assoziatives Array (z. B. unordered_map, unordered_set).

Ihre Leistung hängt stark von der Hash-Funktion ab, mit der für jeden Eintrag ein Index erstellt wird. Wenn Hash-Tabellen wachsen, werden Elemente immer wieder neu gewaschen.

Zeiger sind ein einfacher Typ, im Wesentlichen ein 4/8 Byte-Wert, der ein Objekt eindeutig identifiziert. Das Problem ist, dass die Verwendung einer Adresse als Ergebnis der Hash-Funktion nicht effizient ist, da mehrere LSB Null sind.

Beispiel:

struct MyVoidPointerHash { size_t operator()(const void* val) const { return (size_t)val; } };

Eine schnellere Implementierung besteht darin, ein paar Bits zu verlieren:

struct MyVoidPointerHash2 { size_t operator()(const void* val) const { return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit } };

Letzteres führte zu einer Leistungssteigerung von 10 bis 20% bei einer großen Anwendung, die Hash-Sets und Karten mit Zehntausenden von Elementen verwendet, die häufig gebaut und gelöscht werden.

Kann jemand ein besseres Schema für Hash-Zeiger anbieten?

Die Funktion muss sein:

Schnell! und muss gut inline sein.
Bieten Sie eine angemessene Verteilung an, seltene Kollisionen sind erlaubt.

Update - Benchmark-Ergebnisse

Ich habe zwei Testsätze ausgeführt, einen für int* und für einen Klassenzeiger mit einer Größe von 4 KB. Die Ergebnisse sind sehr interessant.

Ich habe std::unordered_set für alle Tests verwendet, wobei die Datengröße 16 MB betrug, die in einem einzigen Aufruf von new zugewiesen wurde. Der erste Algorithmus wurde zweimal ausgeführt, um sicherzustellen, dass die Caches so heiß wie möglich sind und die CPU mit voller Geschwindigkeit läuft.

Setup: VS2013 (x64), i7-2600, Windows 8.1 x64.

VS2013-Standard-Hash-Funktion
Hash1: return (size_t)(val);
Hash2: return '(size_t)(val) >> 3;
Hash3 (@BasileStarynkevitch): uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15));
Hash4 (@Roddy): uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16));
Hash5 (@egur):

Code:

template<typename Tval> struct MyTemplatePointerHash1 { size_t operator()(const Tval* val) const { static const size_t shift = (size_t)log2(1 + sizeof(Tval)); return (size_t)(val) >> shift; } };

Test 1 - int*:

Der VS2013-Standard dauerte 1292 ms
Hash1 dauerte 742ms
Hash2 nahm 343ms
Hash3 dauerte 1008ms
Hash4 dauerte 629ms
Hash5 nahm 350ms

Test 1 - 4K_class*:

Der VS2013-Standard dauerte 0,423 ms
Hash1 dauerte 23.889ms
Hash2 dauerte 6,331 ms
Hash3 dauerte 0,366 ms
Hash4 dauerte 0,390 ms
Hash5 nahm 0,290 ms

Update2:

Der bisherige Gewinner ist die Templated Hash (Hash5) Funktion. Beste Leistung für Geschwindigkeit bei verschiedenen Blockgrößen.

Update 3: Standard-Hash-Funktion für Baseline hinzugefügt. Es ist alles andere als optimal.

egur · Accepted Answer

Nachdem ich diese Frage eine Weile liegen gelassen habe, werde ich meine bisher beste Hash-Funktion für Zeiger posten:

template<typename Tval> struct MyTemplatePointerHash1 { size_t operator()(const Tval* val) const { static const size_t shift = (size_t)log2(1 + sizeof(Tval)); return (size_t)(val) >> shift; } };

Es ist leistungsstark für verschiedene Blockgrößen.
Wenn jemand eine bessere Funktion hat, ändere ich die akzeptierte Antwort.

Damon · Answer

Theoretisch gesehen lautet die richtige Antwort: "Verwende std::hash, der wahrscheinlich so gut wie möglich ist, und falls dies nicht zutrifft, verwende eine gute Hash-Funktion anstelle einer schnellen. Die Geschwindigkeit der Hash-Funktion ist weniger wichtig als ihre Qualität ".

Die praktische Antwort lautet: "Verwende std::hash, der arm an Pisse ist, aber trotzdem überraschend gut funktioniert."

TL; DR
Nachdem ich fasziniert war, lief ich über das Wochenende ungefähr 30 Stunden Benchmarks. Unter anderem habe ich versucht, einen durchschnittlichen Fall im Vergleich zum schlimmsten Fall zu ermitteln, und versucht, std::unordered_map in das Verhalten im schlimmsten Fall zu zwingen, indem ich ihm absichtlich schlechte Hinweise auf die Anzahl der Eimer in Bezug auf die eingestellte Größe gab.

Ich habe schlechte Hashes (std::hash<T*>) mit allgemein bekannten Hashes von insgesamt guter Qualität (djb2, sdbm) sowie Variationen davon verglichen, die für die sehr kurze Eingabelänge verantwortlich sind, und mit Hashes, von denen ausdrücklich angenommen wird, dass sie in Hashtabellen verwendet werden (murmel2 und murmel3) und pissarme Hashes, die eigentlich schlimmer sind als gar kein Hashing, da sie Entropie wegwerfen.
Da die niedrigsten 2-3 Bits auf Zeigern aufgrund der Ausrichtung immer Null sind, hielt ich es für sinnvoll, eine einfache Rechtsverschiebung als "Hash" zu testen, sodass in diesem Fall nur die Informationen ungleich Null verwendet würden die hashtabelle zb verwendet nur die untersten N Bits. Es stellte sich heraus, dass für vernünftige Verschiebungen (ich habe auch unvernünftige Verschiebungen versucht!) Dies tatsächlich recht gut funktioniert.

Ergebnisse

Einige meiner Ergebnisse waren bekannt und nicht überraschend, andere sind sehr überraschend:

Es ist schwer vorherzusagen, was ein "guter" Hash ist. Gute Hash-Funktionen zu schreiben ist schwierig. Kein Wunder, bekannte Tatsache und erneut bewiesen.
Kein einzelner Hash übertrifft in jedem Szenario alle anderen signifikant. Kein einziger Hash übertrifft in 80% der Fälle alle anderen signifikant. Das erste Ergebnis wurde erwartet, das zweite ist dennoch überraschend.
Es ist wirklich schwer, std::unordered_map dazu zu bringen, sich schlecht zu benehmen. Selbst wenn absichtlich schlechte Hinweise auf die Anzahl der Eimer gegeben werden, die zu mehreren erneuten Hashes führen, ist die Gesamtleistung nicht viel schlechter. Nur die allerschlimmsten Hash-Funktionen, die den größten Teil der Entropie auf fast lächerliche Weise wegwerfen, können die Leistung um mehr als 10-20% erheblich beeinträchtigen (z. B. right_shift_12, was praktisch nur 12 verschiedene ergibt Hash-Werte für 50.000 Eingaben! Es ist nicht verwunderlich, dass die Hash-Map in diesem Fall etwa 100-mal langsamer ausgeführt wird.
Einige "lustige" Ergebnisse sind sicherlich auf Implementierungsdetails zurückzuführen. Meine Implementierung (GCC) verwendet eine Primzahl, die etwas größer als 2 ^ N ist, und fügt Werte mit indentischen Hashes head-first in verknüpfte Listen ein.
Die Spezialisierung von std::hash<T*> ist für GCC geradezu erbärmlich (ein einfacher reinterpret_cast). Lustigerweise ein Funktor, der das Gleiche tut arbeitet beim Einfügen konstant schneller und beim wahlfreien Zugriff langsamer. Der Unterschied ist gering (ein Dutzend Millisekunden bei einem Testlauf von 8-10 Sekunden), aber es ist kein Rauschen, es ist konsistent vorhanden - wahrscheinlich im Zusammenhang mit der Neuanordnung von Befehlen oder dem Pipelining. Es ist erstaunlich, wie genau derselbe Code (der auch ein No-Op ist) konsistent in zwei verschiedenen Szenarien unterschiedlich funktioniert.
Pathetische Hashes nicht führen zu einer deutlich schlechteren Leistung als "gute" Hashes oder Hashes, die explizit für Hash-Tabellen entwickelt wurden. In der Tat sind sie in der Hälfte der Fälle die besten Performer oder unter den Top 3.
Die "besten" Hash-Funktionen führen selten, wenn überhaupt, zu der besten Gesamtleistung.
Die in dieser SO Frage als Antworten angegebenen Hashes sind im Allgemeinen in Ordnung. Sie sind durchschnittlich gut, aber std::hash nicht überlegen. Normalerweise landen sie in den Top 3-4.
Schlechte Hashes sind etwas anfällig für die Reihenfolge der Einfügung (schlechtere Leistung bei zufälliger Einfügung und zufälliger Suche nach zufälliger Einfügung), wohingegen "gute" Hashes dem Einfluss der Reihenfolge der Einfügung widerstandsfähiger sind (geringer oder kein Unterschied), die Gesamtleistung jedoch immer noch etwas langsamer.

Versuchsaufbau

Die Tests wurden nicht nur mit beliebigen 4-Byte- oder 8-Byte-Werten (oder was auch immer) durchgeführt, sondern auch mit tatsächlichen Adressen, die durch Zuweisen des vollständigen Satzes von Elementen auf dem Heap und Speichern der vom Zuweiser bereitgestellten Adressen in einem std::vector (dem Objekte wurden dann gelöscht, sie werden nicht benötigt).
Adressen wurden für jeden Test in der im Vektor gespeicherten Reihenfolge in einen neu zugewiesenen std::unordered_map eingefügt, einmal in der ursprünglichen Reihenfolge ("sequentiell") und einmal nach dem Anwenden eines std::random_shuffle auf den Vektor.

Es wurden Tests für Sätze von 50.000 und 1.000.000 Objekten der Größe 4, 16, 64, 256 und 1024 durchgeführt (die Ergebnisse für 64 wurden hier aus Gründen der Kürze weggelassen. Sie liegen erwartungsgemäß in der Mitte zwischen 16 und 256 - StackOverflow erlaubt nur das Posten von 30k Zeichen).
Die Testsuite wurde dreimal durchgeführt. Die Ergebnisse variierten hier und da um 3 oder 4 Millisekunden, waren jedoch insgesamt identisch. Die hier veröffentlichten Ergebnisse sind die letzten.

Die Reihenfolge der Einfügungen im "zufälligen" Test sowie das Zugriffsmuster (in jedem Test) ist pseudozufällig, aber für jede Hash-Funktion in einem Testlauf genau identisch.

Die Timings unter Hash-Benchmarks dienen zum Summieren von 4.000.000.000 Hash-Werten in einer ganzzahligen Variablen.

Die Spalte insert gibt die Zeit in Millisekunden für 50 Iterationen an, in denen ein std::unordered_map erstellt, 50.000 bzw. 1.000.000 Elemente eingefügt und die Karte zerstört wurde.

Die Spalte access gibt die Zeit in Millisekunden an, um 100.000.000 Suchen nach einem Pseudozufallselement im 'Vektor' durchzuführen, gefolgt vom Nachschlagen dieser Adresse im unordered_map.
Dieses Timing beinhaltet im Durchschnitt eine Cache-Misse für den Zugriff auf ein zufälliges Element im vector, zumindest für den großen Datensatz (kleiner Datensatz passt vollständig in L2).

Alle Timings auf einem 2,66 GHz Intel Core2, Windows 7, gcc 4.8.1/MinGW-w64_32. Timer-Granularität bei 1 ms.

Quellcode

Der Quellcode ist verfügbar auf Ideone , ebenfalls aufgrund der Beschränkung von Stackoverflow auf 30.000 Zeichen.

Hinweis: Das Ausführen der vollständigen Testsuite auf einem Desktop-PC dauert weit über 2 Stunden. Machen Sie also einen Spaziergang, wenn Sie die Ergebnisse reproduzieren möchten.

Testergebnisse

Benchmarking hash funcs... std::hash 2576 reinterpret_cast 2561 djb2 13970 djb2_mod 13969 sdbm 10246 yet_another_lc 13966 murmur2 11373 murmur3 15129 simple_xorshift 7829 double_xorshift 13567 right_shift_2 5806 right_shift_3 5866 right_shift_4 5705 right_shift_5 5691 right_shift_8 5795 right_shift_12 5728 MyTemplatePointerHash1 5652 BasileStarynkevitch 4315 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 421 6988 reinterpret_cast 408 7083 djb2 451 8875 djb2_mod 450 8815 sdbm 455 8673 yet_another_lc 443 8292 murmur2 478 9006 murmur3 490 9213 simple_xorshift 460 8591 double_xorshift 477 8839 right_shift_2 416 7144 right_shift_3 422 7145 right_shift_4 414 6811 right_shift_5 425 8006 right_shift_8 540 11787 right_shift_12 1501 49604 MyTemplatePointerHash1 410 7138 BasileStarynkevitch 445 8014 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 443 7570 reinterpret_cast 436 7658 djb2 473 8791 djb2_mod 472 8766 sdbm 472 8817 yet_another_lc 458 8419 murmur2 479 9005 murmur3 491 9205 simple_xorshift 464 8591 double_xorshift 476 8821 right_shift_2 441 7724 right_shift_3 440 7716 right_shift_4 450 8061 right_shift_5 463 8653 right_shift_8 649 16320 right_shift_12 3052 114185 MyTemplatePointerHash1 438 7718 BasileStarynkevitch 453 8140 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 8945 32801 reinterpret_cast 8796 33251 djb2 11139 54855 djb2_mod 11041 54831 sdbm 11459 36849 yet_another_lc 14258 57350 murmur2 16300 39024 murmur3 16572 39221 simple_xorshift 14930 38509 double_xorshift 16192 38762 right_shift_2 8843 33325 right_shift_3 8791 32979 right_shift_4 8818 32510 right_shift_5 8775 30436 right_shift_8 10505 35960 right_shift_12 30481 91350 MyTemplatePointerHash1 8800 33287 BasileStarynkevitch 12885 37829 -------------------------------- sizeof(T) = 4 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 12183 33424 reinterpret_cast 12125 34000 djb2 22693 51255 djb2_mod 22722 51266 sdbm 15160 37221 yet_another_lc 24125 51850 murmur2 16273 39020 murmur3 16587 39270 simple_xorshift 16031 38628 double_xorshift 16233 38757 right_shift_2 11181 33896 right_shift_3 10785 33660 right_shift_4 10615 33204 right_shift_5 10357 38216 right_shift_8 15445 100348 right_shift_12 73773 1044919 MyTemplatePointerHash1 11091 33883 BasileStarynkevitch 15701 38092 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 415 8243 reinterpret_cast 422 8321 djb2 445 8730 djb2_mod 449 8696 sdbm 460 9439 yet_another_lc 455 9003 murmur2 475 9109 murmur3 482 9313 simple_xorshift 463 8694 double_xorshift 465 8900 right_shift_2 416 8402 right_shift_3 418 8405 right_shift_4 423 8366 right_shift_5 421 8347 right_shift_8 453 9195 right_shift_12 666 18008 MyTemplatePointerHash1 433 8191 BasileStarynkevitch 466 8443 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 450 8135 reinterpret_cast 457 8208 djb2 470 8736 djb2_mod 476 8698 sdbm 483 9420 yet_another_lc 476 8953 murmur2 481 9089 murmur3 486 9283 simple_xorshift 466 8663 double_xorshift 468 8865 right_shift_2 456 8301 right_shift_3 456 8302 right_shift_4 453 8337 right_shift_5 457 8340 right_shift_8 505 10379 right_shift_12 1099 34923 MyTemplatePointerHash1 464 8226 BasileStarynkevitch 466 8372 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 9548 35362 reinterpret_cast 9635 35869 djb2 10668 37339 djb2_mod 10763 37311 sdbm 11126 37145 yet_another_lc 11597 39944 murmur2 16296 39029 murmur3 16432 39280 simple_xorshift 16066 38645 double_xorshift 16108 38778 right_shift_2 8966 35953 right_shift_3 8916 35949 right_shift_4 8973 35504 right_shift_5 8941 34997 right_shift_8 9356 31233 right_shift_12 13831 45799 MyTemplatePointerHash1 8839 31798 BasileStarynkevitch 15349 38223 -------------------------------- sizeof(T) = 64 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 14756 36237 reinterpret_cast 14763 36918 djb2 15406 38771 djb2_mod 15551 38765 sdbm 14886 37078 yet_another_lc 15700 40290 murmur2 16309 39024 murmur3 16432 39381 simple_xorshift 16177 38625 double_xorshift 16073 38750 right_shift_2 14732 36961 right_shift_3 14170 36965 right_shift_4 13687 37295 right_shift_5 11978 35135 right_shift_8 11498 46930 right_shift_12 25845 268052 MyTemplatePointerHash1 10150 32046 BasileStarynkevitch 15981 38143 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 432 7957 reinterpret_cast 429 8036 djb2 462 8970 djb2_mod 453 8884 sdbm 460 9110 yet_another_lc 466 9015 murmur2 495 9147 murmur3 494 9300 simple_xorshift 479 8792 double_xorshift 477 8948 right_shift_2 430 8120 right_shift_3 429 8132 right_shift_4 432 8196 right_shift_5 437 8324 right_shift_8 425 8050 right_shift_12 519 11291 MyTemplatePointerHash1 425 8069 BasileStarynkevitch 468 8496 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 462 7956 reinterpret_cast 456 8046 djb2 490 9002 djb2_mod 483 8905 sdbm 482 9116 yet_another_lc 492 8982 murmur2 492 9120 murmur3 492 9276 simple_xorshift 477 8761 double_xorshift 477 8903 right_shift_2 458 8116 right_shift_3 459 8124 right_shift_4 462 8281 right_shift_5 463 8370 right_shift_8 458 8069 right_shift_12 662 16244 MyTemplatePointerHash1 459 8091 BasileStarynkevitch 472 8476 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 9756 34368 reinterpret_cast 9718 34897 djb2 10935 36894 djb2_mod 10820 36788 sdbm 11084 37857 yet_another_lc 11125 37996 murmur2 16522 39078 murmur3 16461 39314 simple_xorshift 15982 38722 double_xorshift 16151 38868 right_shift_2 9611 34997 right_shift_3 9571 35006 right_shift_4 9135 34750 right_shift_5 8978 32878 right_shift_8 8688 30276 right_shift_12 10591 35827 MyTemplatePointerHash1 8721 30265 BasileStarynkevitch 15524 38315 -------------------------------- sizeof(T) = 256 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 14169 36078 reinterpret_cast 14096 36637 djb2 15373 37492 djb2_mod 15279 37438 sdbm 15531 38247 yet_another_lc 15924 38779 murmur2 16524 39109 murmur3 16422 39280 simple_xorshift 16119 38735 double_xorshift 16136 38875 right_shift_2 14319 36692 right_shift_3 14311 36776 right_shift_4 13932 35682 right_shift_5 12736 34530 right_shift_8 9221 30663 right_shift_12 15506 98465 MyTemplatePointerHash1 9268 30697 BasileStarynkevitch 15952 38349 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = sequential dataset size = 50000 elements name insert access std::hash 421 7863 reinterpret_cast 419 7953 djb2 457 8983 djb2_mod 455 8927 sdbm 445 8609 yet_another_lc 446 8892 murmur2 492 9090 murmur3 507 9294 simple_xorshift 467 8687 double_xorshift 472 8872 right_shift_2 432 8009 right_shift_3 432 8014 right_shift_4 435 7998 right_shift_5 442 8099 right_shift_8 432 7914 right_shift_12 462 8911 MyTemplatePointerHash1 426 7744 BasileStarynkevitch 467 8417 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = random dataset size = 50000 elements name insert access std::hash 452 7948 reinterpret_cast 456 8018 djb2 489 9037 djb2_mod 490 8992 sdbm 477 8795 yet_another_lc 491 9179 murmur2 502 9078 murmur3 507 9273 simple_xorshift 473 8671 double_xorshift 480 8873 right_shift_2 470 8105 right_shift_3 470 8100 right_shift_4 476 8333 right_shift_5 468 8065 right_shift_8 469 8094 right_shift_12 524 10216 MyTemplatePointerHash1 451 7826 BasileStarynkevitch 472 8419 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = sequential dataset size = 1000000 elements name insert access std::hash 10910 38432 reinterpret_cast 10892 38994 djb2 10499 38985 djb2_mod 10507 38983 sdbm 11318 37450 yet_another_lc 11740 38260 murmur2 16960 39544 murmur3 16816 39647 simple_xorshift 16096 39021 double_xorshift 16419 39183 right_shift_2 10219 38909 right_shift_3 10012 39036 right_shift_4 10642 40284 right_shift_5 10116 38678 right_shift_8 9083 32914 right_shift_12 9376 31586 MyTemplatePointerHash1 8777 30129 BasileStarynkevitch 16036 38913 -------------------------------- sizeof(T) = 1024 sizeof(T*) = 4 insertion order = random dataset size = 1000000 elements name insert access std::hash 16304 38695 reinterpret_cast 16241 39641 djb2 16377 39533 djb2_mod 16428 39526 sdbm 15402 37811 yet_another_lc 16180 38730 murmur2 16679 39355 murmur3 16792 39586 simple_xorshift 16196 38965 double_xorshift 16371 39127 right_shift_2 16445 39263 right_shift_3 16598 39421 right_shift_4 16378 39839 right_shift_5 15517 38442 right_shift_8 11589 33547 right_shift_12 11992 49041 MyTemplatePointerHash1 9052 30222 BasileStarynkevitch 16163 38829

Roddy · Answer

Das von der Hash-Funktion zurückgegebene Ergebnis hat den Typ size_t, wird jedoch vom Container in einen 'Bucket-Index' konvertiert, der den richtigen Bucket identifiziert, um das Objekt zu finden.

Ich denke, dass diese Konvertierung nicht im Standard spezifiziert ist, aber ich würde erwarten, dass dies normalerweise eine Modulo-N-Operation ist, wobei N die Anzahl der Buckets ist - und dass N normalerweise eine Zweierpotenz ist, da das Verdoppeln der Bucket-Anzahl gut ist Möglichkeit, die Größe zu erhöhen, wenn es zu viele Treffer gibt. Die Modulo-N-Operation würde bedeuten, dass die naive Hash-Funktion für Zeiger nur einen Bruchteil der Buckets verwendet.

Das eigentliche Problem ist, dass ein "guter" Hash-Algorithmus für Container auf der Kenntnis der Bucket-Größe und der von Ihnen gemachten Werte basieren muss. Wenn beispielsweise die Objekte, die Sie in der Tabelle gespeichert haben, alle eine Größe von 1024 Byte hatten, ist es möglich, dass die niederwertigen 10 Bits jedes Zeigers gleich sind.

struct MyOneKStruct x[100]; //bottom 10 bits of &x[n] are always the same

Ein „bester“ Hash für jede Anwendung erfordert wahrscheinlich viel Versuch und Irrtum und Messung sowie Kenntnis der Verteilung der Werte, die Sie hashnen.

Anstatt den Zeiger einfach um N Bits nach unten zu verschieben, würde ich versuchen, etwas wie XOR das oberste 'Wort' in das unterste Wort zu setzen. Ähnlich wie @ BasileStarynkevichs Antwort.

Der Vorschlag zum Hinzufügen von Hash-Tabellen macht eine interessante Lektüre. Meine Betonung im nachstehenden Absatz: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html

Es ist nicht möglich, eine vollständig allgemeine Hash-Funktion zu schreiben, die gültig ist für alle arten. (Sie können ein Objekt nicht einfach in den Rohspeicher konvertieren und die Bytes Hash; die Idee schlägt unter anderem aus Padding fehl.) Deshalb und auch weil eine gute Hashfunktion ist Nur im Zusammenhang mit einem bestimmten Verwendungsmuster ist unbedingt erforderlich Benutzer können ihre eigenen Hash-Funktionen bereitstellen.

Basile Starynkevitch · Answer

Die Antwort ist offensichtlich system- und prozessorabhängig (insbesondere aufgrund der Seitengröße und der Word-Größe). Ich schlage vor

 struct MyVoidPointerHash { size_t operator()(const void* val) const { uintptr_t ad = (uintptr_t) val; return (size_t) ((13*ad) ^ (ad >> 15)); } };

Die Erkenntnis ist, dass auf vielen Systemen die Seitengröße oft 4 KB beträgt (d. H. 2¹²), so dass die Rechtsverschiebung >>15 signifikante Adressbestandteile in die unteren Bits setzt. Der 13* ist meistens zum Spaß (aber 13 ist Primzahl) und die Bits mehr zu mischen. Der Exklusivcode oder ^ mischt Bits und ist sehr schnell. Die unteren Bits des Hash sind also eine Mischung aus vielen Bits (sowohl hoch als auch niedrig) des Zeigers.

^{Ich behaupte nicht, in solchen Hash-Funktionen viel "Wissenschaft" eingesetzt zu haben. Aber sie funktionieren oft recht gut. YMMV. Ich würde vermuten, dass Sie das Deaktivieren von ASLR vermeiden sollten!}

Orient · Answer

Kann Ihre Lösung auf Performance-Rennstrecken nicht schlagen (weder für char noch für 1024-große struct), aber im Hinblick auf die Richtigkeit gibt es einige Verbesserungen:

#include <iostream> #include <new> #include <algorithm> #include <unordered_set> #include <chrono> #include <cstdlib> #include <cstdint> #include <cstddef> #include <cmath> namespace { template< std::size_t argument, std::size_t base = 2, bool = (argument < base) > constexpr std::size_t log = 1 + log< argument / base, base >; template< std::size_t argument, std::size_t base > constexpr std::size_t log< argument, base, true > = 0; } struct pointer_hash { template< typename type > constexpr std::size_t operator () (type * p) const noexcept { return static_cast< std::size_t >(reinterpret_cast< std::uintptr_t >(p) >> log< std::max(sizeof(type), alignof(type)) >); } }; template< typename type = std::max_align_t, std::size_t i = 0 > struct alignas(alignof(type) << i) S { }; int main() { constexpr std::size_t _16M = (1 << 24); S<> * p = new S<>[_16M]{}; auto latch = std::chrono::high_resolution_clock::now(); { std::unordered_set< S<> *, pointer_hash > s; for (auto * pp = p; pp < p + _16M; ++pp) { s.insert(pp); } } std::cout << std::chrono::duration_cast< std::chrono::milliseconds >(std::chrono::high_resolution_clock::now() - latch).count() << "ms" << std::endl; delete [] p; return EXIT_SUCCESS; }