Table de hachage, conflit de hachage

Bonjour tout le monde,On se revoit,Je suis ton ami, le chef de l'armée..

Table de hachage 1.Une table de hachage est une sorte de clékeyStockage des donnéesvalueStructure de,ParkeyStocké comme valeur d'identitévalueValeur;Il suffit d'entrerkey,Vous pouvez obtenir levalueValeur.Lorsque vous Interrogez un élément par valeur clé,Utiliser le mêmehashLa fonction vakeyConvertir en indice de tableau,Obtenir des données à partir d'un tableau en fonction de l'emplacement de l'indice.C'est en fait une extension du tableau,Tableau+Liste des liens+Arbre Rouge et noir. 2.Conception de la table de hachage La conception de la fonction de hachage ne doit pas être trop compliquée.,Les fonctions de hachage complexes ont un impact indirecthashPerformance du tableau;Deuxièmement, les valeurs de hachage doivent être réparties aussi aléatoirement et uniformément que possible.,Éviter ou réduire le nombre de conflits de hachage,Moyenne des données stockées dans chaque seau.

Les méthodes de conception conventionnelles comprennent l'analyse des données.,Sélectionner les caractéristiques commerciales des données pour extraire certaines données pour le calcul,Ensuite, nous obtenons le résultat qui est le plus haché après avoir additionné la longueur du tableau de hachage.Il y a aussi l'Adressage direct、Méthode de la moyenne au carré、Méthode de pliage et méthode des nombres aléatoires, etc..

Facteur de charge（Facteur de charge）：Réduire la longueur de la Liste Expansion inefficace：Multiplié par2Pour agrandir Plus le facteur de charge est grand,Plus d'éléments sont stockés dans la table de hachage,Moins il y a de place libre,Plus la probabilité de conflit de hachage est élevée,Insérer、Les performances diminuent lorsque les données sont supprimées et trouvées. L'expansion inefficace doit être évitée.,Parce que dans de rares cas, la vitesse d'insertion est très lente,Provoque un crash de l'utilisateur. Fonction de hachage 1.La valeur de hachage calculée par la fonction de hachage doit être un entier non négatif 2.Sikey1==key2,Alorshash(key1)==hash(key2) 3.Même les deuxkeyDehashValeur égale,Mais c'est possiblekeyValeurs inégales 4.Scénario d'application：Cryptage sécurisé、Identification unique、Vérification des données、Équilibrage de la charge、 Fragmentation des données et stockage réparti, etc. Hash conflict En raison de la limitation de la portée de la cartographie ,key La probabilité de valeur est supérieure à la plage de cartographie , Il y a deux choses différentes key Mapping to the same location

Les méthodes courantes pour résoudre les conflits de hachage sont Open address et Link List . Méthode des adresses ouvertes：Une fois là - Bas,hash Les conflits de valeurs sont résolus en redéployant de nouveaux emplacements . Pour la méthode de détection linéaire lorsque plus d'éléments sont stockés dans la table de hachage , Plus la probabilité de conflit de hachage est élevée , Dans des cas extrêmes, il faut sonder toute la table de hachage ,La complexité temporelle estO(n). Méthode de la liste de liens：Méthode de l'adresse de la chaîne, Plus utilisé dans des applications spécifiques , Chaque seau correspond à une liste liée dans la table de hachage , Conserver les éléments ayant la même valeur de hachage dans la liste des liens correspondants à la même position de baril , Parce qu'il faut comparer key Valeur donc la complexité du temps d'insertion est O(k), La complexité temporelle de la recherche et de la suppression est proportionnelle à la longueur de la liste liée O(k),En généralk Quand la valeur n'est pas grande, on peut penser que O(1). La longueur de la liste doit être réduite au minimum , Un paramètre peut être introduit ： Facteur de charge ou facteur de charge . Le facteur de charge est utilisé pour limiter indirectement la longueur de la liste , Plus la valeur est élevée, plus la longueur admissible de la liste est grande , Plus la table de hachage est mauvaise , Mais plus le facteur de charge est petit, plus l'espace est gaspillé .

HashMap La méthode de la liste de liens est adoptée pour résoudre le problème. hashConflit,ThreadLocalMap Résolution des conflits par une méthode d'adressage ouverte basée sur la détection linéaire .

Les données de la méthode d'adressage ouvert sont stockées dans un tableau , Peut être utilisé efficacement CPU Cache pour accélérer les requêtes , Il n'y aura pas de problèmes avec les listes de liens et les pointeurs . Lorsque le facteur de charge est grand, il provoque un grand nombre d'actions de détection ,Les performances vont chuter, C'est très gênant de supprimer les données. , Et il faut plus d'espace de stockage que la méthode de la liste liée .La quantité de données est relativement faible、 Convient à la méthode d'adresse ouverte lorsque le facteur de charge est faible . Les données de la méthode de la liste liée sont stockées dans la liste liée , L'utilisation de la mémoire est un peu plus élevée que la méthode d'adresse de développement , Un facteur de charge plus élevé peut être toléré , Parce que le stockage est nécessaire dans le noeud nextPointeur, Consomme de l'espace mémoire supplémentaire 【 Problèmes de charge utile 】. En fait, si l'on considère la longueur de la liste , On pourrait envisager d'introduire des arbres rouges et noirs. , Pour éviter les attaques malveillantes de collision de hachage qui stockent des données dans un seau .

Éditeur：Programmeur de pile complète,Veuillez indiquer la source de la réimpression.：https://javaforall.cn/151682.htmlLien vers le texte original：https://javaforall.cn