qu'est-ce que le hachage javascript

En JavaScript, le hachage fait référence à une table de hachage, qui est une structure de données qui accède directement à l'emplacement de stockage en mémoire en fonction de mots-clés via la table de hachage, une certaine relation est établie entre l'emplacement de stockage de l'élément de données et le mot-clé de ; l'élément de données. Une relation correspondante, et la fonction qui établit cette relation correspondante est appelée fonction de hachage.

L'environnement d'exploitation de ce tutoriel : système Windows 7, JavaScript version 1.8.5, ordinateur Dell G3.

Concept de base du hachage javascript :

La table de hachage (table de hachage) est une structure de données qui accède directement à l'emplacement de stockage en mémoire en fonction de mots-clés, via la table de hachage, l'emplacement de stockage des éléments de données et l'emplacement. des éléments de données Une certaine correspondance s'établit entre les mots-clés, et la fonction qui établit cette correspondance est appelée fonction de hachage.

Comment construire une table de hachage :

Supposons que le nombre d'éléments de données à stocker est n, définissez une unité de stockage continue d'une longueur de m (m > n) et utilisez le mot-clé Ki ( de chaque élément de données) 0

D'un point de vue mathématique, la fonction de hachage est en fait un mappage de mots-clés sur des unités de mémoire. Par conséquent, nous espérons que l'adresse Huaxi calculée par la fonction de hachage pourra être mappée à un emplacement aussi uniformément que possible grâce à l'opération la plus simple possible. . Dans une série d'unités de mémoire, il y a trois points clés dans la construction d'une fonction de hachage : (1) Le processus de fonctionnement doit être aussi simple et efficace que possible pour améliorer l'efficacité de l'insertion et de la récupération de la table de hachage ; la fonction doit avoir un bon type de hachage, Pour réduire la probabilité de collision de hachage ; Troisièmement, la fonction de hachage doit avoir une plus grande compression pour économiser de la mémoire.

Méthodes couramment utilisées :

• Méthode d'adresse directe : utilisez une certaine valeur de fonction linéaire du mot-clé comme adresse de hachage, qui peut être exprimée comme hash(K)=aK+C ; , mais l'inconvénient est que la complexité spatiale peut être plus élevée, adaptée aux cas avec moins d'éléments.
• Méthode de division avec reste : c'est l'adresse de hachage qui est laissée en divisant le mot-clé de l'élément de données par une certaine constante. Cette méthode est simple à calculer et a un large éventail d'applications. C'est une fonction de hachage fréquemment utilisée et peut être. exprimée sous la forme :
  hash(K=K mod C; La clé de cette méthode est la sélection de la constante. L'exigence générale est qu'elle soit proche ou égale à la longueur de la table de hachage elle-même. La théorie de la recherche montre que la constante fonctionne mieux lors de la sélection de nombres premiers
• Méthode d'analyse numérique : cette méthode consiste à prendre des nombres avec des valeurs relativement uniformes dans les mots-clés des éléments de données comme adresse de hachage. Cela peut éviter autant que possible les conflits, mais cette méthode l'est. convient uniquement aux situations où tous les mots-clés sont connus. Pour ceux qui souhaitent concevoir La table de hachage plus générale n'est pas applicable
• Méthode de la somme carrée : convertissez la chaîne actuelle en une valeur Unicode et trouvez le carré de cette valeur. les chiffres de la valeur au carré sont les valeurs de hachage du nombre actuel. Plus précisément, le nombre de bits dépend de la taille de la table de hachage actuelle
• Méthode de somme segmentée : divisez la valeur à insérer en plusieurs segments en fonction de la valeur au carré. nombre de bits dans la table de hachage actuelle, ajoutez les segments et supprimez le bit le plus élevé du résultat. C'est la valeur de hachage de cette valeur.

Solution au conflit de hachage :

Lors de la construction de la table de hachage, il y a un. problème : pour deux mots-clés différents, l'adresse de hachage est calculée par notre fonction de hachage. Lorsque la même adresse de hachage est obtenue, nous appelons ce phénomène un conflit de hachage

Le conflit de hachage est principalement lié à deux facteurs

(1. ) Facteur de remplissage, qui fait référence au facteur de remplissage. Le rapport entre le nombre d'éléments de données stockés dans la table de hachage et la taille de l'espace d'adressage de hachage, a = n/m ; plus a est petit, plus la possibilité de conflit est faible, au contraire, la possibilité de conflit est plus grande, mais a Plus l'utilisation de l'espace est faible, plus l'utilisation de l'espace est grande, plus l'utilisation de l'espace est élevée. généralement contrôlé entre 0,6 et 0,9, tandis que HashTable dans .net définit directement la valeur maximale de a comme 0,72 (bien que le MSDN officiel de Microsoft indique que le facteur de remplissage par défaut de HashTable est de 1,0, il s'agit en fait d'un multiple de 0,72)
(2) Il est lié à la fonction de hachage utilisée. Si la fonction de hachage est appropriée, vous pouvez répartir les adresses de hachage aussi uniformément que possible dans l'espace d'adressage de hachage, réduisant ainsi l'apparition de conflits, mais l'acquisition d'une bonne fonction de hachage dépend en grande partie de beaucoup de pratique

1) Adressage ouvert. Méthode

