Warum ist die Größe 127 (prime) besser als die 128 für eine hash-Tabelle?

Angenommen, dass simple uniform hashing, das Wesen, jedem gegebenen Wert ist ebenso wie hash in die slots der hash. Warum ist es besser, eine Tabelle mit der Größe 127 und nicht 128? Ich verstehe wirklich nicht, was ist das problem mit der Potenz von 2 zahlen. Oder, wie es eigentlich überhaupt einen Unterschied macht.

Beim Einsatz der division-Methode,
wir in der Regel zu vermeiden, bestimmte Werte
von m (Tabellengröße). Zum Beispiel, m
sollte es nicht eine Potenz von 2 ist, denn wenn m
= 2^p , dann ist h(k) ist genau die p niedrigsten bits von k.

Nehmen wir an, die Elemente, die sind nur zwischen 1 und 10000 und ich nahm die Größe der Tabelle als 128. Wie kann 127, besser zu sein?
Also 128 ist 2^6 (1000000) und 127 ist 0111111. Welchen Unterschied macht dies? Alle zahlen (als Hash) sind immer noch die niedrigsten p-bits von k 127 zu. Habe ich etwas falsch gemacht?

Ich bin auf der Suche nach einige Beispiele, wie ich kann wirklich nicht verstehen, warum das schlecht ist. Vielen Dank im Voraus!

PS: ich bin mir bewusst:
Hash-Tabelle: warum sollte die Größe Primzahl?

  • > PS: I am aware of: Hash table: why size should be prime? - dann Lesen Sie es erneut, oder der link durch diese one
  • Der thread verlinkt wurde, macht eine Vermutung, dass die Elemente innerhalb einer Beziehung ("Dann, wenn eine Reihe von Zeichenfolgen alle mit dem gleichen ersten char zugeführt, dann werden die Ergebnisse alle gleich modulo k")
  • Sorry, aber wenn Sie darauf bestehen, dass es nicht notwendig ist zu optimieren, die gegen Kollisionen für Ihre spezifischen hash-Werte, die Sie verwirren könnten Indizierung mit hashing. Eine perfekte hash-kann verwendet werden als index, aber alle möglichen Werte müssen bekannt sein, bis vor. Mit einer solchen Konfiguration ist es egal, auch wenn die Anzahl der buckets, ist tatsächlich ein Fakt (n!). Das ist aber nicht die generische Wissenschaft hinter hashing.
  • OT: Clash ist ein sehr schönes screen-Namen verwenden, wenn im Gespräch über hash-Kollisionen 🙂
  • Ich bin nicht darauf bestehen, dass ich keine Kollisionen. Ich versuche nur zu verstehen, warum eine Primzahl ist, obwohl kleiner als eine Potenz von 2 ist, ist besser als eine Potenz von zwei. Den link den du mir gegeben hast, bezieht sich auf eine situation, wo eine bestimmte Gruppe von Elementen ist wahrscheinlicher zu geschehen. Vielen Dank für Ihre Antworten!
  • möglich, Duplikat der Warum Einstellung Hashtabelle der Länge eine Primzahl ist eine gute Praxis ?
  • Da Reale Daten fast nie gleichverteilt. Wenn Sie hash-strings mit 128, erhalten Sie 26 Eimer ungleichmäßig gefüllt und der rest leer. Wenn Sie 127 Sie werden wahrscheinlich bekommen Sie alle gefüllt gleichmäßiger.
  • Nur die Korrektur eines Tippfehler: 128 2^7, 2^6.

