Comment Java implémente-t-il les tables de hachage?

Est-ce que quelqu’un sait comment Java implémente ses tables de hachage (HashSet ou HashMap)? Compte tenu des différents types d’objects que l’on peut vouloir placer dans une table de hachage, il semble très difficile de trouver une fonction de hachage qui fonctionnerait bien dans tous les cas.

HashMap et HashSet sont très similaires. En fait, le second contient une instance du premier.

Un HashMap contient un tableau de compartiments afin de contenir ses entrées. La taille du tableau est toujours de 2. Si vous ne spécifiez pas une autre valeur, il y a au départ 16 compartiments.

Lorsque vous y insérez une entrée (clé et valeur), elle détermine le compartiment dans lequel l’entrée sera insérée en la calculant à partir du code de hachage de sa clé (le hashcode n’est pas son adresse mémoire et le hachage n’est pas un module ). Différentes entrées peuvent entrer en collision dans le même compartiment, elles seront donc placées dans une liste.

Les entrées seront insérées jusqu’à ce qu’elles atteignent le facteur de charge. Ce facteur est de 0,75 par défaut et il n’est pas recommandé de le modifier si vous n’êtes pas certain de ce que vous faites. 0,75 comme facteur de charge signifie qu’un HashMap de 16 compartiments ne peut contenir que 12 entrées ( 16 * 0,75 ). Ensuite, un tableau de compartiments sera créé, doublant la taille de la précédente. Toutes les entrées seront à nouveau placées dans le nouveau tableau. Ce processus est connu sous le nom de rehashing , et peut être coûteux.

Par conséquent, une bonne pratique, si vous connaissez le nombre d’entrées à insérer, consiste à créer un HashMap en spécifiant sa taille finale:

new HashMap(finalSize); 

Vous pouvez vérifier la source de HashMap , par exemple.

Java dépend de l’implémentation de la méthode hashCode () par chaque classe pour répartir les objects de manière uniforme. De toute évidence, une mauvaise méthode hashCode () entraînera des problèmes de performances pour les grandes tables de hachage. Si une classe ne fournit pas de méthode hashCode (), la valeur par défaut dans l’implémentation actuelle est de renvoyer une fonction (c’est-à-dire un hachage) de l’adresse de l’object en mémoire. Citant de la doc API:

Dans la mesure du possible, la méthode hashCode définie par la classe Object renvoie des entiers distincts pour des objects distincts. (Ceci est généralement implémenté en convertissant l’adresse interne de l’object en un entier, mais cette technique d’implémentation n’est pas requirejse par le langage de programmation JavaTM.)

Il existe deux méthodes générales pour implémenter un HashMap. La différence est la façon dont on traite les collisions.

La première méthode, celle des utilisateurs de Java, fait en sorte que chaque compartiment du HashMap contienne une liste liée individuellement. Pour ce faire, chaque compartiment contient un type d’ entrée , qui met en cache le code de hachage, comporte un pointeur sur la clé, un pointeur sur la valeur et un pointeur sur l’entrée suivante. Lorsqu’une collision se produit en Java, une autre entrée est ajoutée à la liste.

L’autre méthode pour gérer les collisions consiste simplement à placer l’élément dans le prochain compartiment vide. L’avantage de cette méthode est qu’elle nécessite moins d’espace, mais elle complique les suppressions, car si le compartiment suivant l’élément supprimé n’est pas vide, il faut vérifier si cet élément se trouve dans le bon ou le mauvais compartiment et le déplacer. s’il est entré en collision avec l’élément en cours de suppression.

Avec mes propres mots:

Un object d’ Entry est créé pour contenir la référence de la clé et de la valeur.

Le HashMap a un tableau de Entry .

L’index pour l’entrée donnée est le hash renvoyé par key.hashCode()

En cas de collision (le même index a été atsortingbué à deux clés), l’entrée est stockée dans l’atsortingbut .next de l’entrée existante.

C’est ainsi que deux objects avec le même hachage peuvent être stockés dans la collection.

De cette réponse, nous obtenons:

  public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } 

Dites-moi si j’ai un problème.