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

到底如何理解散列表呢？下面進(jìn)入正題。

一、什么是散列表

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

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

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

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

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

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

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

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

和字典類(lèi) Dictionary 一樣，用一個(gè)對(duì)象來(lái)存儲(chǔ)所有鍵值對(duì)。

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

然后給類(lèi)添加方法，主要是這三個(gè)：

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

當(dāng)然還需要和上一篇一樣的轉(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ù)就是開(kāi)頭說(shuō)到的，將字符串轉(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 接受一個(gè) key 值，首先判斷參數(shù) key 是否是一個(gè)數(shù)值，如果是則直接返回。否則的話將 key 值轉(zhuǎn)換為字符串。

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

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

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

2.put 方法

現(xiàn)在我們有了自己的 hashCode 函數(shù)，下面來(lái)實(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 是上篇介紹的類(lèi)，用來(lái)存儲(chǔ)鍵值對(duì)。

3.get 方法

從散列表中獲取一個(gè)值也很簡(jiǎn)單。

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

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

4.delete 方法

最后一個(gè)方法是從散列表中刪除一個(gè)項(xiàng)：

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

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

三、使用散列表

首先添加幾個(gè)鍵值對(duì)：

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 值，是兩個(gè)兩位數(shù)的數(shù)字。

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

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

然后再刪除一個(gè) key：

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

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

四、總結(jié)

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

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

最新評(píng)論