Explication de l'algorithme du tableau à HashMap

1. Qu'est-ce qu'un tableau ?

J'ai oublié dans quel livre j'ai vu une phrase comme "Toutes les structures de données sont l'évolution de tableaux". Cela a du sens quand on y pense, car la mémoire de l'ordinateur est en fait un espace de stockage linéaire.

Exemple de code Java : int[] array = new int[5]

En ignorant les informations d'en-tête de l'objet et les informations sur la longueur du tableau, la JVM allouera 20 octets d'espace mémoire dans le tas lors de l'exécution, ce qui ressemble à ceci :

​

Une telle structure de données peut facilement accéder aux données via des indices de tableau, mais elle nécessite de parcourir le tableau lors de la recherche, et la complexité temporelle moyenne est de O(n/2).

Lorsque la quantité de données est importante ou que les opérations de recherche sont fréquentes, de telles opérations de parcours sont presque inacceptables. Alors, comment pouvons-nous trouver des données rapidement et en moins de temps ?

2. Recherche binaire

Si les éléments du tableau sont triés, la méthode naturelle consiste à utiliser la recherche binaire.

Par exemple, il existe un tableau d'entiers d'une longueur de 1 000. Les entiers du tableau sont classés du plus petit au plus grand Si je veux savoir si 6 000 se trouve dans ce tableau. Ensuite, je peux d'abord vérifier si le nombre dans le tableau[500] est 6000. Si le nombre dans le tableau[500] est inférieur à 6000, vérifiez le nombre à la position du tableau[750]... et ainsi de suite. jusqu'à 10 fois, le résultat peut être déterminé.

La complexité temporelle de cet algorithme est O(logN).

Cependant, dans la plupart des cas, les éléments du tableau ne sont pas ordonnés et la complexité temporelle O(NlogN) requise pour le tri dépasse généralement de loin le temps requis pour le parcours.

Le problème revient donc à son point initial. Comment retrouver rapidement des données dans des données désordonnées ?

3. Pensée ignorante

Je me souviens encore d'avoir regardé "Programming Pearls" lorsque j'ai appris la programmation. Il y avait une description : dans les années 1970, Mike Lesk a construit une fonction de recherche de numéro de téléphone pour la compagnie de téléphone. Par exemple, entrez la touche numérique 5375*6* correspondante. à LESK*M* Le numéro de téléphone correct ou la liste facultative peuvent être renvoyés avec un taux de fausse correspondance de seulement 0,2 %.

Comment peut-on le faire ?

À cette époque, je ne comprenais pas du tout les structures de données et les algorithmes. C'est toujours très intéressant de restaurer le processus de pensée sauvage de l'époque.

㈠ Ajout

En additionnant tous les nombres (la touche * est 11), la somme de 5375*6* est 48. La somme de la plupart des entrées ne dépasse pas 100, ce qui signifie que des dizaines de milliers de numéros de téléphone seront regroupés dans les 100 premières positions du tableau, ce n'est donc pas réalisable.

㈡Multiplication

Lorsque tous les nombres sont multipliés ensemble, le produit est 381150. Cela semble réalisable, mais il y a un problème : les produits de lesk, lsek, slke... sont les mêmes, et chaque touche numérique correspond également à 3 lettres, ce qui fait que la probabilité de répétition est très élevée.

㈢ Multiplication améliorée

① Les chaînes avec les mêmes lettres mais des ordres alphabétiques différents peuvent ainsi éviter les conflits : chaque nombre est d'abord multiplié par le numéro de série, puis multiplié par d'autres valeurs.

②Chaque touche numérique correspond à 3 lettres anglaises. Si l'utilisateur ne saisit pas le numéro de séquence de la lettre dans la touche numérique, il n'y a aucun moyen de calculer davantage avec précision. La seule direction qui peut être envisagée est de créer des statistiques de probabilité basées sur la liste de mots donnée, elle ne sera donc pas prise en compte.

㈣ Conflit de localisation

Même si une multiplication améliorée est utilisée, les produits calculés par différentes lettres de nom peuvent toujours être répétés. Alors, que faut-il faire en cas de conflit ?

Enregistrer la séquence au prochain emplacement vide ? À bien y penser, ça ne marche pas. Si la prochaine position vide est le produit d’un autre ensemble de lettres, un conflit secondaire se produit.