InformationsquelleAutor Clash | 2011-05-08
  1. 21

    Alle zahlen (als Hash) sind immer noch die niedrigsten p-bits von k 127 zu.

    Falsch ist (oder ich falsch verstanden..). k % 127 hängt von allen bits von k. k % 128 hängt nur von der 7 niedrigsten bits.

    EDIT:

    Haben Sie eine perfekte Verteilung zwischen 1 und 10.000. 10,000 % 127 und 10,000 % 128 beide schalten Sie dies in eine ausgezeichnete kleineren Vertrieb. Alle Eimer enthalten 10,000 /128 = 78 (oder 79) Elemente.

    Wenn Sie eine Verteilung zwischen 1 und 10.000, die parteiisch ist, denn {x, 2x, 3x, ..} häufiger auftreten. Dann ein prime Größe geben wird, eine viel, viel bessere Verteilung wie in diesem Antwort. (Es sei denn x ist genau das, was prime Größe.)

    So, das abschneiden der high-bits (mit einer Größe von 128) ist überhaupt kein problem wenn die Verteilung in den unteren bits ist gut genug. Aber, mit realen Daten und realen schlecht entwickelt, hash-Funktionen, müssen Sie diese high-bits.

    • Sie sind Recht Ishtar. Aber dies ist äquivalent zu sagen, dass ein Vielfaches von 128 % 128 (die höherwertigen bits sind immer Vielfache von 128) wird zu 0, was für mich, ist offensichtlich. 127 auf der anderen Seite hat diese Eigenschaft nicht haben, aber es wird noch mehr Vielfache von 127, also das sollte noch schlimmer werden, sollte es nicht? Ich verstehe nicht das problem mit dem ignorieren der höherwertigen bits.
    • Das eigentliche problem bei der ignoriert die höheren bits ist, dass Leute schreiben, miese hash-Funktionen. Also, wenn Ihre Tabelle muss eine gute Verteilung es wäre dumm, zu ignorieren, diese zusätzlichen bits Aufwand. Gut hashes ist hart, also mit einer Top Größe, die Sie sind einfach nur tolerant.
    • das problem mit dem ignorieren der höheren bits ist, dass es normal ist für einen gegebenen Datensatz zu variieren nur in einigen bits. (E. g., eine Reihe von string-Variablen repräsentieren Pfade Zustimmen könnten auf das erste Dutzend Zeichen. Oder, Alter könnte Stimmen alle, aber die unteren 6 bits.) Wenn das sind die bits, die Sie werfen, sind Sie gehen, um eine Menge von Kollisionen.
    InformationsquelleAutor Ishtar
  2. 5

    Division-Methode

    ", Wenn mit der Teilung Methode, die wir in der Regel zu vermeiden, bestimmte Werte von m
    (Tabellengröße). Zum Beispiel, m sollte nicht die macht der 2, da, falls m =
    2p , dann h(k) ist nur die p niedrigsten bits von k."

    --CLRS

    Zu verstehen, warum m = 2p verwendet nur die p niedrigsten bits von k, müssen Sie zuerst verstehen, die modulo-Hashfunktion h(k) = k % m.

    Den Schlüssel geschrieben werden kann in Bezug auf ein quotient q, und den Rest r.

    k = nq + r

    Wahl der quotient zu q = m erlaubt uns zu schreiben k % m einfach wie der Rest in der obigen Gleichung ist:

    k % m = r = k - nm,  where r < m

    Daher k % m entspricht kontinuierlich Subtraktion m insgesamt n mal (bis r < m):

    k % m = k - m - m - ... - m,  until r < m

    Können versuchen hashing-Schlüssel k = 91 mit m = 24 = 16.

      91 = 0101 1011
- 16 = 0001 0000
----------------
  75 = 0100 1011
- 16 = 0001 0000
----------------
  59 = 0011 1011
- 16 = 0001 0000
----------------
  43 = 0010 1011
- 16 = 0001 0000
----------------
  27 = 0001 1011
