Ich habe gerade ein Buch "C Interfaces and Implementations" gekauft. Im ersten Kapitel wurde eine "Atom" -Struktur implementiert, Beispielcode wie folgt:
%Vor%am Ende des Kapitels, in Übungen 3.1, sagte der Autor des Buches " Die meisten Texte empfehlen die Verwendung einer Primzahl für die Größe von Eimer. Die Verwendung einer Prime- und einer guten Hash-Funktion ergibt normalerweise a bessere Verteilung der Längen der Listen, die von Eimern hängen. Atom verwendet eine Zweierpotenz, die manchmal explizit zitiert wird als eine schlechte Wahl. Schreiben Sie ein Programm zum Generieren oder Lesen, sagen wir 10.000 typische Strings und messen die Geschwindigkeit von Atom_new und die Verteilung von den Längen der Listen. Dann ändern Sie die Eimer, so dass es hat 2.039 Einträge (die größte Primzahl weniger als 2.048), und wiederholen Sie die Messungen. Braucht man eine Haupthilfe? Wie viel kostet dein? Schlussfolgerung hängt von Ihrer spezifischen Maschine ab? "
Also habe ich die Hashtabellengröße auf 2039 geändert, aber es scheint eine Primzahl zu sein, die tatsächlich gemacht wurde eine schlechte Verteilung der Längen der Listen, ich habe versucht 64, 61, 61 tatsächlich auch eine schlechte Verteilung gemacht.
Ich möchte nur wissen, warum eine Primzahl-Tabellengröße eine schlechte Verteilung ergibt, liegt das daran, dass die Hash-Funktion, die mit Atom_new verwendet wird, eine schlechte Hash-Funktion ist?
Ich verwende diese Funktion, um die Längen der Atomlisten auszudrucken
%Vor%Ich habe gerade ein Buch "C Interfaces and Implementations" gekauft. Im ersten Kapitel wurde eine "Atom" -Struktur implementiert, Beispielcode wie folgt:
%Vor%am Ende des Kapitels, in Übungen 3.1, sagte der Autor des Buches " Die meisten Texte empfehlen die Verwendung einer Primzahl für die Größe von Eimer. Die Verwendung einer Prime- und einer guten Hash-Funktion ergibt normalerweise a bessere Verteilung der Längen der Listen, die von Eimern hängen. Atom verwendet eine Zweierpotenz, die manchmal explizit zitiert wird als eine schlechte Wahl. Schreiben Sie ein Programm zum Generieren oder Lesen, sagen wir 10.000 typische Strings und messen die Geschwindigkeit von Atom_new und die Verteilung von den Längen der Listen. Dann ändern Sie die Eimer, so dass es hat 2.039 Einträge (die größte Primzahl weniger als 2.048), und wiederholen Sie die Messungen. Braucht man eine Haupthilfe? Wie viel kostet dein? Schlussfolgerung hängt von Ihrer spezifischen Maschine ab? "
Also habe ich die Hashtabellengröße auf 2039 geändert, aber es scheint eine Primzahl zu sein, die tatsächlich gemacht wurde eine schlechte Verteilung der Längen der Listen, ich habe versucht 64, 61, 61 tatsächlich auch eine schlechte Verteilung gemacht.
Ich möchte nur wissen, warum eine Primzahl-Tabellengröße eine schlechte Verteilung ergibt, liegt das daran, dass die Hash-Funktion, die mit Atom_new verwendet wird, eine schlechte Hash-Funktion ist?
Ich verwende diese Funktion, um die Längen der Atomlisten auszudrucken
%Vor%Nun, vor einiger Zeit musste ich eine Hash-Tabelle (in der Treiberentwicklung) implementieren, und ich ungefähr dasselbe. Warum zum Teufel sollte ich eine Primzahl verwenden? OTOH-Potenz von 2 ist sogar noch besser - anstatt den Modulus im Falle einer Potenz von 2 zu berechnen, können Sie ein bitweises UND verwenden.
Also habe ich eine solche Hash-Tabelle implementiert. Der Schlüssel war ein Zeiger (der von einer Drittanbieterfunktion zurückgegeben wurde). Dann habe ich schließlich festgestellt, dass in meiner Hash-Tabelle nur 1/4 aller Einträge gefüllt ist. Da diese Hash-Funktion, die ich verwendet habe, Identitätsfunktion war, und nur für den Fall stellte sich heraus, dass alle zurückgegebenen Zeiger ein Vielfaches von 4 sind.
Die Idee, die Primzahlen für die Größe der Hash-Tabelle zu verwenden, ist folgende: Reale-Welt-Hash-Funktionen nicht produzieren gleichverteilte Werte. Normalerweise gibt es (oder zumindest gibt es) eine Abhängigkeit. Um diese Verteilung zu streuen wird empfohlen, Primzahlen zu verwenden.
BTW, theoretisch kann es gelegentlich vorkommen, dass die Hash-Funktion die Zahlen erzeugt, die Vielfache Ihrer gewählten Primzahl sind. Aber die Wahrscheinlichkeit dafür ist geringer, als wenn es keine Primzahl wäre.
Das ist es, was Julienne Walker von Eternally Confuzzled über Hashtabellengrößen sagen muss:
Wenn es um Hash-Tabellen geht, am meisten Die empfohlene Tischgröße ist eine beliebige Primzahl Nummer. Diese Empfehlung wird gemacht weil Hashing im Allgemeinen ist falsch verstanden und schlechte Hash-Funktionen erfordern einen zusätzlichen Mischschritt von Division durch eine Primzahl, um a ähneln gleichmäßige Verteilung. Ein anderer Grund dass eine Tabellengröße empfohlen wird ist wegen mehrerer der Kollision Lösungsmethoden erfordern es zu arbeiten. In Wirklichkeit ist dies eine Verallgemeinerung und ist eigentlich falsch (eine Macht von zwei mit ungeraden Schrittgrößen wird typischerweise funktionieren genauso gut für die meisten Kollisionen Lösungsstrategien), aber nicht viele Leute betrachten die Alternativen und in der Welt der Hash-Tabellen, Prime Regeln.
Es gibt einen weiteren Faktor, der hier funktioniert, und das ist, dass die konstanten Hashing-Werte alle ungerade / prim und weit verstreut sein sollten. Wenn Sie eine gerade Anzahl von Einheiten (z. B. Zeichen) in dem zu hashenden Schlüssel haben, erhalten Sie mit allen ungeraden Konstanten einen gleichmäßigen anfänglichen Hashwert. Für eine ungerade Anzahl von Einheiten erhalten Sie eine ungerade Zahl. Ich habe damit experimentiert und nur die 50/50% Teilung war am Abend der Verteilung sehr viel wert. Natürlich, wenn alle Schlüssel gleich lang sind, ist das egal.
Das Hashing muss auch sicherstellen, dass Sie nicht denselben anfänglichen Hash-Wert für "AAB" wie für "ABA" oder "BAA" erhalten.
Ich denke, es ist der Code, um den Bucket auszuwählen. In den Code, den Sie eingefügt haben, steht:
%Vor%Das funktioniert gut für Größen, die Potenzen von zwei sind, da der letzte Effekt die unteren Bits von %code% ist. Für andere Größen hat %code% Bits in 0 und der bitweise Operator %code% verwirft diese Bits und hinterlässt "Löcher" in der Bucket-Liste.
Die allgemeine Formel für die Bucket-Auswahl lautet:
%Vor%Ich denke, es ist der Code, um den Bucket auszuwählen. In den Code, den Sie eingefügt haben, steht:
%Vor% Das funktioniert gut für Größen, die Potenzen von zwei sind, da der letzte Effekt die unteren Bits von h ist. Für andere Größen hat NELEMS(buckets)-1 Bits in 0 und der bitweise Operator & verwirft diese Bits und hinterlässt "Löcher" in der Bucket-Liste.
Die allgemeine Formel für die Bucket-Auswahl lautet:
%Vor%Das ist es, was Julienne Walker von Eternally Confuzzled über Hashtabellengrößen sagen muss:
Wenn es um Hash-Tabellen geht, am meisten Die empfohlene Tischgröße ist eine beliebige Primzahl Nummer. Diese Empfehlung wird gemacht weil Hashing im Allgemeinen ist falsch verstanden und schlechte Hash-Funktionen erfordern einen zusätzlichen Mischschritt von Division durch eine Primzahl, um a ähneln gleichmäßige Verteilung. Ein anderer Grund dass eine Tabellengröße empfohlen wird ist wegen mehrerer der Kollision Lösungsmethoden erfordern es zu arbeiten. In Wirklichkeit ist dies eine Verallgemeinerung und ist eigentlich falsch (eine Macht von zwei mit ungeraden Schrittgrößen wird typischerweise funktionieren genauso gut für die meisten Kollisionen Lösungsstrategien), aber nicht viele Leute betrachten die Alternativen und in der Welt der Hash-Tabellen, Prime Regeln.
Es gibt einen weiteren Faktor, der hier funktioniert, und das ist, dass die konstanten Hashing-Werte alle ungerade / prim und weit verstreut sein sollten. Wenn Sie eine gerade Anzahl von Einheiten (z. B. Zeichen) in dem zu hashenden Schlüssel haben, erhalten Sie mit allen ungeraden Konstanten einen gleichmäßigen anfänglichen Hashwert. Für eine ungerade Anzahl von Einheiten erhalten Sie eine ungerade Zahl. Ich habe damit experimentiert und nur die 50/50% Teilung war am Abend der Verteilung sehr viel wert. Natürlich, wenn alle Schlüssel gleich lang sind, ist das egal.
Das Hashing muss auch sicherstellen, dass Sie nicht denselben anfänglichen Hash-Wert für "AAB" wie für "ABA" oder "BAA" erhalten.