Heureusement, il existe des nombres premiers.

Les nombres premiers ne peuvent être divisibles que par 1 et lui-même, donc tout produit obtenu par la multiplication ci-dessus ne peut pas être un nombre premier, donc le numéro de téléphone n'est pas stocké dans la position du nombre premier.

Par conséquent, à partir du produit actuel, recherchez le nombre premier suivant à droite. Si la position du nombre premier est toujours utilisée, continuez à rechercher le nombre premier le plus proche suivant...

. À ce stade, le problème semble résolu.

L'utilisateur saisit une chaîne de nombres, le produit est calculé selon la formule et le numéro de téléphone en position d'indice est renvoyé. S'il est incorrect, les nombres premiers suivants sont recherchés séquentiellement jusqu'à ce que l'élément du tableau indice par un certain nombre premier soit vide, et enfin tous les numéros de téléphone trouvés sont renvoyés. Dans la plupart des cas, le numéro de téléphone peut être trouvé en complexité temporelle O(1).

㈤ Le tableau est trop grand

Le seul problème est que le tableau créé selon l’idée ci-dessus est trop grand. Un nom comporte 10 lettres. Si le nombre correspondant à chaque lettre est 9, le produit final obtenu est environ 9 élevé à la puissance 17. Cela signifie construire un tableau de taille 9 ^ 17, ce qui est totalement irréalisable.

㈥Plus tard

Même si le facteur de taille trop grande du tableau n’est pas pris en compte, avec mon niveau de programmation débutant à cette époque, j’étais incapable d’écrire un tel programme.

La raison pour laquelle j'ai restauré ce processus de réflexion est que je pense que le processus de réflexion indépendante est très intéressant et précieux. Pensez-y, en fait, les algorithmes existants ont finalement été développés par ces grands qui cherchaient des solutions étape par étape dans des projets réels.

Par conséquent, lorsque vous rencontrez des problèmes difficiles en ingénierie, tant que vous êtes prêt à réfléchir à la décomposition du problème et à chercher des solutions à chaque petit problème, de nombreux soi-disant problèmes peuvent être résolus.

Plus tard, après avoir lu « Structure des données et analyse des algorithmes. Description du langage Java », j'ai réalisé que mon idée était en fait l'adressage ouvert.

HashMap du JDK utilise un chaînage séparé. Différence : le concept de compartiments est ajouté pour enregistrer les données conflictuelles ; l'opération restante est effectuée pour réduire la taille du tableau.

Parlons donc de HashMap en Java.

4. Explication détaillée de la structure et de l'algorithme HashMap

L'essence de HashMap est toujours un tableau, et c'est un tableau multidimensionnel de longueur variable, similaire à la structure présentée ci-dessous :

㈠ Brève introduction

Le tableau de HashMap stocke le nœud principal de la liste chaînée.

Enregistrer les données :

Calculez le hashCode de la clé, puis effectuez une opération de reste avec la longueur du tableau pour obtenir l'indice du tableau (nœud de tête de liste liée).

Si la position est vide, générez un nouveau nœud de liste chaînée et enregistrez-le dans le tableau.

Si la position n'est pas vide, chaque nœud de la liste chaînée est comparé cycliquement : il existe déjà un nœud avec la même clé, et l'ancien nœud est écrasé s'il n'y a pas de nœud avec la même clé, le nouveau nœud est utilisé comme ; le nœud de queue de la liste chaînée (remarque : voir le code source du JDK1.8, les nouveaux nœuds sont toujours ajoutés à la fin de la liste chaînée, au lieu d'être le nœud principal de la liste chaînée comme JDK1.6).

Données de recherche :

Calculez le hashCode de la clé, puis effectuez une opération de reste avec la longueur du tableau pour obtenir l'indice du tableau (nœud de tête de liste liée). Si la liste chaînée n'est pas vide, comparez d'abord le premier nœud. Si la clé du premier nœud est la même (hashCode est la même et égal à vrai), la valeur du premier nœud est renvoyée directement si la clé du premier nœud est différente. , les autres nœuds de la liste chaînée sont parcourus séquentiellement et comparés, et la valeur avec la même clé est renvoyée La valeur du nœud (null est renvoyé si aucun nœud avec la même clé n'est trouvé).

