Comment un Java HashMap de gérer les différents objets avec le même code de hachage?

Une hashmap fonctionne comme ceci (c'est un peu simplifié, mais il illustre le mécanisme de base):

Il a un certain nombre de "seaux", qu'elle utilise pour stocker des paires clé-valeur dans. Chaque compartiment dispose d'un numéro unique - c'est ce qui identifie le seau. Quand vous mettez une paire clé-valeur dans la carte, la table de hachage va regarder le code de hachage de la clé, et de stocker la paire dans le seau dont l'identificateur est le code de hachage de la clé. Par exemple: Le code de hachage de la clé est de 235 -> la paire est stocké dans un seau numéro 235. (À noter qu'un compartiment peut stocker plus d'une paire clé-valeur).

Lorsque vous recherche une valeur dans la table de hachage, en lui donnant une touche, il va d'abord regarder le code de hachage de la clé que vous avez donné. La table de hachage va ensuite chercher dans le seau, puis il compare la clé qui vous a donné les clés de toutes les paires dans le seau, en les comparant avec equals().

Maintenant, vous pouvez voir comment cela est très efficace pour la recherche de paires clé-valeur dans une carte: par le code de hachage de la clé de la table de hachage sait immédiatement où seau à regarder, de sorte qu'il n'a qu'à tester par rapport à ce qui est dans le seau.

Regardant le mécanisme ci-dessus, vous pouvez également voir quelles sont les conditions nécessaires sur la hashCode() et equals() méthodes de touches:

• Si les deux touches sont les mêmes (equals() retourne true lorsque vous comparez entre eux), leur hashCode() méthode doit renvoyer le même nombre. Si les touches de violer la présente, ensuite, les clés de l'égalité peuvent être stockées dans des compartiments différents, et la table de hachage ne serait pas en mesure de trouver des paires clé-valeur (parce qu'il va dans le même seau).

• Si les deux clés sont différentes, alors il n'a pas d'importance si leurs codes de hachage sont les mêmes ou pas. Ils seront stockés dans le même seau si leurs codes de hachage sont les mêmes, et dans ce cas, la table de hachage va utiliser equals() de les distinguer.

HashMap est un tableau de Entry objets.

Envisager HashMap comme un tableau d'objets.

Ont un oeil à ce que ce Object est:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Chaque Entry objet représente une paire clé-valeur. Le domaine next se réfère à un autre Entry objet si un seau a plus d'un Entry.

Parfois, il peut arriver que des codes de hachage pour 2 objets différents sont les mêmes. Dans ce cas, deux objets seront enregistrées dans un seau et va être présenté comme une liste chaînée.
Le point d'entrée est le plus récemment ajouté objet. Cet objet fait référence à un autre objet avec la next de champ, et ainsi de suite. La dernière entrée se réfère à null.

Lorsque vous créez un HashMap avec le constructeur par défaut

HashMap hashMap = new HashMap();

Le tableau est créé avec la taille 16 et défaut de 0,75 équilibrer la charge.

L'ajout d'une nouvelle paire clé-valeur

1. Calculer hashcode pour la clé
2. Calculer la position hash % (arrayLength-1) où l'élément doit être placé (seau nombre)
3. Si vous essayez d'ajouter une valeur à une clé qui a déjà été enregistré dans HashMap, alors la valeur est écrasée.
4. Sinon, l'élément est ajouté au seau.

Si le seau a déjà au moins un élément, un nouveau est ajouté et placé dans la première position du seau. Son next champ fait référence à l'ancien élément.

Suppression

1. Calculer hashcode pour la clé donnée
2. Calculer seau nombre hash % (arrayLength-1)
3. Obtenir une référence à la première Entrée de l'objet dans le seau et par le biais de la méthode equals itérer sur toutes les entrées dans le seau. Finalement, nous allons trouver la bonne Entry.
   Si un élément souhaité n'est pas trouvé, le retour null

