HashMap mise en œuvre en Java. Comment le seau de calcul de l'indice de travail?

Le hachage est lui-même calculé par le hashCode() méthode de l'objet que vous essayez de magasin.

Ce que vous voyez ici est le calcul de la "seau" pour stocker l'objet basé sur le hachage h. Idéalement, pour éviter les collisions, vous avez le même nombre de compartiments comme c'est le maximum réalisable valeur de h - mais qui pourrait être trop gourmandes en mémoire. Par conséquent, vous ont généralement un faible nombre de compartiments avec un danger de collision.

Si h est, disons, 1000, mais vous avez seulement 512 seaux dans votre sous-jacente de tableau, vous devez savoir où placer l'objet. Généralement, un mod opération sur h serait suffisant, mais c'est trop lent. Compte tenu de la propriété interne de HashMap que le sous-jacent de la matrice de toujours a nombre de compartiments égal à 2^n du Soleil, les ingénieurs ont pu utiliser l'idée de h & (length-1), il fait un au niveau du bit ET avec un nombre composé de tous 1's, pratiquement lecture seulement le n plus bas les bits de la table de hachage (qui est le même que le fait de faire h mod 2^n, seulement beaucoup plus rapide).

Exemple:

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)

La réponse ci-dessus est très bonne, mais je tiens à expliquer pourquoi Java peut utiliser indexFor pour créer des index

Exemple, j'ai un HashMap comme ceci (ce test est sur Java7, je vois Java8 changement HashMap beaucoup, mais je pense que cette logique du toujours très bon)

//Default length of "budget" (table.length) after create is 16 (HashMap#DEFAULT_INITIAL_CAPACITY)
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("A",1); //hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5
hashMap.put("B",2); //hash("B")=70, indexFor(hash,table.length)=70&(16-1) = 6
hashMap.put("P",3); //hash("P")=85, indexFor(hash,table.length)=85&(16-1) = 5
hashMap.put("A",4); //hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5
hashMap.put("r", 4);//hash("r")=117, indexFor(hash,table.length)=117&(16-1) = 5

Vous pouvez voir l'index de l'entrée avec la touche "A" et de l'objet avec les principaux "P" et de l'objet avec les principaux "r" ont le même indice (= 5). Et voici le débogage de suite après j'exécute le code ci-dessus

Table dans l'image est ici

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    transient HashMap.Entry<K, V>[] table;
    ...
}

=> je vois

Si les indices sont différents, une nouvelle entrée sera ajouter à la table

Si l'indice est même et hash est même, la nouvelle valeur sera mise à jour

Si l'indice est même et hash est différents, une nouvelle entrée sera point à l'ancienne entrée (comme un LinkedList). Alors, vous savez pourquoi Map.Entry ont champ next

static class Entry<K, V> implements java.util.Map.Entry<K, V> {
        ...
        HashMap.Entry<K, V> next;
}

Vous pouvez vérifier à nouveau par lire le code dans HashMap.

Comme maintenant, vous pouvez penser que HashMap sera jamais besoin de changer la taille (16) parce que indexFor() toujours valeur de retour <= 15 mais il pas correcte.

Si vous regardez HashMap code

 if (this.size >= this.threshold ...) {
      this.resize(2 * this.table.length);

HashMap redimensionner le tableau (le double de la longueur de la table) lorsque size >= threadhold

Qu'est-ce que threadhold? threadhold est calculé ci-dessous

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75F;
...
this.threshold = (int)Math.min((float)capacity * this.loadFactor, 1.07374182E9F); //if capacity(table.length) = 16 => threadhold = 12

Quel est le size? size est calculé ci-dessous.

Bien sûr, size ici n'est pas table.length .

Tout le temps de vous mettre une nouvelle entrée HashMap et HashMap besoin de créer une nouvelle entrée (à noter que HashMap de ne pas créer une nouvelle entrée lorsque la clé est la même, il vient de remplacer la valeur pour existaient entrée) puis size++

void createEntry(int hash, K key, V value, int bucketIndex) {
    ...
    ++this.size;
}

Espoir aide