Le but de HashMap introduisant des listes chaînées est de résoudre le problème de conflit en double évoqué dans la section précédente.

Remarque :

Si le hashcode de toutes les clés est le même, en supposant qu'elles sont toutes 0, alors 0%4 = 0, tous les éléments seront enregistrés dans la liste chaînée 0, et l'enregistrement et la recherche de chaque donnée nécessitent de parcourir la liste chaînée 0. Ensuite, le HashMap à ce moment-là a essentiellement dégénéré en une liste chaînée, et la complexité temporelle a également augmenté du O(1) conçu à O(n/2).

Afin de maintenir autant que possible la complexité temporelle de la recherche et de l'enregistrement HashMap à O(1), les éléments doivent être répartis uniformément dans chaque liste chaînée, c'est-à-dire que chaque liste chaînée n'enregistre qu'un seul élément.

Alors, quels sont les facteurs d’influence ?

Premièrement, le hashcode de la clé ne peut pas être répété s'il est répété, il y aura certainement une liste chaînée pour enregistrer au moins 2 éléments

; La seconde est la conception de la fonction de hachage. S'il ne s'agit que d'un simple reste, alors le reste sera beaucoup répété

 ; Le troisième est la capacité du tableau. Si 100 éléments doivent être répartis dans un tableau d'une longueur de 10, quelle que soit la façon dont vous le calculez, il y aura une liste chaînée pour enregistrer plusieurs éléments. Le meilleur des cas est que chacun soit lié. la liste en enregistre 10 ;

La conception algorithmique de ces trois facteurs est présentée en détail ci-dessous.

㈡ Génération de hashcode

Il s'agit du code de génération hashCode de la classe String.

　　public int hashCode() {
　　　　int h = hash;
　　　　if (h == 0 && value.length > 0) {
　　　　　　char val[] = value;
　　　　　　for (int i = 0; i < value.length; i++) {
　　　　　　　　h = 31 * h + val[i];
　　　　　　}
　　　　　　hash = h;
　　　　}
　　　　return h;
　　}

La valeur de la classe String est char[] et char peut être converti en codage UTF-8. Par exemple, les codages UTF-8 de « a », « b » et « c » sont respectivement 97, 98 et 99 ; « abc » converti en une formule basée sur le code ci-dessus est :

h = 31 * 0 + 97 = 97;

h = 31 * 97 + 98 = 3105 ;

h = 31 * 3105 + 99 = 96354

31 est utilisé comme facteur multiplicateur car il s'agit d'une taille de nombre premier relativement appropriée : si la valeur est trop petite, le produit sera trop petit lorsque le nombre d'éléments impliqués dans le calcul du hashcode est petit s'il s'agit d'un nombre pair ; , cela équivaut à un décalage vers la gauche. Lorsque le dépassement de multiplication entraîne une perte régulière d'informations sur les bits. Ces deux éléments entraîneront une augmentation des taux de redoublement.

Si 32 est utilisé comme facteur multiplicateur (équivalent à << 5), en prenant comme exemple la chaîne "abcabcabcabcabc", les résultats du calcul de chaque étape de son hashcode sont les suivants :

​

Comme le montre la figure ci-dessus, toutes les 3 lettres à la fin de la chaîne généreront un hashcode répété. Ce n'est pas une coïncidence. Même si vous passez à d'autres lettres anglaises, il est facile de répéter, et l'utilisation de nombres premiers réduira considérablement les risques de répétition. Si vous êtes intéressé, vous pouvez vous référer à l'image ci-dessus pour effectuer l'opération de décalage à gauche, et vous constaterez que ce n'est pas accidentel.

　　《Effective Java》一书中详细描述了hashcode的生成规则和注意事项，有兴趣的可以去看看。

　　从源代码的hashCode()方法可知，String类对象保存了已经计算好的hashCode，如果已经调用过hashCode()方法，那么第二次调用时不会再重新生成，而是直接返回已经计算好的hashCode。

　　String对象总是会存放到String类私有维护的常量池中，不显式使用new关键字时，如果常量池中已经有value相同的对象，那么总是会返回已有对象的引用。因此，很多情况下生成hashCode这种比较昂贵的操作实际上并不需要执行。

