Eine schlampige Hash-Tabelle sollte auf Implementierungsebene verstanden werden. Notieren Sie sich also, was Sie beim kurzen Lesen bemerkt haben. Ich konnte es vor 10 Jahren nicht lesen, aber diesmal konnte ich es schnell lesen. (Ich habe Adopt Open JDK 13 gelesen)
Innerhalb der Tabelle wurden Daten von den folgenden Klassen verwaltet. Kurz gesagt, es wird durch Closed Addressing implementiert.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
/ ** Mittlere Kleidung * / }
Abgesehen davon war die Unified Map der Eclipse-Sammlung (10.1) ebenfalls Open Addressing, dies wurde jedoch in einem Array anstatt mit einem Zeiger verkettet. Es scheint, dass der Grund darin besteht, dass Sie den Speichercache wie Open Addressing effektiv machen möchten.
Hash-Wert-Berechnung. Wenn die Anzahl der Elemente klein ist, werden die oberen 16 Bits zu den unteren 16 Bits XOR-verknüpft, um zu vermeiden, dass der Speicherort nur durch die unteren Bits bestimmt wird, so dass auch die oberen Bits verwendet werden können.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Wie man die Hash-Tabelle nachschlägt. Der Index war der Wert, der durch Subtrahieren von 1 von der Anzahl der Elemente n in der Tabelle und Ausführen einer UND-Operation erhalten wurde.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
Übrigens scheint die Anzahl der Elemente in der Tabelle (tab.length oben) ein Vielfaches von 2 zu sein, und wenn -1 daraus gesetzt wird, werden alle Bits gesetzt, so dass es den Anschein hat, als würde die Operation die unteren Bits verlassen.
Recommended Posts