Explication détaillée et exemples simples de stockage de hachage Java

Java Hash Storage

Les structures de données du stockage de hachage en Java font principalement référence à HashSet, HashMap, LinkedHashSet, LinkedHashMap et HashTable, etc. Pour comprendre le mécanisme de stockage de hachage en Java, nous devons d'abord comprendre deux méthodes : equals() et hashCode(). Concernant la méthode equals() et sa différence avec l'opérateur relationnel "==", nous l'avons expliqué dans un autre article. Quant à hashCode(), c'est une méthode définie dans la classe Object :

public native int hashCode();

Il s'agit d'une méthode locale qui renvoie une valeur int et n'est pas implémentée dans la classe Object. Cette méthode est principalement utilisée dans les structures de données qui utilisent le hachage et fonctionne normalement avec des collections basées sur le hachage. Par exemple, lors de l'insertion d'un objet dans un conteneur (nous supposons qu'il s'agit d'un HashMap), comment déterminer si l'objet existe déjà dans le conteneur. conteneur ? Où est la cible ? Puisqu’il peut y avoir des milliers d’éléments dans le conteneur, utiliser la méthode equals() pour les comparer séquentiellement est très inefficace. La valeur du hachage est la vitesse, il enregistre la clé quelque part afin qu'elle puisse être trouvée rapidement. La structure de données la plus rapide pour stocker un ensemble d'éléments est un tableau, utilisez-le donc pour stocker des informations clés (notez qu'il s'agit des informations clés, pas de la clé elle-même). Mais comme le tableau ne peut pas ajuster sa capacité, il y a un problème : on veut sauvegarder un nombre incertain de valeurs dans la Map, mais que faire si le nombre de clés est limité par la capacité du tableau ?

La réponse est : le tableau ne sauvegarde pas la clé lui-même, mais génère un numéro via l'objet clé et l'utilise comme indice du tableau. Ce numéro est le code de hachage (hashcode), qui est défini dans Object et peut être généré par la méthode hashCode() remplacée par votre classe. Pour résoudre le problème de la capacité fixe du tableau, différentes clés peuvent produire le même indice, un phénomène appelé conflit. Par conséquent, le processus d'interrogation d'une valeur dans le conteneur est le suivant : calculez d'abord le code de hachage de l'objet à insérer via hashCode(), puis utilisez le code de hachage pour interroger le tableau. Les conflits sont souvent gérés via des liens externes, c'est-à-dire que le tableau ne stocke pas directement la valeur, mais une liste de valeurs, puis une requête linéaire est effectuée sur les valeurs de la liste. Cette partie de la requête sera naturellement effectuée. Ralentissez. Cependant, si la fonction de hachage est suffisamment bonne, il y aura moins de valeurs à chaque position du tableau. Par conséquent, le mécanisme de hachage peut accéder rapidement à un emplacement du tableau, en comparant seulement quelques éléments. C'est pourquoi HashMap est si rapide. Nous pouvons en faire l'expérience grâce à la méthode HashMap.put() :

public V put(K key, V value) {
  if (table == EMPTY_TABLE) {
   inflateTable(threshold);
  }
  if (key == null)
   return putForNullKey(value);
  int hash = hash(key);
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
   Object k;
   if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
   }
  }
 
  modCount++;
  addEntry(hash, key, value, i);
  return null;
 }

L'idée principale est : dans la clé. Lorsqu'il n'est pas vide, le hachage du code de hachage est obtenu en fonction de l'objet clé, puis l'indice i du tableau est obtenu via le code de hachage. Parcourez la liste représentée par table[i] et déterminez si la clé existe via equals(). Si elle existe, mettez à jour l'ancienne valeur avec la nouvelle valeur et renvoyez l'ancienne valeur, sinon, ajoutez la nouvelle paire clé-valeur à HashMap. . On peut voir ici que la méthode hashCode existe pour réduire le nombre d'appels à la méthode égale, améliorant ainsi l'efficacité du programme.

Ici, nous devons noter : hashCode() n'a pas toujours besoin de pouvoir renvoyer un code d'identification unique, mais la méthode equals() doit déterminer strictement si deux objets sont identiques.

Merci d'avoir lu, j'espère que cela pourra vous aider, merci pour votre soutien à ce site !

Pour des explications plus détaillées et des exemples simples de stockage de hachage Java, veuillez faire attention au site Web PHP chinois !