　　㈢ 哈希函数设计

　　现在，已经得到了重复率很低的hashCode，还有什么美中不足的地方吗？

　　⑴ 扰动函数

　　static final int hash(Object key) {
　　　　　　int h;
　　　　　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
　　}

　　下图还是以字符串“abcabcabcabcabc”为例，使用上面方法得到的运算过程和结果。

　　

　　为什么要先无符号右位移16位，然后再执行异或运算？看看下图的二进制的与运算，你就会明白。

　　

　　你会发现只要二进制数后4位不变，前面的二进制位无论如何变化都会出现相同的结果。为了防止出现这种高位变化而低位不变导致的运算结果相同的情况，因此需要将高位的变化也加入进来，而将整数的二进制位上半部与下半部进行异或操作就可以得到这个效果。

　　为什么要使用与运算？

　　因为哈希函数的计算公式就是hashCode % tableSize，当tableSize是2的n次方(n≥1)的时候，等价于hashCode & (tableSize - 1)。

　　扰动函数优化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0

　　扰动函数优化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6

　　这就是为什么需要增加扰动函数的原因。

　　⑵ 源代码详解

　　代码解释之前需要补充说明一下，jdk1.8引入了红黑树来解决大量冲突时的查找效率，所以当一个链表中的数据大到一定规模的时候，链表会转换成红黑树。因此在jdk1.8中，HashMap的查找和保存数据的最大时间复杂度实际上就是红黑树的时间复杂度O(logN)。

　　以下是HashMap中的保存数据的方法源代码，相信经过以上的描述，已经非常容易看懂这一段代码。

　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
　　　　Node<K,V>[] tab;　　　　//HashMap数组
　　　　Node<K,V> p;　　　　　　//初始化需要保存的数据
　　　　int n;　　　　　　　　　//数组容量
　　　　int i;　　　　　　　　　//数组下标

　　　　/* 如果数组为空或0，初始化容量为16 */
　　　　if ((tab = table) == null || (n = tab.length) == 0){
　　　　　　n = (tab = resize()).length;
　　　　}

　　　　/* 使用哈希函数获取数组位置(如果为空，保存新节点到数组) */
　　　　if ((p = tab[i = (n - 1) & hash]) == null){
　　　　　　tab[i] = newNode(hash, key, value, null);
　　　　}

　　　　/* 如果数组位置已经有值，则使用下列方式保存数据 */
　　　　else {
　　　　　　Node<K,V> e;　　　　//临时节点保存新值
　　　　　　K k;　　　　　　　　//临时变量用于比较key

　　　　　　//如果头节点与新节点的key的hash值相同 且 key的值相等，e赋值为旧节点
　　　　　　if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
　　　　　　　　e = p;
　　　　　　}

　　　　　　//如果头节点是一个红黑树节点，那么e将保存为树节点
　　　　　　else if (p instanceof TreeNode){
　　　　　　	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
　　　　　　}

　　　　　　//如果头节点与新节点不同，且头节点不是红黑树节点，循环比对链表的所有节点
　　　　　　else {
　　　　　　　　for (int binCount = 0; ; ++binCount) {
　　　　　　　　　　if ((e = p.next) == null) {
　　　　　　　　　　　　//如果直到链表尾未找到相同key的节点，将新结点作为最后一个节点加入到链表
　　　　　　　　　　　　p.next = newNode(hash, key, value, null);

　　　　　　　　　　　　//如果链表节点数大于等于8-1，转换成红黑树；转换成红黑树的最小节点数是8
　　　　　　　　　　　　if (binCount >= TREEIFY_THRESHOLD - 1){
　　　　　　　　　　　　　　treeifyBin(tab, hash);
　　　　　　　　　　　　}
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　//如果循环过程中发现新旧key的值相同，跳转：是否覆盖旧值
　　　　　　　　　　if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
　　　　　　　　　　　　break;
　　　　　　　　　　}
　　　　　　　　　　p = e;
　　　　　　　　}
　　　　　　}

