Auslastung und Kapazität der Hash-Tabelle

Wenn die Anzahl der Einträge in der Hash-Tabelle überschreitet das Produkt der Auslastung und der aktuellen Kapazität, wie die die Kapazität erhöht wird?

InformationsquelleAutor user1054194 | 2011-11-18
  1. 5

    Hängt es von der zugrunde liegenden Implementierung. Zum Beispiel in der HashMap der zugrunde liegenden storage-array:

    transient Entry[] table;

    Den Eintrag Objekt enthält den Schlüssel und den Wert. Wenn die Kapazität nicht ausreichend (wie Sie richtig gesagt, überschreitet das Produkt der Auslastung und der aktuellen Kapazität), wird ein neues array erstellt und die alten Werte werden kopiert, in es.

    Sehen die sourcecode der HashMap für OpenJdk 7 und suchen für void resize(int newCapacity). Die wichtigsten Zeilen in der Methode sind:

    Entry[] newTable = new Entry[newCapacity];   //create the new table
transfer(newTable);                          //transfer and rehash the data
table = newTable;                            //from now on use the new table
threshold = (int)(newCapacity * loadFactor); //compute the new threshold

    threshold ist die maximale Anzahl von Elementen, die enthalten sein können, vor der Erhöhung der Größe wieder. transfer() auch aufwärmt Elemente, also Elemente werden wahrscheinlich gespeichert in verschiedenen array-Indizes im Vergleich zu Ihrer ursprünglichen position. Sie können Blick auf den code, ist überraschend einfach zu Lesen.

    InformationsquelleAutor stivlo
  2. 0

    Den load-Faktor ist ein Maß dafür, wie voll die hash-Tabelle erlaubt zu bekommen, bevor seine Kapazität automatisch erhöht. Wenn die Anzahl der Einträge in der Hash-Tabelle überschreitet das Produkt der Auslastung und der aktuellen Kapazität, die Kapazität erhöht wird durch den Aufruf der Methode rehash.

    hier ein überblick der Aufguss-Methode

     int oldCapacity = table.length;
Entry[] oldMap = table;

int newCapacity = oldCapacity * 2 + 1;
Entry[] newMap = new Entry[newCapacity];

    Wie Sie sehen können, eigentlich eine Verdoppelung der Kapazität der Eintrag [], wenn das Produkt der Auslastung und der aktuellen Kapazität erhöht die Schwelle.

    finden Sie in der Aufguss-Methode der hashtable-für mehr details.

    Aufguss-Methode

    InformationsquelleAutor dpsdce
  3. 0

    Wenn Sie erstellen eine neue Hashtabelle erstellt, ist es mit einer Standard-Größe und Auslastung.

    Quellcode 

    public Hashtable() {
        this(11, 0.75f);
}

    Wenn Sie das hinzufügen von Elementen in es

    prüft es die 

    if (count >= threshold) {

}

    bzw. erstellt ein neues array und kopiert als Stivlo sagte.

    private transient Entry[] Tabelle;

    InformationsquelleAutor r0ast3d
Schreibe einen Kommentar