Voici une description sommaire de HashMaps'mécanisme, pour Java 8 version, (il peut être légèrement différent de la version 6 de Java).

Structures de données

• Table de hachage
  
  La valeur de hachage est calculée à l'aide d' hash() sur la clé, et à décider lequel seau de la table de hachage à utiliser pour une clé donnée.
• Liste liée (individuellement)
  
  Lorsque le nombre d'éléments dans un seau est petit, une seule liste liée est utilisé.
• Rouge-Noir arbre
  
  Lorsque le nombre d'éléments dans un seau est grand, rouge-noir arbre est utilisé.

Classes (interne)

• Map.Entry
  
  Représenter une entité unique dans la carte, la clé/valeur de l'entité.

• HashMap.Node
  
  Liste liée version de nœud.

  Il pourrait s'agir d':

  • Un compartiment de hachage.
    
    Parce qu'il a une valeur de hachage de la propriété.
  • Un nœud dans la seule liste liée, (ainsi également à la tête de la linkedlist).
• HashMap.TreeNode
  
  L'arbre de la version de nœud.

Champs (interne)

• Node[] table
  
  Le seau de table, (chef de listes chaînées).
  
  Si un seau ne contient pas d'éléments, il est alors nulle, donc que prendre de l'espace de référence.
• Set<Map.Entry> entrySet
  Ensemble d'entités.
• int size
  
  Nombre d'entités.
• float loadFactor
  
  Indiquer le degré de remplissage de la table de hachage est autorisé, avant de la redimensionner.
• int threshold
  
  La prochaine taille à laquelle redimensionner.
  
  Formule: threshold = capacity * loadFactor

Méthodes (interne)

• int hash(key)
  
  Calculer le hachage à clé.

• Comment carte de hachage dans le seau?
  
  Utiliser la logique suivante:

  static int hashToBucket(int tableSize, int hash) {
      return (tableSize - 1) & hash;
  }

Sur la capacité

Dans la table de hachage, de la capacité signifie que le comte de seau, il pourrait être obtenir de table.length.

Pourrait également être calculée à l'aide d' threshold et loadFactor, donc pas besoin d'être défini comme un champ de classe.

Pourrait obtenir de la capacité effective via: capacity()

Opérations

• Trouver entité par clé.
  
  D'abord trouver le seau par la valeur de hachage, puis la boucle est lié de recherche ou la liste triée de l'arbre.
• Ajouter une entité à clef.
  
  D'abord trouver le seau en fonction de la valeur de hachage de la clé.
  
  Ensuite, essayez de trouver la valeur:
  • Si trouvé, remplacer la valeur.
  • Sinon, ajouter un nouveau nœud au début de la liste chaînée, ou insérez-le dans triés arbre.
• Redimensionner
  
  Lorsque threshold atteint, permettra de doubler la table de hachage de la capacité(table.length), puis d'effectuer une re-hachage sur tous les éléments de reconstruire la table.
  
  Cela pourrait être une opération coûteuse.

Performance

• obtenir des & mettre
  
  Complexité temporelle est O(1), parce que:
  • Seau est accessible par un index de tableau, donc O(1).
  • Liste liée dans chaque seau est de petite longueur, pourrait donc vue comme O(1).
  • La taille de l'arbre est également limitée, parce que la volonté d'étendre la capacité de & re-hachage lors de l'élément nombre augmenter, donc pourrait le voir comme O(1), pas O(log N).

Vous êtes trompé sur le point trois. Deux entrées peuvent avoir le même code de hachage, mais de ne pas être égal. Jetez un oeil à la mise en œuvre de HashMap.obtenez de l'OpenJdk. Vous pouvez voir qu'il vérifie que les valeurs de hachage sont égaux et que les touches sont égaux. Étaient point trois vrai, alors il serait inutile de vérifier que les clés sont égaux. Le code de hachage est comparé à l'avant de la clé parce que l'ancien est plus efficace en comparaison.

