JS模擬實現(xiàn)哈希表及應用詳解

更新時間：2018年05月04日 11:17:05 作者：Wayne-Zhu

這篇文章主要介紹了JS模擬實現(xiàn)哈希表及應用,結合實例形式分析了javascript模擬實現(xiàn)哈希表的步驟、相關操作技巧與使用方法,需要的朋友可以參考下

本文實例講述了JS模擬實現(xiàn)哈希表及應用。分享給大家供大家參考，具體如下：

在算法中，尤其是有關數(shù)組的算法中，哈希表的使用可以很好的解決問題，所以這篇文章會記錄一些有關js實現(xiàn)哈希表并給出解決實際問題的例子。

說明： 這篇文章所寫并不是真正意義的哈希表，只是與哈希表的使用有相似之處。

第一部分：相關知識點

屬性的枚舉:

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

輸出：

即對于對象而言，我們可以使用for in來枚舉對象的屬性。

屬性的刪除：

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

對象的屬性可以通過 delete 來刪除，并且會有一個返回值。如下：

注意：一般只有對象的屬性才可以刪除，而變量是不能刪除的，如：

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

這時打印臺輸出false，因為變量是不可被刪除的。

檢測屬性是否存在：

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

前者返回true，后者返回false。即我們可以使用in來確定一個對象是否含有該屬性。

屬性的添加：

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

屬性的添加非常簡單，如上所示，最終打印出來的對象是包含 school 屬性的。

第二部分: 使用js實現(xiàn)哈希表

下面是通過構造函數(shù)得到一個哈希表，在使用時只需實例化即可，且下面的功能較為豐富，在實際問題中，我們可以選擇性的使用。

// 創(chuàng)建構造函數(shù)HashTable
function HashTable() {
    // 初始化哈希表的記錄條數(shù)size
    var size = 0;
    // 創(chuàng)建對象用于接受鍵值對
    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;
    };
    // 根據(jù)鍵獲取value,如果不存在就返回null
    this.getValue = function (key) {
      return this.containKey(key) ? res[key] : null;
    };
    // 獲取哈希表中的所有value, 返回一個數(shù)組
    this.getAllValues = function () {
      var values = [];
      for (var prop in res) {
        values.push(res[prop]);
      }
      return values;
    };
    // 根據(jù)值獲取哈希表中的key，如果不存在就返回null
    this.getKey = function (value) {
      for (var prop in res) {
        if (res[prop] === value) {
          return prop;
        }
      }
      // 遍歷結束沒有return，就返回null
      return null;
    };
    // 獲取哈希表中所有的key,返回一個數(shù)組
    this.getAllKeys = function () {
      var keys = [];
      for (var prop in res) {
        keys.push(prop);
      }
      return keys;
    };
    // 獲取哈希表中記錄的條數(shù)，返回一個數(shù)值
    this.getSize = function () {
      return size;
    };
    // 清空哈希表，無返回值
    this.clear = function () {
      size = 0;
      res = {};
    };
}

第三部分：應用實例

問題：給定一個整型的數(shù)組（無序），找出其中的兩個數(shù)使得其和為某個指定的值，并返回這兩個數(shù)的下標（數(shù)組下標從0開始），假設數(shù)組元素的值各不相同。

實現(xiàn)如下：

<!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]) {
        // 獲取兩個下標，跳出循環(huán)
        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
   // 創(chuàng)建構造函數(shù)HashTable
  function HashTable() {
    // 初始化哈希表的記錄條數(shù)size
    var size = 0;
    // 創(chuàng)建對象用于接受鍵值對
    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;
    };
    // 根據(jù)鍵獲取value,如果不存在就返回null
    this.getValue = function (key) {
      return this.containKey(key) ? res[key] : null;
    };
    // 獲取哈希表中的所有value, 返回一個數(shù)組
    this.getAllValues = function () {
      var values = [];
      for (var prop in res) {
        values.push(res[prop]);
      }
      return values;
    };
    // 根據(jù)值獲取哈希表中的key，如果不存在就返回null
    this.getKey = function (value) {
      for (var prop in res) {
        if (res[prop] === value) {
          return prop;
        }
      }
      // 遍歷結束沒有return，就返回null
      return null;
    };
    // 獲取哈希表中所有的key,返回一個數(shù)組
    this.getAllKeys = function () {
      var keys = [];
      for (var prop in res) {
        keys.push(prop);
      }
      return keys;
    };
    // 獲取哈希表中記錄的條數(shù)，返回一個數(shù)值
    this.getSize = function () {
      return size;
    };
    // 清空哈希表，無返回值
    this.clear = function () {
      size = 0;
      res = {};
    };
  }
  </script>
</body>
</html>

在實際的使用過程中，我們可以先寫出主要的功能，然后有需要再添加。

PS：這里再為大家提供幾款hash操作相關工具供大家參考使用：

在線散列/哈希算法加密工具：
http://tools.jb51.net/password/hash_encrypt

在線MD5/hash/SHA-1/SHA-2/SHA-256/SHA-512/SHA-3/RIPEMD-160加密工具：
http://tools.jb51.net/password/hash_md5_sha

更多關于JavaScript相關內(nèi)容感興趣的讀者可查看本站專題：《javascript編碼操作技巧總結》、《JavaScript加密解密技巧匯總》、《JavaScript數(shù)學運算用法總結》、《JavaScript數(shù)據(jù)結構與算法技巧總結》及《JavaScript錯誤與調(diào)試技巧總結》

希望本文所述對大家JavaScript程序設計有所幫助。

您可能感興趣的文章: