Comment résoudre le problème de conflit de hachage avec HashMap en Java

1. Algorithme de hachage et table de hachage

Pour comprendre les conflits de hachage, comprenez d'abord l'algorithme de hachage et la table de hachage

• L'algorithme de hachage consiste à convertir une entrée de n'importe quelle longueur en une sortie de longueur fixe via un algorithme de hachage. . Ce résultat de sortie est Une valeur de hachage

• La table de hachage est également appelée « table de hachage ». Il s'agit d'une structure de données qui accède directement à l'emplacement de stockage en mémoire via la clé. mappez la clé à un certain emplacement dans la table pour obtenir les données à cet emplacement, accélérant ainsi la recherche de données

2 Conflit de hachage

Le conflit de hachage est dû à l'algorithme de hachage, les données calculées sont illimitées. , et la plage du résultat calculé est limitée Oui, il y aura toujours des données différentes et les valeurs obtenues après le calcul sont les mêmes, alors dans ce cas, il y aura ce qu'on appelle un conflit de hachage

3. quatre façons de résoudre les conflits de hachage

La méthode d'adressage ouverte est également appelée détection linéaire. La méthode consiste à partir de l'emplacement où le conflit se produit, à trouver un emplacement libre dans la table de hachage dans un certain ordre, puis à y stocker les éléments en conflit. location. En Java, ThreadLocal utilise la méthode de détection linéaire pour résoudre les conflits de hachage

Comme le montre la figure, key=name est stocké à l'index 1 de la table de hachage lors de l'ajout de key=hobby, en supposant que le. L'index calculé est également 1, alors un conflit de hachage se produit à ce moment-là et l'adressage ouvert est ouvert. La méthode consiste à trouver un emplacement libre afin de stocker la clé en conflit

Méthode d'adressage en chaîne. C'est une méthode simple. La compréhension est d'utiliser une liste chaînée unidirectionnelle pour stocker la clé avec un conflit de hachage, telle que HashMap

Comme le montre la figure, les clés en conflit sont directement stockées sous la forme d'une liste chaînée unidirectionnelle.

Ensuite, la méthode de hachage consiste à calculer la clé via une certaine fonction de hachage. En cas de conflit, utilisez-en une autre. La fonction de hachage peut la hacher et continuer à la calculer jusqu'à ce qu'il n'y ait plus de conflits. avoir un certain impact sur les performances

L'établissement d'une zone de suppression publique consiste à diviser la table de hachage en deux parties de base : la table et la table des avantages. Tous les éléments en conflit seront placés dans la table des avantages

4. Version JDK1.8

HashMap dans la version JDK1.8 utilise la méthode d'adressage en chaîne et le rouge L'arbre noir est utilisé pour résoudre le problème du conflit de hachage. L'arbre rouge-noir est utilisé pour optimiser le problème de la complexité temporelle accrue causée par la longueur. liste chaînée de la table de hachage Lorsque la longueur de la liste chaînée est supérieure ou égale à 8 et que la capacité de la table de hachage est supérieure à 64, alors ajoutez à l'élément de la liste chaînée, cela déclenchera une transformation du lié. liste dans un arbre rouge-noir

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!