Introduction détaillée à la façon dont JavaScript implémente les tables de hachage

Cet article vous apporte des connaissances pertinentes sur javascript Il présente principalement les problèmes liés à la façon dont JavaScript implémente les tables de hachage. La structure entière du tableau dans lequel les données finales sont insérées est encapsulée, et le résultat est la table de hachage. j'espère que cela aide tout le monde.

Recommandations associées : Tutoriel d'apprentissage Javascript

Les tables de hachage sont généralement implémentées sur la base de tableaux, mais par rapport aux tableaux, elles présentent de nombreux avantages :

1. Elles peuvent fournir une insertion très rapide - Recherche par suppression opérations
2. Peu importe la quantité de données, l'insertion et la suppression nécessitent un temps proche d'un temps constant : c'est-à-dire un niveau de temps O(1). En fait, quelques instructions machine suffisent pour le faire.
3. Les tables de hachage sont plus rapides que les arbres, et vous pouvez trouver instantanément les éléments souhaités
4. Les tables de hachage sont beaucoup plus faciles à coder que les arbres

Quelques défauts des tables de hachage par rapport aux tableaux :

1. Les données dans la table de hachage n'est pas en ordre, donc les éléments ne peuvent pas être parcourus de manière fixe
2. Normalement, les clés de la table de hachage ne peuvent pas être répétées, et les mêmes clés ne peuvent pas être placées comme clé, utilisée pour enregistrer différents éléments
3. L'utilisation de l'espace n'est pas élevée, la couche inférieure utilise des tableaux et certaines cellules ne sont pas utilisées

Qu'est-ce qu'une table de hachage ?

• Les tables de hachage ne sont pas faciles à comprendre, contrairement aux tableaux, listes chaînées et arbres, qui peuvent exprimer leur structure et leurs principes sous forme de graphiques.
• La structure de la table de hachage est array, mais sa magie réside dans une transformation de la valeur d'indice. Cette transformation peut être appelée fonction de hachage, qui peut être obtenue via la fonction de hachage HashCode.

Quelques concepts de tables de hachage

• Hashification : Le processus de conversion de grands nombres en indices dans la plage du tableau est appelé hachage
• ha Fonction de hachage : Nous convertissons habituellement mots en grands nombres, et mettez l'implémentation du code du hachagegrands nombres dans une fonction, appelée fonction de hachage
• Table de hachage : Encapsulez l'intégralité de la structure dans le tableau ; dans lequel les données finales sont insérées, et le résultat est une table de hachage.

Problèmes qui doivent encore être résolus :

L'indice haché est toujours possible
• dupliquer Comment résoudre ce problème ? Cette situation s'appelle conflit, le conflit est inévitable, nous ne pouvons que résoudre le conflit.

Méthodes pour résoudre les conflits

Deux solutions courantes pour résoudre les conflits :

Option 1 :
• Méthode d'adresse en chaîne (Méthode Zip) ; L'opération de reste est effectuée sur 10
et la plage du reste

0~9

est utilisée comme valeur d'indice du tableau. De plus, la position correspondant à chaque valeur d'indice dans le tableau ne stocke plus un nombre, mais stocke un tableau ou liste chaînée composé de nombres qui ont le même reste après une opération de reste.

Résumé : La façon de résoudre les conflits avec la méthode d'adresse de chaîne est que

chaque unité de tableau

ne stocke plus une seule donnée, mais une chaîne. La structure de données couramment utilisée pour cette chaîne est. Tableau ou liste chaînée, les deux structures de données sont tout aussi efficaces en recherche (car la chaîne ne comporte généralement pas trop d'éléments). Option 2 : Méthode d'adresse ouverte

 ;

• La méthode de travail principale de la méthode d'adresse ouverte consiste à trouver des cellules vides
pour placer des

éléments de données

en conflit.

Selon les différentes façons de détecter la position des cellules vierges, il peut être divisé en trois méthodes:

Détection linéaire

• détection secondaire voir À mesure que le facteur de remplissage augmente, la longueur de détection moyenne augmente de manière linéaire et douce. La méthode d'adresse en chaîne est souvent utilisée en développement. Par exemple, la méthode d'adresse en chaîne
est utilisée dans HashMap en Java.
• Excellente fonction de hachage
L'avantage d'une table de hachage est sa vitesse, de sorte que la fonction de hachage ne peut pas utiliser d'algorithmes complexes qui consomment des performances élevées. Une façon d'améliorer la vitesse consiste à minimiser les
• multiplications et divisions dans la fonction de hachage.
Une fonction de hachage performante devrait présenter les deux avantages suivants :

• Calcul rapide ;
• Distribution uniforme ;

Calcul rapide

Loi de Horner : La loi de Horner est également appelée algorithme de Qin Jiu en Chine.

Quand pour trouver la valeur d'un polynôme, calculez d'abord la valeur du polynôme linéaire dans la parenthèse la plus intérieure, puis calculez la valeur du polynôme linéaire couche par couche de l'intérieur vers l'extérieur. Cet algorithme convertit la valeur du polynôme à n degrés f(x) en valeur de polynômes à n degrés.

Avant transformation

:

Nombre de multiplications : n (n+1)/2 fois ;

• Nombre d'ajouts : n fois ;
• Nombre d'ajouts : n fois ;

Si le grand O est utilisé pour représenter la complexité temporelle, il est directement réduit de O(N2) avant transformation en

O(N)

.
• Distribution uniforme
• Afin de garantir que les données sont

également réparties

dans la table de hachage, lorsque nous devons utiliser des constantes, essayez d'utiliser des nombres premiers par exemple : la longueur de la table de hachage, la base de la Nième puissance, etc.

HashMap en Java utilise la méthode d'adresse en chaîne et la méthode de hachage utilise la formule :

index = HashCode (clé) & (Longueur-1)

C'est-à-dire que les données sont converties en binaire pour les opérations et , et ce n'est pas une opération de reste. De cette manière, l’ordinateur opère directement sur des données binaires, ce qui est plus efficace. Cependant, JavaScript aura des problèmes lors de l'exécution des opérations et appelées big data, donc l'opération restante sera toujours utilisée lors de l'utilisation de JavaScript pour implémenter le hachage.

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i  this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i  7 && this.count  0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i <p><strong></strong></p>Recommandations associées : <p>Tutoriel d'apprentissage Javascript<strong></strong><strong></strong></p>

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!