Java: Eine "prime" - Reihe oder "power of two" als HashMap-Größe?

Viele Bücher und tutorials sagen, dass die Größe einer Hashtabelle muss eine Primzahl gleichmäßig zu verteilen und die Tasten in alle buckets. Aber Java ist HashMap verwendet immer eine Größe, die eine Potenz von zwei. Sollte es nicht mit einem prime? Was ist besser, ein "prime" - oder "power of two", wie die hash-Tabelle der Größe?

  • Ich bezweifle, dass Sie wirklich genau sagen, dass, und wenn Sie tun, Sie sind falsch. Das ist nur ein Weg, es zu tun.
InformationsquelleAutor Nikunj Banka | 2013-03-15
  1. 24

    Mit einer Leistung von zwei effektiv-Masken aus oberen bits der hash-code. So eine schlechte hash-Funktion könnte besonders schlecht in diesem Szenario.

    Java HashMap verringert diese durch misstrauten das Objekt hashCode() Umsetzung und anwenden einer zweiten Stufe der Vermischung zu Ihrem Ergebnis:

    Gilt eine zusätzliche hash-Funktion zu einem bestimmten hashCode, die einen Schutz gegen schlechte Qualität von hash-Funktionen. Dies ist entscheidend, da die HashMap verwendet power-of-two length hash-Tabellen, die sonst Kollisionen für die hashCodes, die unterscheiden sich nicht in den unteren bits.

    Wenn Sie eine gute hash-Funktion, oder etwas ähnliches tun, was HashMap hat, spielt es keine Rolle, ob Sie Primzahlen usw. als die Größe der Tabelle.

    Wenn auf der anderen Seite, die hash-Funktion ist von unbekannten oder von schlechter Qualität, dann mit einer Primzahl wäre eine sicherere Wette. Es wird jedoch dynamisch-große Tabellen tricker zu implementieren, da alle von einer plötzlichen Sie müssen in der Lage sein zu produzieren Primzahlen, anstatt nur die Multiplikation der Größe mit einem Konstanten Faktor.

    • Aus Neugier: Warum? (oder haben Sie auch Referenz/links, die erklären, diese)?
    • Sind Sie sicher, die Größe des Tisches egal ist? Ist das nicht der Punkt, der eine gute hash-Funktion verteilt die Daten in der Tabelle, um die Zahl der Kollisionen reduzieren? Aber wenn die Tabelle sehr klein ist, dann Kollisionen zu erhöhen, unabhängig von der hash-Funktion. Bin ich etwas fehlt?
    • Es ist klar, dass größer ist besser (oder zumindest kaum schlechter sein). Jedoch, für ähnliche Größen, es gibt keinen Grund zu bevorzugen, Primzahlen usw., solange die hash-Funktion ist von hoher Qualität.
    • Hab es, danke.
    • Ich habe umformuliert, dass ein Teil der Antwort, da es nicht ganz klar war, was ich meinte.
    • Die Kapazität der Tabelle erhöht (um etwa einen Faktor zwei), wenn die Auslastung überschritten wird, so dass, auch wenn die anfängliche Kapazität der Tisch ist sehr klein, die Tabelle wird erweitert, um eine geeignete Größe für die maximale Anzahl von Einträgen enthalten. Eine gute erste Vermutung bedeutet weniger ändern der Größe als der Tisch wächst, aber eine schlechte erste Vermutung wird noch schließlich produzieren ein effizientes Tabelle.

    InformationsquelleAutor NPE
  2. 4

    Standard HashMap-Implementierung hat eine hash Methode, die aufwärmt Ihr Objekt die hashcode zu vermeiden, die Falle. Der Kommentar vor der hash() Methode liest:

    /**
 * Retrieve object hash code and applies a supplemental hash function to the
 * result hash, which defends against poor quality hash functions.  This is
 * critical because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
    InformationsquelleAutor assylias
  3. 4

    Der einzige Weg zu wissen, was besser ist zwischen Haupt-und power-of-two ist es zum benchmark.

    Vor vielen Jahren, beim schreiben eines assembler, deren Leistung hing stark auf symbol-talbe-lookup, getestet habe ich dies mit einem großen block generierten Bezeichner. Auch mit einer naiv-mapping, fand ich, dass die Kraft-der-zwei, wie erwartet, hatte weniger gleichmäßige Verteilung und längere Ketten als eine ähnlich große prime Anzahl der buckets. Es lief noch schneller, weil die Geschwindigkeit von Eimer-Auswahl durch bit-Maskierung.

    Nehme ich stark an java.util-Entwickler würden nicht gegriffen haben, um die extra-hashing-und Kraft-der-zwei ohne benchmarking ist es, gegen eine prime Anzahl der buckets. Es ist eine sehr offensichtliche Sache zu tun ist, wenn das entwerfen einer Hash-Datenstruktur.

    Deshalb, ich bin mir sicher, dass die Neuauflage und Kraft-der-zwei-Größe bietet eine bessere Leistung für typische Java-hash-maps als eine prime Anzahl der buckets.

    InformationsquelleAutor Patricia Shanahan
  4. 0

    Leistung/Berechnung Zeit Sicht-power-of-two Größen berechnet werden kann, mit nur bit-Maskierung, das geht schneller als integer-division, die sonst benötigt würden.

    InformationsquelleAutor mtk
  5. 0

    Sollten Sie wahrscheinlich verwenden prime Größe, hash-Tabellen, wenn Sie verwenden quadratische Sondieren für die kollisionsauflösung. Wenn Sie ein prime Größe Tisch, quadratische Sondieren wird, trifft die Hälfte der Einträge, weniger, wenn es ist nicht eine Primzahl. So könnten Sie nicht finden, einen geeigneten Ort zu speichern Sie den Eintrag, auch wenn Ihre hash-Tabelle ist weniger als halb voll. Seit Java hash-maps nicht verwenden quadratische Sondieren, gibt es keine Notwendigkeit zu verwenden Primzahlen als Größe.

    InformationsquelleAutor Drunix
Schreibe einen Kommentar