上一篇我們一篇JavaScript 數(shù)據(jù)結(jié)構(gòu)之字典方法搞定了字典，這篇呢我們學習一個與字典非常相似的數(shù)據(jù)結(jié)構(gòu)，散列表與字典基本一致，區(qū)別是字典存儲的 key 是字符串，而散列表是一個數(shù)值（哈希值）。

到底如何理解散列表呢？下面進入正題。

一、什么是散列表

散列表，也叫做哈希表，可以根據(jù)鍵（Key）直接訪問數(shù)據(jù)在內(nèi)存中存儲的位置。

簡單來說，散列表就是字典的另一種實現(xiàn)，它的優(yōu)勢是比字典能更快地找到一個值。在常規(guī)的字典操作中，使用get()方法獲得一個值，需要遍歷整個數(shù)據(jù)結(jié)構(gòu)，這樣明顯會比較慢。

散列表為了讓查找提速，使用了一個叫散列函數(shù)的方法，將 key 轉(zhuǎn)換成一個由 Unicode 碼組合而成的數(shù)值，這個數(shù)值被稱為散列值。

最終在散列表中存儲數(shù)據(jù)的結(jié)構(gòu)是：散列值為 key，數(shù)據(jù)值為 value。這樣查找數(shù)據(jù)時，就可以通過散列值直接定位位置，就好比數(shù)組下標一樣直接定位元素，免去了整個數(shù)據(jù)結(jié)構(gòu)的遍歷，因此比字典的字符串定位要快上許多。

上述的概念如果比較難理解，看一張圖你就明白了：

散列表還可以用來做數(shù)據(jù)庫的索引。在關(guān)系型數(shù)據(jù)庫如 MySQL 中，當你新建一張表并創(chuàng)建好了字段，你還可以為某些字段設(shè)置索引。設(shè)置索引是在散列表中存儲了索引值和對應(yīng)記錄的引用，以便快速的找到數(shù)據(jù)。

當然了散列表還有其他應(yīng)用，比如我們 JavaScript 當中的對象，那就是一個妥妥的散列表。

二、創(chuàng)建散列表

和字典類 Dictionary 一樣，用一個對象來存儲所有鍵值對。

class HashMap {
  constructor() {
    this.table = {}
  }
}

然后給類添加方法，主要是這三個：

• put：向散列表增加/更新一個項
• remove：根據(jù)鍵名移除鍵值
• get：根據(jù)鍵名獲取鍵值

當然還需要和上一篇一樣的轉(zhuǎn)換字符串函數(shù)：

function keyToString(item) {
  if(item === null) {
    return 'NULL'
  }
  if(item === undefined) {
    return 'UNDEFINED'
  }
  if(item instanceof String) {
    return `${item}`
  }
  return item.toString()
}

1.創(chuàng)建散列函數(shù)

散列函數(shù)就是開頭說到的，將字符串轉(zhuǎn)換為散列值的函數(shù)。

hashCode(key) {
  if(typeof key === 'number') {
    return key;
  }
  let tableKey = keyToString(key)
  let hash = 0;
  for(let i = 0; i < tableKey.length; i++) {
    hash += tableKey.charCodeAt(i)
  }
  return Math.ceil(hash / 20);
}

上述代碼中，hashCode 接受一個 key 值，首先判斷參數(shù) key 是否是一個數(shù)值，如果是則直接返回。否則的話將 key 值轉(zhuǎn)換為字符串。

結(jié)下來的邏輯是，定義一個 hash 變量為 0，然后循環(huán)字符串的長度。在循環(huán)體內(nèi)通過 charCodeAt 方法獲取每個字母對應(yīng)的 Unicode 編碼，并將結(jié)果累加。

最后一行，返回 Math.ceil(hash / 20) 的值，這是什么意思呢？

其實作用非常簡單，就是為了避免 hash 值過大，然后才將它除以一個數(shù)值然后取整。這里用的 20，你也可以根據(jù)你的是實際情況決定數(shù)值范圍，改用其他數(shù)值。

2.put 方法

現(xiàn)在我們有了自己的 hashCode 函數(shù)，下面來實現(xiàn) put 方法。

put(key, value) {
  if(key !== null && value !== null) {
    let pos = this.hashCode(key)
    this.table[pos] = new ValuePair(key, value)
    return true;
  }
  return false;
}

put 方法與字典的 set 方法幾乎一樣，區(qū)別只是 table 的屬性從 key 變成了 hash。這也是散列表與字典的不同之處，只需要確保 hash 唯一即可。

ValuePair 是上篇介紹的類，用來存儲鍵值對。

3.get 方法

從散列表中獲取一個值也很簡單。

get(key) {
  let valuePair = this.table[this.hashCode(key)] 
  return valuePair ? valuePair.value : undefined;
}

首先通過前面創(chuàng)建的 hashCode 方法獲取到 key 的 hash 值，然后在 table 中獲取這個 hash 有沒有匹配的 value。如果有則返回 value，無則返回 undefined。

4.delete 方法

最后一個方法是從散列表中刪除一個項：

remove(key) {
  let hash = this.hashCode(key)
  if(this.table[hash]) {
    delete this.table[hash]
    return true;
  }
  return false;
}

以上就是散列表的全部實現(xiàn)，下面我們來使用。

三、使用散列表

首先添加幾個鍵值對：

var hashmap = new HashMap()
hashmap.put('name', '捷德')
hashmap.put('color', '紅黑')
hashmap.put('father', '貝利亞')

console.log('name：', hashmap.hashCode('name')) // name：21
console.log('father：', hashmap.hashCode('father')) // father：32

我們用 hashCode 方法獲取了 key 的 hash 值，是兩個兩位數(shù)的數(shù)字。

接著我們根據(jù) key 獲取 value：

console.log(hashmap.get("name")); // 捷德
console.log(hashmap.get("color")); // 紅黑
console.log(hashmap.get("size")); // undefined

然后再刪除一個 key：

console.log(hashmap.remove("color")); // true
console.log(hashmap.remove("size")); // false
console.log(hashmap.get("color")); // undefined

你看這三個方法在使用的過程中，和字典的效果幾乎一致。我們在類內(nèi)部實現(xiàn)的 hash 值，在使用類方法的時候是無感知的，只是內(nèi)部數(shù)據(jù)存儲的結(jié)構(gòu)不同。

四、總結(jié)

本篇介紹了很常用的散列表數(shù)據(jù)結(jié)構(gòu)，你學會了嗎？散列表與字典很相似，了解他們的區(qū)別非常關(guān)鍵。

不過本篇實現(xiàn)的散列表還有一個異常情況，就是生成的散列值可能重復(fù)，這樣就會出現(xiàn)覆蓋的情況。下一篇，我們介紹如何處理散列值的沖突。

最新評論