Hi=(H(key) + di) MOD m i=1,2,…k(k Où H(key) est le hachage. fonction ; m est la longueur de la table de hachage ; di est une séquence incrémentielle. Il existe 3 séquences incrémentales :
①Détection linéaire puis hachage : di=1,2,3,…,m-1
②Détection secondaire puis hachage : di=1^2,-12,2 ^2,-2 2,…±k^2(k ③Détection pseudo-aléatoire puis hachage : di=séquence de nombres pseudo-aléatoires

Inconvénients :

Nous pouvons constater un phénomène : lorsque les enregistrements sont déjà renseignés aux positions i, i+1 et i+2 dans le tableau, les enregistrements avec les adresses de hachage suivantes i, i+1, i+2 et i+ 3 sont tous La position de i+3 sera remplie. Ce phénomène de deux enregistrements avec des premières adresses de hachage différentes en compétition pour la même adresse de hachage ultérieure qui se produit lors du traitement des conflits est appelé « agrégation secondaire », c'est-à-dire lors du traitement des synonymes In Au processus de conflit, des conflits non synonymes s'ajoutent. Mais d'un autre côté, utiliser la détection linéaire puis le hachage pour gérer les conflits peut garantir que tant que la table de hachage n'est pas pleine, une adresse Hk qui n'entre pas en conflit peut toujours être trouvée. La détection secondaire et le rehachage ne sont possibles que lorsque la longueur m de la table de hachage est un nombre premier de la forme 4j+3 (j est un nombre entier). Autrement dit, la méthode d'adressage ouverte provoquera une agrégation secondaire, ce qui nuira à la recherche.

2) Méthode de re-hachage

Hi = RHi (clé), i=1,2,...k RHi sont toutes des fonctions de hachage différentes, c'est-à-dire que lorsque des synonymes provoquent des conflits d'adresse, l'adresse d'un autre hachage La fonction est calculée jusqu'à ce qu'aucun conflit ne se produise. Cette méthode est moins sujette à l’agrégation, mais augmente le temps de calcul.

Inconvénients : Temps de calcul augmenté.

3) Méthode d'adresse en chaîne (méthode zip)

Stocke tous les enregistrements dont les mots-clés sont des synonymes dans la même liste chaînée linéaire.

Avantages :

①La méthode de fermeture éclair est simple à gérer les conflits et ne présente aucun phénomène d'accumulation, c'est-à-dire que les mots non synonymes ne seront jamais en conflit, donc la longueur moyenne de recherche est plus courte ;
②Étant donné l'espace des nœuds sur chaque liste chaînée dans le la méthode zipper est appliquée dynamiquement, elle est donc plus adaptée aux situations où la longueur de la table ne peut pas être déterminée avant de créer la table
③ Afin de réduire les conflits, la méthode d'adressage ouverte nécessite que le facteur de remplissage α soit petit, donc lorsque le nœud la taille est grande, beaucoup d’espace sera gaspillé. Dans la méthode Zipper, α ≥ 1 est acceptable, et lorsque le nœud est grand, le domaine de pointeur ajouté dans la méthode Zipper est négligeable, économisant ainsi de l'espace
④ Dans une table de hachage construite avec la méthode Zipper, l'opération de suppression de nœuds ; est facile à mettre en œuvre. Supprimez simplement le nœud correspondant sur la liste chaînée. Pour la table de hachage construite par la méthode d'adresse ouverte, la suppression d'un nœud ne peut pas simplement laisser l'espace du nœud supprimé vide, sinon le chemin de recherche du nœud synonyme qui est rempli dans la table de hachage après celui-ci sera tronqué. En effet, dans diverses méthodes d'adresse ouverte, les unités d'adresse vides (c'est-à-dire les adresses ouvertes) sont des conditions d'échec de la recherche. Par conséquent, lors de l'exécution d'une opération de suppression sur une table de hachage qui utilise la méthode d'adresse ouverte pour gérer les conflits, elle peut uniquement marquer le nœud supprimé pour suppression, mais ne peut pas réellement supprimer le nœud.

Inconvénients :

L'inconvénient de la méthode zipper est que les pointeurs nécessitent de l'espace supplémentaire, donc lorsque la taille du nœud est petite, la méthode d'adressage ouverte est plus économe en espace, et si l'espace du pointeur enregistré est utilisé pour augmenter la taille de la table de hachage, elle peut être utilisée. Le facteur de remplissage devient plus petit, ce qui à son tour réduit les conflits dans la méthode d'adressage ouverte, augmentant ainsi la vitesse de recherche moyenne.

4) Établir une zone de débordement publique

Supposons que la plage de valeurs de la fonction de hachage est [0,m-1], puis laissez le vecteur HashTable[0...m-1] être la base table, et chaque composant est stocké dans un enregistrement et configure le vecteur OverTable[0...v] comme table de débordement. Tous les enregistrements dont les mots-clés sont synonymes des mots-clés de la table de base, quelles que soient leurs adresses de hachage obtenues par la fonction de hachage, seront renseignés dans la table de débordement en cas de conflit.

Une implémentation de table de hachage d'une fonction de hachage simple sans gestion des conflits

class Hash {
  constructor() {
    this.table = new Array(1024);
  }
  hash(data) {
    //就将字符串中的每个字符的ASCLL码值相加起来，再对数组的长度取余
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    console.log("Hash Value: " + data + " -> " + total);
    return total % this.table.length;
  }
  insert(key, val) {
    var pos = this.hash(key);
    this.table[pos] = val;
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

utilise la méthode du centre carré pour construire la fonction de hachage et la méthode de détection linéaire de la méthode d'adresse ouverte pour résoudre les conflits.

class Hash {
  constructor() {
    this.table = new Array(1000);
  }
  hash(data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    //把字符串转化为字符用来求和之后进行平方运算
    var s = total * total + ""
    //保留中间2位
    var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1
    console.log("Hash Value: " + data + " -> " + index);
    return index;
  }
  solveClash(index, value) {
    var table = this.table
    //进行线性开放地址法解决冲突
    for (var i = 0; index + i < 1000; i++) {
      if (table[index + i] == null) {
        table[index + i] = value;
        break;
      }
    }
  }
  insert(key, val) {
    var index = this.hash(key);
    //把取中当做哈希表中索引
    if (this.table[index] == null) {
      this.table[index] = val;
    } else {
      this.solveClash(index, val);
    }
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

【Apprentissage recommandé : Tutoriel avancé javascript】

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!