Introduction détaillée aux tables de hachage en Java

Qu'est-ce qu'une table de hachage

Une table de hachage, également appelée table de hachage, est une donnée A ? structure qui fournit une relation de mappage entre les clés et les valeurs. Tant qu'une clé est donnée, la valeur correspondante peut être trouvée efficacement et la complexité temporelle est proche de O(1).

Vidéos d'apprentissage en ligne recommandées : Vidéo Java

Comment fonctionnent les tables de hachage

Une table de hachage est essentiellement un tableau. Nous savons que les tableaux sont accessibles de manière aléatoire en fonction d'indices, tels que a[0], a[1], a[2], a[3], a[4]. De cette façon, l'efficacité des requêtes est très élevée. Dans une table de hachage, lorsque l'on donne une clé, la valeur correspondante peut être interrogée immédiatement. À l'heure actuelle, nous avons besoin d'une "station de transfert" pour convertir la clé et l'indice du tableau d'une manière ou d'une autre, et cette station de transfert est la fonction de hachage.

Les fonctions de hachage sont implémentées de différentes manières dans différentes langues. Celui utilisé en Java est HashMap.

En Java et dans la plupart des langages orientés objet, chaque objet a son propre hashcode pour distinguer différents objets, et ce hashcode est une variable entière. À ce stade, nous devons convertir cette variable entière en indice du tableau. La méthode de conversion la plus simple consiste à prendre le modulo de la longueur du tableau.

La formule est la suivante :

index = HashCode(key) % Array.length

Par exemple :

Étant donné un tableau d'une longueur de 8, on souhaite trouver la Vaule correspondant à la clé "001121" , et " Le hashcode de 001121 " est 1420036703, alors l'indice du tableau peut être obtenu grâce au calcul suivant :

index = HashCode("001121")%Array.length = 1420036703 % 8 = 7

Opérations de lecture et d'écriture de la table de hachage

1. L'opération d'écriture

L'opération d'écriture consiste à insérer une nouvelle paire clé-valeur dans la table de hachage (appelée Entry dans jdk).

La méthode spécifique est la suivante : convertir la valeur clé en indice de tableau via une fonction de hachage, puis insérer l'entrée à cette position dans le tableau (notez qu'il s'agit de la paire clé-valeur d'entrée Clé+Valeur, pas seulement la valeur). Il est concevable que différentes valeurs de clé puissent être converties en le même indice, et cela devient alors un conflit de hachage.

Les méthodes couramment utilisées pour résoudre les conflits de hachage sont la méthode d'adressage ouvert et la méthode de liste chaînée.

L'idée de base de la méthode d'adressage ouverte est la suivante : lorsqu'un conflit de hachage se produit, l'entrée est placée dans la position vide suivante dans le tableau, c'est-à-dire reculée une par une.

L'idée de base de la méthode de liste chaînée (appliquée dans la classe de collection HashMap de Java) est que chaque élément du tableau n'est pas seulement un objet Entry, mais également le nœud principal d'une liste chaînée. Chaque objet Entry pointe vers son prochain nœud Entry via le pointeur suivant. Lorsqu'un nouvel objet Entry est mappé à une position de tableau conflictuelle, il suffit de l'insérer dans la liste chaînée correspondante.

2. Opérations de lecture

Les opérations de lecture correspondent aux opérations d'écriture, et ne doivent traiter que des situations conflictuelles.

L'idée spécifique est la suivante : utilisez la fonction de hachage pour convertir la valeur de clé à trouver en indice de tableau, puis vérifiez si la valeur de clé à cette position dans le tableau est la clé que nous recherchons si. alors, trouvez-le. La valeur Value de l'entrée peut être renvoyée ; sinon, continuez à chercher dans la liste chaînée pour voir s'il existe une valeur Key correspondante.

Par exemple, lorsque nous voulons trouver la valeur correspondant à la clé 002936, nous convertissons d'abord la clé en indice de tableau et obtenons l'indice 2. Nous vérifions l'élément et constatons que la clé de l'élément est 002947 , ce qui n'est pas ce que nous voulons. Si vous interrogez la clé, continuez à rechercher dans la liste chaînée.

3. Expansion

Nous savons que l'expansion du tableau est nécessaire lorsque le nombre d'éléments dans le tableau atteint la longueur maximale de le tableau Lors de l'expansion du tableau, quand la table de hachage sera-t-elle développée ?

Lorsque la table de hachage atteint un certain degré de saturation après l'insertion de plusieurs éléments, la probabilité d'un conflit de hachage augmente. À ce moment-là, un grand nombre d'éléments sont encombrés à la même position d'indice du tableau. de post-commande Cela a un grand impact sur les performances des opérations d'insertion et de requête. À ce stade, il est nécessaire d'étendre la table de hachage.

Les facteurs qui affectent l'expansion de la table de hachage sont :

Capacity，即HashMap的当前长度

LoadFactor，即HashMap的负载因子，默认值为0.75

扩容需要满足的条件：

HashMap.Size >= Capacity X LoadFactor

简单解释为：当哈希表中的条目数超出了当前容量与其加载因子的乘积时，并且要存放的位置已经有元素了（哈希碰撞），这两个条件满足时，需要进项扩容，会将容量扩大为原来的两倍。加载因子默认值0.75，是在空间和时间上的一个折中，加载因子过高（发生冲突可多存放在链表），虽然减少了空间成本，但也增加了查询成本。

扩容的步骤：

扩容不是简单地把散列表的长度扩大，而是经历了下面两个步骤：

1.扩容，创建一个新的Entry空数组，长度时原数组的2倍；

2.重新Hash，遍历原Entry数组，所有的Entry重新Hash到新数组中。

经过扩容，原本拥挤的散列表重新变得稀疏，原有的Entry也重新得到了尽可能均匀的分配。需要注意的是，关于HashMap的实现，JDK8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时，为了提高插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。

相关文章教程推荐：java语言入门

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!