Introduction détaillée aux tables de hachage (tables de hachage) en JavaScript (exemples de code)

Le contenu de cet article est une introduction détaillée (exemple de code) sur les tables de hachage (tables de hachage) en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. .

Table de hachage

La table de hachage (également appelée table de hachage) accède directement à l'emplacement de stockage mémoire en fonction de la structure de données clé (Clé). Autrement dit, il accède à l'enregistrement en calculant une fonction sur la valeur clé qui mappe les données de requête requises à un emplacement dans la table, ce qui accélère la recherche. Cette fonction de mappage est appelée fonction de hachage et le tableau stockant les enregistrements est appelé table de hachage.

On part de l'image ci-dessus pour analyser

• Il existe un ensemble U, qui est 1000, 10, 152, 9733, 1555, 997, 1168

• Le côté droit est une liste (table de hachage) de 10 emplacements Nous devons stocker les entiers de l'ensemble U dans cette liste

• Comment le stocker et dans quel emplacement ? Ce problème doit être résolu via une fonction de hachage. Ma méthode de stockage est de prendre le reste de 10. Regardons cette image

• 1000%10=0, 10%10=0, puis les deux entiers 1000 et 10 Il sera stocké dans l'emplacement numéroté 0

• 152%10=2 puis il sera stocké dans l'emplacement 2

• 9733 %10 =3 est stocké dans l'emplacement numéroté 3

Grâce à l'exemple simple ci-dessus, vous devriez avoir une compréhension générale des points suivants

• L'ensemble U est la clé qui peut apparaître dans la table de hachage

• La fonction de hachage est une méthode de votre propre conception pour combiner l'ensemble Les valeurs clés ​​dans U sont stockés dans la table de hachage grâce à un calcul, comme le reste

• dans l'exemple, qui stocke la clé calculée

Alors voyons comment nous obtenons habituellement la valeur ?

Par exemple, nous stockons une clé sous la forme 1000 et une valeur sous la forme « Zhang San » ---> {key:1000, value:'Zhang San'>

D'après notre explication ci-dessus, Doit-il être stocké dans cet emplacement de 1000%10 ?
Lorsque nous voulons trouver la valeur Zhang San via la clé, pouvons-nous simplement rechercher dans l'emplacement key%10 ? À ce stade, vous pouvez vous arrêter et réfléchir.

Quelques terminologies de hachage (vous pouvez y jeter un bref coup d'œil)

• Toutes les clés pouvant apparaître dans la table de hachage sont appelées l'ensemble complet U

• Utilisez M pour représenter le nombre d'emplacements

• Étant donné une clé, la fonction de hachage calcule dans quel emplacement elle doit apparaître. La fonction de hachage h= k% dans l'exemple M ci-dessus, la fonction de hachage h est un mappage de la clé k à l'emplacement.

• 1000 et 10 sont tous deux stockés dans l'emplacement numéroté 0. Cette situation s'appelle une collision.

Après avoir lu ceci, je ne sais pas si vous avez une compréhension générale de ce qu'est une fonction de hachage. Grâce à l'exemple et à votre réflexion, vous pouvez revenir en arrière et lire la définition de la table de hachage en haut de l'article. Si vous pouvez le lire, alors je suppose que vous devriez le comprendre.

Fonctions de hachage couramment utilisées

Traiter les entiers h=>k%M (qui est l'exemple que nous avons donné ci-dessus)

Traiter les chaînes :

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

L'algorithme de hachage n'est pas au centre des préoccupations ici, et je ne l'ai pas étudié en profondeur. L'essentiel ici est de comprendre quel type de structure de données est une table de hachage, quels sont ses avantages et ce qu'elle fait spécifiquement.

La fonction de hachage mappe simplement les clés aux listes via un certain algorithme.

Construire une table de hachage

Grâce à l'explication ci-dessus, nous allons créer ici une table de hachage simple

La composition de la table de hachage

• Les emplacements M

• ont une fonction de hachage

• et ont une méthode d'ajout pour ajouter la valeur clé à la table de hachage

• Il existe une méthode de suppression pour supprimer

• Il existe une méthode de recherche pour trouver la valeur correspondante en fonction de la clé

Initialisation

-Initialiser le nombre d'emplacements de la table de hachage

-Utiliser un tableau pour créer M emplacements

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

Fonction de hachage

Traite le Fonction de hachage de chaînes, string est utilisé ici car il est plus général de convertir des valeurs en chaînes

Convertissez d'abord la valeur de clé transmise en chaîne Afin d'être plus rigoureux,

.

convertir les caractères Convertissez la chaîne en tableau, par exemple, 'abc' => [...'abc'] => 🎜>Convertissez le charCodeAt de chaque caractère séparément Calcul, le reste de M est considéré comme correspondant au nombre d'emplacements Vous n'avez que 10 emplacements au total. Votre valeur %10 tombera certainement dans les emplacements de 0 à 9

.

Ajouter

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

Appelez la fonction de hachage pour obtenir l'adresse de stockage correspondante (qui est l'emplacement de notre analogie)

Car il peut y avoir plusieurs valeurs stockées dans un emplacement , il doit être représenté par un tableau à deux dimensions. Par exemple, nous avons calculé que le numéro d'emplacement de l'emplacement entrant est 0, ce qui est slot[0], alors nous devrions le stocker dans slot[0][0]. le numéro d'emplacement qui arrive plus tard est également l'emplacement numéroté 0, alors nous devrions aller à slot[0][1] Stocker dans

Supprimer

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        this.slots[h].push(value);
    }

Utilisez l'algorithme de hachage pour trouver l'emplacement

Supprimer par filtrage

Rechercher

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }

Trouver l'emplacement correspondant grâce à l'algorithme de hachage

Utilisez la fonction de recherche pour trouver la valeur de la même clé

Renvoyer la valeur correspondante

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

总结

讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。

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!