Une table de hachage bâclée doit être comprise au niveau de l'implémentation, alors prenez note de ce que vous avez remarqué en la lisant brièvement. Je n'ai pas pu le lire il y a 10 ans, mais cette fois j'ai pu le lire rapidement. (J'ai lu Adoptez Open JDK 13)
À l'intérieur du tableau, les données étaient gérées par les classes suivantes. En bref, il est mis en œuvre par adressage fermé.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
/ ** Vêtements intermédiaires * / }
En passant, Unified Map of Eclipse Collection (10.1) était également un adressage ouvert, mais il était enchaîné dans un tableau au lieu d'être chaîné avec un pointeur. Il semble que la raison en soit que vous souhaitez rendre le cache mémoire efficace comme l'adressage ouvert.
Calcul de la valeur de hachage. Lorsque le nombre d'éléments est petit, afin d'éviter que l'emplacement de stockage ne soit déterminé uniquement par les bits inférieurs, les 16 bits supérieurs sont XORed vers les 16 bits inférieurs de sorte que les bits supérieurs peuvent également être utilisés.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Comment rechercher la table de hachage. L'indice était la valeur obtenue en soustrayant 1 du nombre d'éléments n dans la table et en exécutant une opération AND.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
À propos, le nombre d'éléments dans le tableau (tab.length ci-dessus) semble être un multiple de 2, et lorsque -1 est défini à partir de cela, tous les bits sont définis, il semble donc que l'opération laisse les bits inférieurs.
Recommended Posts