Detailed explanation of JS simulation implementation of hash table and its application

This article mainly introduces JS simulation to implement hash tables and their applications. It analyzes the steps of javascript simulation to implement hash tables, related operating techniques and usage methods in the form of examples. Friends in need can refer to the following

The example in this article describes the JS simulation implementation of hash table and its application. Share it with everyone for your reference, as follows:

In algorithms, especially in algorithms related to arrays, the use of hash tables can solve problems very well, so this article will record some relevant js implementations Hash tables and give examples of solving real-world problems.

Note: What this article writes is not a real hash table, but is similar to the use of hash tables.

Part 1: Related knowledge points

Enumeration of attributes:

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

Output:

That is, for objects, we can use for in to enumerate the properties of the object.

Deletion of attributes:

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);

The attributes of the object can be deleted through delete, and there will be a return value . As follows:

Note: Generally, only the properties of objects can be deleted, but variables cannot be deleted, such as:

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

At this time, the print console outputs false because the variable cannot be deleted.

Detect whether the attribute exists:

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

The former returns true and the latter returns false. That is, we can use in to determine whether an object contains this attribute.

Adding attributes:

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

The addition of attributes is very simple, as shown above, the final printed object It contains the school attribute.

Part 2: Use js to implement hash table

The following is a hash table obtained through the constructor. When using it, just Just instantiate it, and the following functions are relatively rich. In actual problems, we can use them selectively.

// 创建构造函数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 = {};
    };
}

Part 3: Application Example

Problem: Given an integer Array (unordered), find two numbers in it such that their sum is a specified value, and return the subscripts of these two numbers (array subscripts start from 0), assuming that the values ​​of the array elements are different .

The implementation is as follows:

<!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>

In the actual use process, we can write the main functions first, and then add them if necessary.

Related recommendations:

JS implementation of Ferris wheel lottery

JS simulation method to implement encapsulation

The above is the detailed content of Detailed explanation of JS simulation implementation of hash table and its application. For more information, please follow other related articles on the PHP Chinese website!