- 16 = 0001 0000
----------------
  11 = 0000 1011

    So 91 % 24 = 11 ist nur die binäre form 91 nur mit der p=4 niedrigsten bits übrig.

    Wichtige Unterscheidung:

    Dies bezieht sich speziell auf die division-Methode der Vermischung. In der Tat, das Gegenteil ist wahr für die Multiplikation-Methode wie bereits in CLRS:

    "Ein Vorteil der Multiplikation-Methode ist, dass der Wert von m ist nicht kritisch... Wir wählen in der Regel [m] eine Potenz von 2 ist, da können wir dann leicht implementieren Sie die Funktion auf den meisten Computern."

    InformationsquelleAutor bcorso
  3. 3

    Nick ist richtig, dass im Allgemeinen die hash-Tabelle Größe spielt keine Rolle. Aber in dem speziellen Fall, wo offene Adressierung mit Doppel-hashing verwendet wird (in dem das Intervall zwischen den Sonden wird berechnet, indem eine weitere hash-Funktion), dann ist eine Primzahl-Größe hash-Tabelle ist am besten, um sicherzustellen, dass alle hash-Tabelle Einträge vorhanden sind, die für ein neues element (als Corkscreewe erwähnt.)

    InformationsquelleAutor Neil G
  4. 3

    First off, ist es nicht über die Kommissionierung eine Primzahl. Für Ihr Beispiel, wenn Sie wissen, dass Ihre Daten eingestellt werden im Bereich von 1 zu 10.000, Kommissionierung 127 oder 128 wird keinen Unterschied machen, bc, es ist ein schlechtes design Wahl.

    Eher, es ist besser, wählen Sie eine WIRKLICH große prime wie 3967 für dein Beispiel, so dass jeder die Daten eigene Schlüssel/Wert-paar. Sie wollen einfach nur, um auch Kollisionen minimieren. Kommissionierung 127 oder 128 für dein Beispiel macht keinen Unterschied bc 127/128 Eimer wird gleichmäßig gefüllt (das ist schlecht und verschlechtert das Einfüge-und lookup-Laufzeit O(1) O(n)) im Gegensatz zu 3967 (der die Aufrechterhaltung der O(1) mal)

    EDIT #4

    Entwurf der "hash-Funktion" ist
    etwas wie eine schwarze Kunst. Kann es sein
    stark beeinflusst von den Daten, die
    soll gespeichert werden, in der
    hashing-basierte Daten zu Struktur, also die
    Diskussion über eine sinnvolle hashing
    Funktion kann oft streunenden in einer
    Diskussion über bestimmte Eingänge.

    Warum Primzahlen sind "bevorzugt", man hat
    zu prüfen, einen "Widersacher" - Analyse,
    das ist angenommen, ich entwarf ein Allgemeines
    Hash-basierten Datenstruktur, wie
    würde es führen angesichts der schlimmsten Eingang
    von einem Widersacher. Da die Leistung
    diktiert wird durch Hash-Kollisionen, die
    Frage was ist der hash
    verwenden Sie minimiert, dass die Kollision in der
    schlimmsten Zustand. Eine solche Bedingung ist
    wenn die Eingabe immer zahlen
    teilbar durch einige integer, sagen wir 4. Wenn
    verwenden Sie N = 128 dann eine beliebige Anzahl
    teilbar durch 4 mod 128 ist noch
    teilbar durch 4, was bedeutet, dass nur
    Eimer 4, 8, 12, ... sind immer immer
    verwendet, was zu einer 25% - Auslastung
    die Daten-Struktur. Primzahlen effektiv
    reduziert die Wahrscheinlichkeit einer solchen
    Szenario Auftritt, mit den Nummern > N.

    • Korrigieren Sie mich, wenn ich falsch Liege, aber 3976 mehrere Werte in jeder Gruppe.
    • Ich denke, er Las 1000. Ich weiß, 127 und 128 sind schlecht für 10000. Was ich verstehen will ist, warum ist es besser einen prime-und nicht irgendeine andere Nummer? Warum ist eine Potenz von 2 ist schlecht? Sagen dann, ich nahm 16384 (2^14). Warum ist 16381 besser? Dank
    • Sorry, typoe: ich meinte 3967. Gut, es geht zurück auf die Konstruktion der hash-Funktion. Für jetzt, wenn Sie annehmen, eine bare, hash-Funktion, die dauert nur eine Zahl (zwischen 1 und 10.000) und nimmt Sie modulo von 3967 es praktisch gewährleistet, dass wir keine Kollisionen in der Tabelle. Auch die große prime macht unser Tisch fast 4x größer und wird gewährleisten, dass die Kollisionen haben eine geringe Wahrscheinlichkeit passiert
    • Meinst du, dass die Größe der Tabelle sollte größer sein als die Bandbreite der möglichen hash-Werte? Eine Größe von 127/128 mit hash-Funktion 1-10,000 ist in Ordnung, wenn Sie speichern 50-Elemente.
    • Ich sehe nicht ein, warum 127 ist "klein" und 3967 ist "ganz groß". Alles, was zählt, ist der Auslastung. Wenn Sie die Speicherung von 10 Elementen, 127 ist völlig in Ordnung, und wird wahrscheinlich entstehen weniger cache-misses.
    • Ich gehe nicht in die load-Faktor/balancing, aber ich will hinzufügen, mehr darüber, warum wir Primzahlen statt die macht der 2 für hashing (mit einem Freund diskutiert): der Grund, warum wir vermeiden eine Potenz von 2 ist, die hash-Funktionen sind letztlich die Rückgabe einem binären Ergebnis, und wenn Sie eine Potenz von zwei, Sie sind im Grunde abhacken der oberen Hälfte des hash-seit binäre ist eine Potenz von zwei. Idealerweise sollten Sie jedes element in dem hash-Wert spielen eine bedeutende Rolle in der hash-position, so dass durch auswählen einer Primzahl (oder zumindest eine #, die nicht eine Potenz von zwei), dann machst du einen besseren job mit den ganzen hash.
    • was meinst du mit "Binär ist eine Potenz von zwei"? Ich dachte, binary war einfach eine andere Basis für die Darstellung von zahlen. Ich sehe auch nicht, wie die Hälfte der hash ist immer abgehauen, wenn eine Potenz von zwei ist, verwendet.
    • Kaufe ich nicht, die Erklärung. Wenn Sie mod von 127, bist du immer noch nicht über die gesamte hash. Sie verlieren alle, aber (etwas weniger als) 7 bits von Informationen. Es ist nur viel schwerer zu sehen, welche bits von Informationen, die Sie verlieren. Denkst du, dass modding von 3 ist besser als modding von 4?
    • G + alle anderen: wenn ich lese zuerst diese Frage, dachte ich, es wurde mehr über "warum Primzahlen" als Gegensatz zu "was ist falsch mit der power von 2 s???" also ich habe mit Freunden an der UW und an der UC Berkeley und präsentieren Ihnen die abschließende Bearbeiten (done zu den besten meiner Fähigkeiten) ich mache oben. Ich hoffe, es hilft, verdeutlicht, warum eine Potenz von 2 ist, sind keine großartigen Kandidaten im Vergleich zu Primzahlen!

    InformationsquelleAutor Matthew Chan
  5. 2

    Wenn Sie eine perfekte hash-Funktion, die eine gleichmäßige Verteilung, dann ist es egal.

    • Wenn nicht, kann es passieren, dass eine rekursive Kollision angezeigt wird, so dass es unmöglich für ein bestimmtes Element gespeichert werden soll, in die hashtable. Mit Primzahl-Größe (oder perfekte hash-Funktion), wird dies nicht auftreten.
    • Das würde wirklich davon abhängen, was die Tabelle nicht auf eine Kollision.
    • Meine hash-Funktion ist die modulo-operator. Dies ist nicht eine perfekte hash, oder? Ich habe nicht wirklich erreicht perfektes hashing noch, aber von was ich gelesen habe dieser hat mehr zu tun in der Tatsache, dass keine neuen Schlüssel eingefügt werden, die Elemente sind statisch.
    • das ist eine ziemlich schlechte hash-Funktion, wenn Sie modding durch die Größe der Tabelle, weil die höherwertigen bits werden nicht verwendet die hash-Funktion. Warum gehst du nicht einfach kopieren std::hash<int>?
    • dies ist, was ich versuche zu verstehen. Wie ist es mit einem prime, das ist in der Nähe eine Blüte zwei-oder jede andere Zahl in der Nähe eine Potenz von zwei sein, besser als eine Potenz von zwei sein? BTW: Es gibt keine hash in std soweit ich weiß. Es gibt std::map, aber ich denke, im inneren wirkt es wie ein binärer Baum (könnte falsch sein)
    • Hast du meine Antwort? Auch std::hash Hinzugefügt wurde in C++0x, so können Sie den code finden Sie online, wenn Sie nicht bereits installiert haben.
    • Ich wollte sehen, Ihre Antwort. Das Buch mit dem modulo-operator als hash-Funktion für dieses Beispiel nicht die doppelte hashing.
    • Doppel-hashing hat nichts zu tun mit der hash-Funktion; es hat damit zu tun, wie Kollisionen aufgelöst werden. Das ist Teil der Implementierung der hash-Tabelle. Es könnte hilfreich sein, Lesen Sie den Wikipedia-Artikel über hash-Tabellen.
    • G, Danke für die Erklärung, aber es ist nicht mit double-hashing entweder die slot verwendet werden, ist das Ergebnis der hash-Funktion, die einfach den modulo-operator

    InformationsquelleAutor Nick ODell
  6. 2

    Wikipedia hat tatsächlich eine gute Zusammenfassung dazu:

    http://en.wikipedia.org/wiki/Hash_table

    Weisen Sie darauf hin, dass einige hash-Funktionen sind speziell für den Betrieb NUR mit Primzahlen. Dieser Artikel erklärt, warum Potenzen von zwei sind schlecht:

    http://www.concentric.net/~Ttwang/tech/primehash.htm

    InformationsquelleAutor
  7. 0

    Ich nicht beweisen kann Sie es nicht mehr, obwohl ich erinnere mich, dass dies in einer Prüfung an der Universität vor einer million Jahren, aber eine optimale hash-Größen sind nicht nur prime. Sie wollen wählen eine Primzahl N, so dass N = 4*M − 1 (wo M ist ebenfalls eine ganze Zahl).

    Macht 31 eine bessere Anzahl der buckets als 29. M ist 8, wenn N ist 31, aber es gibt keine Integrale M wenn N 29.

    Wie gesagt, ich weiß es nicht mehr, die Mathematik, die dies beweisen. Es war in einen Theorie-Kurs gelehrt von Rachel Manber gemacht, Udi Frau, die vor rund 25 Jahren oder so.

    InformationsquelleAutor tchrist
  8. 0

    hier ist ein Weg zu verstehen, " k % 127 hängt von allen bits von k. k % 128 hängt nur von der 7 niedrigsten bits." .

    k % 128 ist gleich mit k & (2^7-1) .zum Beispiel: 129 % 128 = 1 , Binär: 1000 0001 & 0111 1111 =0000 0001,jede hight bit (2^7-1) ist 0 ,was bedeutet, dass es Dosis keine Rolle, was die hohe position ist. aber das übersetzen ist ungültig für zahlen, die nicht gleich 2^n.

    jetzt lassen Sie uns nehmen einen Blick an, wie wir tun, division Dezimal 129 % 127 ,der erste Blick auf die höchste position 1,die weniger als 127 ist,dann bekommen wir den nächsten Punkt 2 kombinieren, die mit der Faust bekommen wir 12 , 12 ist kleiner als " 127 " ist,dann kombinieren Sie mit 9, was bedeutet, 129 ,geteilt durch 127 der Rest 2 ist,könnten wir schreiben dies in der Mathematik:129 = 1 * 127 +2 so haben wir 2 [all dies wird als Long_division] ,und es ist das gleiche in der Binären division,jetzt wissen wir k % 127 hängt von allen bits von k

    InformationsquelleAutor paxi
  9. 0

    Ich glaube, dass es nur zu tun hat mit der Tatsache, dass Computer funktionieren
    mit im base 2. Etwas ähnliches geschieht mit der Basis 10.

    ...

    Kommissionierung eine ausreichend große, non-power-of-two Reihe wird sicherstellen, dass die hash-Funktion ist wirklich eine Funktion, alle input-bits, anstatt
    eine Teilmenge von Ihnen.

    Von Warum hash-Tabellen sollten eine Primzahl-Größe.

    InformationsquelleAutor Ste_95
Schreibe einen Kommentar