Si vous êtes intéressés à en apprendre un peu plus à propos de cela, jetez un oeil à l'article de Wikipedia sur En Abordant résolution de collision, je crois que c'est le mécanisme de l'OpenJdk mise en œuvre utilise. Ce mécanisme est subtilement différent du "seau" approche de l'une des autres réponses mentionne.

Chaque Entrée de l'objet représente paire clé-valeur. Champ suivant se réfère à d'autres de l'Entrée de l'objet si un seau a plus d ' 1 Entrée.

Parfois, il peut arriver que hashCodes pour 2 objets différents sont les mêmes. Dans ce cas, les 2 objets sont enregistrés dans un seau et va être présenté comme LinkedList. Le point d'entrée est plus récemment ajoutés objet. Cet objet fait référence à un autre objet avec le champ suivant et ainsi de on. La dernière entrée se réfère à la valeur null.
Lorsque vous créez HashMap avec le constructeur par défaut

Tableau est est créé avec la taille 16 et défaut de 0,75 équilibrer la charge.

(Source)

Je ne vais pas entrer dans les détails de comment HashMap fonctionne, mais donne un exemple afin que nous puissions rappeler comment HashMap œuvres par rapport à la réalité.

Nous avons Clé, Valeur ,HashCode et d'un seau.

Pendant un certain temps, nous vous concernent chacun d'entre eux avec les éléments suivants:

• Seau -> Une Société
• HashCode -> la Société de l'adresse(toujours unique)
• Valeur -> Une Maison dans la Société
• Touche -> adresse de la Chambre.

À L'Aide De La Carte.get(clé) :

Stevie veut obtenir de son ami(Josse) de la maison qui vit dans une villa située dans un VIP de la société, que ce soit JavaLovers de la Société.
Josse adresse de son SSN(ce qui est différent pour tout le monde).
Il y a un index maintenu dans lequel on trouve le nom de la Société basée sur le SSN.
Cet indice peut être considéré comme un algorithme pour trouver le HashCode.

• SSN Nom de la Société
• 92313(Josse de) -- JavaLovers
• 13214 -- AngularJSLovers
• 98080 -- JavaLovers
• 53808 -- BiologyLovers

1. Cette SSN(clé) de la première nous donne un HashCode(à partir de la table d'index) qui n'est rien mais le nom de la Société.
2. Maintenant, plusieurs maisons peuvent être dans la même société, de sorte que le HashCode peut être commun.
3. Supposons, la Société est commun pour les deux maisons, comment allons-nous à identifier la maison pour laquelle nous allons, oui, en utilisant le (SSN)clé qui n'est rien, mais l'adresse de la Chambre

À L'Aide De La Carte.put(clé,Valeur)

Ce trouve convenable de la société pour cette Valeur par trouver le HashCode et la valeur est stockée.

J'espère que cette aide, et c'est ouvert aux modifications.

Comme il est dit, une image vaut 1000 mots. Je dis: un peu de code est mieux que 1000 mots. Voici le code source de la table de hachage. La méthode Get:

/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && //always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

Ainsi, il devient clair que le hachage est utilisé pour trouver le "seau" et le premier élément est toujours vérifié dans ce seau. Si non, alors equals de la clé est utilisée pour trouver le véritable élément de la liste chaînée.

Voyons le put() méthode:

  /**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) //-1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { //existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

C'est un peu plus compliqué, mais il devient évident que le nouvel élément est mis dans l'onglet à la position calculée en fonction de hachage:

i = (n - 1) & hash ici i est l'index où le nouvel élément sera mis (ou c'est le "compartiment"). n est la taille de la tab array (array de "compartiments").

Tout d'abord, il est tenté d'être mis comme premier élément dans le "seau". Si il y a déjà un élément, puis ajouter un nouveau nœud à la liste.