Explication détaillée de la mise en œuvre de la simulation JS de la table de hachage et de son application

Cet article présente principalement la simulation JS pour implémenter les tables de hachage et leurs applications. Il analyse les étapes de la simulation javascript pour implémenter les tables de hachage, les techniques d'exploitation associées et les méthodes d'utilisation sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

Les exemples de cet article décrivent l'implémentation de simulation JS des tables de hachage et leurs applications. Partagez-le avec tout le monde pour votre référence, comme suit :

Dans les algorithmes, en particulier dans les algorithmes liés aux tableaux, l'utilisation de tables de hachage peut très bien résoudre les problèmes, cet article enregistrera donc quelques implémentations js pertinentes Tables de hachage et donner des exemples de résolution de problèmes du monde réel.

Remarque : Cet article ne concerne pas une table de hachage au sens propre du terme, mais est similaire à l'utilisation d'une table de hachage.

Partie 1 : Points de connaissances associés

Énumération des attributs :

var person = {
  name: "zzw",
  sex: "Male",
  age: 21
};
for (var prop in person) {
  console.log(prop + " ",person[prop]);
}

Sortie :

C'est-à-dire que pour les objets, nous pouvons utiliser for in pour énumérer les propriétés de l'objet.

Suppression d'attributs :

var person = {
  name: "zzw",
  sex: "Male",
  age: 21
};
var ifRemove = delete person.name;
for (var prop in person) {
  console.log(prop + " ",person[prop]);
}
console.log(ifRemove);

Les attributs d'un objet peuvent être supprimés par delete, et là sera une valeur de retour. Comme suit :

Remarque : Généralement, seuls les attributs des objets peuvent être supprimés, mais les variables ne peuvent pas être supprimées, telles que :

var x = 1;
console.log(delete x);

À ce stade, la console d'impression affiche false car la variable ne peut pas être supprimée.

Détecter si l'attribut existe :

var person = {
  name: "zzw",
  sex: "Male",
  age: 21
};
console.log("age" in person);
console.log("someOther" in person);

Le premier renvoie vrai et le second renvoie faux. Autrement dit, nous pouvons utiliser in pour déterminer si un objet contient cet attribut.

Ajout d'attributs :

var person = {
  name: "zzw",
  sex: "Male",
  age: 21
};
person["school"] = "XJTU";
console.log(person);

L'ajout d'attributs est très simple, comme indiqué ci-dessus, et finalement imprimé L'objet contient l'attribut école.

Partie 2 : Utiliser js pour implémenter une table de hachage

Ce qui suit est une table de hachage obtenue via le constructeur. Lors de son utilisation, il suffit de l'utiliser. Instanciez-le simplement, et les fonctions suivantes sont relativement riches dans les problèmes réels, nous pouvons les utiliser de manière sélective.

// 创建构造函数HashTable
function HashTable() {
    // 初始化哈希表的记录条数size
    var size = 0;
    // 创建对象用于接受键值对
    var res = {};
    // 添加关键字，无返回值
    this.add = function (key, value) {
      //判断哈希表中是否存在key，若不存在，则size加1，且赋值
      if (!this.containKey(key)) {
        size++;
      }
      // 如果之前不存在，赋值； 如果之前存在，覆盖。
      res[key] = value;
    };
    // 删除关键字, 如果哈希表中包含key，并且delete返回true则删除，并使得size减1
    this.remove = function (key) {
      if (this.containKey(key) && (delete res[key])) {
        size--;
      }
    };
    // 哈希表中是否包含key，返回一个布尔值
    this.containKey = function (key) {
      return (key in res);
    };
    // 哈希表中是否包含value，返回一个布尔值
    this.containValue = function (value) {
      // 遍历对象中的属性值，判断是否和给定value相等
      for (var prop in res) {
        if (res[prop] === value) {
          return true;
        }
      }
      return false;
    };
    // 根据键获取value,如果不存在就返回null
    this.getValue = function (key) {
      return this.containKey(key) ? res[key] : null;
    };
    // 获取哈希表中的所有value, 返回一个数组
    this.getAllValues = function () {
      var values = [];
      for (var prop in res) {
        values.push(res[prop]);
      }
      return values;
    };
    // 根据值获取哈希表中的key，如果不存在就返回null
    this.getKey = function (value) {
      for (var prop in res) {
        if (res[prop] === value) {
          return prop;
        }
      }
      // 遍历结束没有return，就返回null
      return null;
    };
    // 获取哈希表中所有的key,返回一个数组
    this.getAllKeys = function () {
      var keys = [];
      for (var prop in res) {
        keys.push(prop);
      }
      return keys;
    };
    // 获取哈希表中记录的条数，返回一个数值
    this.getSize = function () {
      return size;
    };
    // 清空哈希表，无返回值
    this.clear = function () {
      size = 0;
      res = {};
    };
}

Partie 3 : Exemple d'application

Problème : étant donné un tableau d'entiers (non ordonné), recherchez-y deux nombres tels que leur somme soit une valeur spécifiée et renvoyez les indices de ces deux nombres (les indices du tableau commencent à 0), en supposant que les valeurs des éléments du tableau ne sont pas les mêmes.

est implémenté comme suit :

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>哈希表的使用</title>
</head>
<body>
  <script>
  function queryIndex(arr, result) {
    var hashTable = new HashTable();
    var arrLength = arr.length;
    var sub = [];
    for (var i = 0; i < arrLength; i++) {
      // 扫描一遍，存储下标和值
      hashTable.add(i, arr[i]);
    }
    for (var j = 0; j < arrLength; j++) {
      if (hashTable.containValue(result - arr[j]) && result !== 2*arr[j]) {
        // 获取两个下标，跳出循环
        sub.push(j);
        var antherIndex = Number(hashTable.getKey(result - arr[j]));
        sub.push(antherIndex);
        break;
      }
    }
    if (sub.length !== 0) {
      return sub;
    } else {
      return -1;
    }
  }
  console.log(queryIndex([1,5,7,3,8], 15)); // 2, 4
  console.log(queryIndex([8,18,28,12,29,17], 46)); // 2, 4
  console.log(queryIndex([8,18,28,12,29,17], 2)); // -1
   // 创建构造函数HashTable
  function HashTable() {
    // 初始化哈希表的记录条数size
    var size = 0;
    // 创建对象用于接受键值对
    var res = {};
    // 添加关键字，无返回值
    this.add = function (key, value) {
      //判断哈希表中是否存在key，若不存在，则size加1，且赋值
      if (!this.containKey(key)) {
        size++;
      }
      // 如果之前不存在，赋值； 如果之前存在，覆盖。
      res[key] = value;
    };
    // 删除关键字, 如果哈希表中包含key，并且delete返回true则删除，并使得size减1
    this.remove = function (key) {
      if (this.containKey(key) && (delete res[key])) {
        size--;
      }
    };
    // 哈希表中是否包含key，返回一个布尔值
    this.containKey = function (key) {
      return (key in res);
    };
    // 哈希表中是否包含value，返回一个布尔值
    this.containValue = function (value) {
      // 遍历对象中的属性值，判断是否和给定value相等
      for (var prop in res) {
        if (res[prop] === value) {
          return true;
        }
      }
      return false;
    };
    // 根据键获取value,如果不存在就返回null
    this.getValue = function (key) {
      return this.containKey(key) ? res[key] : null;
    };
    // 获取哈希表中的所有value, 返回一个数组
    this.getAllValues = function () {
      var values = [];
      for (var prop in res) {
        values.push(res[prop]);
      }
      return values;
    };
    // 根据值获取哈希表中的key，如果不存在就返回null
    this.getKey = function (value) {
      for (var prop in res) {
        if (res[prop] === value) {
          return prop;
        }
      }
      // 遍历结束没有return，就返回null
      return null;
    };
    // 获取哈希表中所有的key,返回一个数组
    this.getAllKeys = function () {
      var keys = [];
      for (var prop in res) {
        keys.push(prop);
      }
      return keys;
    };
    // 获取哈希表中记录的条数，返回一个数值
    this.getSize = function () {
      return size;
    };
    // 清空哈希表，无返回值
    this.clear = function () {
      size = 0;
      res = {};
    };
  }
  </script>
</body>
</html>

Dans le processus d'utilisation réel, nous pouvons d'abord écrire les fonctions principales, puis les ajouter si nécessaire Ajouter à.

Recommandations associées :

JS pour implémenter la loterie de la grande roue

Simulation JS pour implémenter la méthode d'encapsulation

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!