　　　　　　//是否覆盖旧值
　　　　　　if (e != null) {
　　　　　　　　V oldValue = e.value;
　　　　　　　　//如果新值不为空且（允许修改旧值 或 旧值为空），覆盖旧节点的值
　　　　　　　　if (!onlyIfAbsent || oldValue == null){
　　　　　　　　　　e.value = value; 	
　　　　　　　　}
　　　　　　　　afterNodeAccess(e);　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　　　　　return oldValue;　　　　//返回旧值
　　　　　　}
　　　　}

　　　　//用于比较判断是否在遍历集合过程中有其它线程修改集合，详情请网上搜索fail-fast快速失败机制
　　　　++modCount;

　　　　//当key数量大于允许容量时进行扩容。允许容量在HashMap中是数组长度 * 装填因子(默认0.75)
　　　　if (++size > threshold){
　　　　	resize();
　　　　}

　　　　//回调函数，这里是空函数，但在linkedHashMap中实现了此方法
　　　　afterNodeInsertion(evict);
　　　　return null;
　　}

　　⑶ 简化后的伪代码

　　putval(key, value){
　　　　index = key.hashcode % tablesize;
　　　　if(null == table[index]){
　　　　　　table[index] = new node(key, value);
　　　　}else{
　　　　　　firstNode = table[index];
　　　　　　nextNode = firstNode.next;
　　　　　　while(nextNode.hasNextNode()){
　　　　　　　　//如果找到相同key的旧节点，覆盖旧节点
　　　　　　　　if(key == nextNode.key){
　　　　　　　　　　nextNode = new node(key, value);　　
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　//如果到队列末尾依然没有找到相同key的旧节点，将新结点加入到最后一个节点的末尾
　　　　　　　　if(nextNode.next == null){
　　　　　　　　　　nextNode.next = new node(key, value);
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　nextNode = nextNode.next;
　　　　　　}
　　　　}
　　}

　　⑷ 数组大小设计

　　代码注释中已经稍有提及，这里再分别展开讨论。

　　①数组容量选择

　　HashMap的初始容量是 1 << 4，也就是16。以后每次扩容都是size << 1，也就是扩容成原来容量的2倍。如此设计是因为 2^n-1(n≥1)的二进制表示总是为重复的1，方便进行求余运算。

　　《数据结构与算法分析.Java语言描述》一书中的建议是容量最好是质数，有助于降低冲突，但没有给出证明或实验数据。

　　质数虽然是神奇的数字，但个人感觉在这里并没有特别的用处。

　　根据公式index = hashCode % size可知，无论size是质数还是非质数，index的值区间都是0至(size-1)之间，似乎真正起决定作用的是hashCode的随机性要好。

　　这里先不下结论，待以后再写一个随机函数比较下质数和非质数重复率。

　　②装填因子

　　装填因子默认是0.75，也就是说如果数组容量为16，那么当key的数量大于12时，HashMap会进行扩容。

　　装填因子设计成0.75的目的是为了平衡时间和空间性能。过小会导致数组太过于稀疏，空间利用率不高；过大会导致冲突增大，时间复杂度会上升。

　　㈣ 关于其它

　　红黑树是在JDK 1.8中引入的，想用简单的语言来讲清楚红黑树的数据结构、增删改查操作及时间复杂度分析，这是一个复杂且艰难的任务，更适合单独来描述，因此留待以后吧。

　五　最小完美哈希函数(Minimal Perfect Hash Function, MPHF)

　　Jdk中的HashMap解决了任意数据集的时间复杂度问题，所设计的哈希函数在未知数据集的情况下有良好的表现。

　　但如果有一个已知数据集(如Java关键字集合)，如何设计一个哈希函数才能同时满足以下两方面的要求：

　　⑴ 容器容量与数据集合的大小完全一致；

⑵ Il n'y a pas de conflit.

En d’autres termes, lorsqu’un certain ensemble de données est donné, si une fonction de hachage permet à chaque nœud du conteneur d’avoir un et un seul élément de données, une telle fonction de hachage est appelée fonction de hachage parfaite minimale.

Récemment, j'étudiais les principes de la compilation et j'ai mentionné comment résoudre le problème de recherche de complexité temporelle O(1) des ensembles de mots-clés, et j'ai mentionné que la fonction de hachage parfait minimum pouvait être utilisée. Quand je vois un terme comme celui-ci, je me sens immédiatement très bien et noble.

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!