上篇末尾我們遺留了一個(gè)問(wèn)題，就是將字符串轉(zhuǎn)化為散列值后可能出現(xiàn)重復(fù)。當(dāng)以散列值（hash 值）為 key 存儲(chǔ)數(shù)據(jù)時(shí)，就會(huì)有覆蓋已有數(shù)據(jù)的風(fēng)險(xiǎn)。本篇我們看如何處理散列值沖突的問(wèn)題，并實(shí)現(xiàn)更完美的散列表。

一、處理散列值沖突

有時(shí)候一些鍵會(huì)有相同的散列值。比如 aab 和 baa，從字符串的角度來(lái)說(shuō)它們是不同的值，但是按照我們的散列函數(shù)邏輯，將每個(gè)字母的 Unicode 碼累加得出的散列值，一定是一樣的。

我們知道在 JavaScript 對(duì)象當(dāng)中，如果賦值時(shí)指定的 key 已存在，那么就會(huì)覆蓋原有的值，

比如這個(gè)例子：

var json = { 18: '雷歐' }
json[18] = '歐布'
console.log(json) // { 18: '歐布' }

為了避免上述代碼中出現(xiàn)的風(fēng)險(xiǎn)，我們需要想辦法處理，如何使 key != key，則 hash != hash？

目前可靠的方法有兩個(gè)，分別是：分離鏈接 和 線性探查。

1.分離鏈接

分離鏈接法是指在散列表存儲(chǔ)數(shù)據(jù)時(shí)，value 部分用 鏈表 來(lái)代替之前的 鍵值對(duì)。鍵值對(duì)只能存儲(chǔ)一個(gè)，而鏈表可以存儲(chǔ)多個(gè)鍵值對(duì)。如果遇到相同的散列值，則在已有的鏈表中添加一個(gè)鍵值對(duì)即可。

我們需要重寫(xiě)三個(gè)方法：put、get 和 remove。我們看如何實(shí)現(xiàn)：

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

2.put 方法

首先還是基本的類(lèi)結(jié)構(gòu)，然后看 put 方法：

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

LinkedList 類(lèi)是標(biāo)準(zhǔn)的鏈表類(lèi)，在鏈表篇講過(guò)如何實(shí)現(xiàn)，這里直接使用

對(duì)比上篇的散列表 put 方法，你會(huì)發(fā)現(xiàn)差別不大，變化的部分如下：

// 變化前
this.table[pos] = new ValuePair(key, value)
// 變化后
if(!this.table[pos]) {
  this.table[pos] = new LinkedList()
}
this.table[pos].push(new ValuePair(key, value))

優(yōu)化后的邏輯是，在存儲(chǔ)數(shù)據(jù)時(shí)，將鍵值對(duì)存在一個(gè)鏈表里。如果有相同的 hash 值，則向已有的鏈表中添加一個(gè)鍵值對(duì)，這樣就避免了覆蓋。

不過(guò)這種方式也有弊端，每添加一個(gè)鍵值對(duì)就要?jiǎng)?chuàng)建一個(gè)鏈表，會(huì)增加額外的內(nèi)存空間。

3.get 方法

get 方法：

get(key) { 
  let linkedList = this.table[this.hashCode(key)]
  if(linkedList && !linkedList.isEmpty()) {
    let current = linkedList.getItemAt(0);
    while(current) {
      if(current.value.key == key) {
        return current.value.value
      }
      current = current.next
    }
  }
  return undefined; 
}

新的 get 方法明顯比之前的復(fù)雜了許多。主要邏輯是根據(jù) key 找到一個(gè)鏈表，然后再遍歷鏈表找到與參數(shù) key 相匹配的鍵值對(duì)，最后返回找到的值。

while 循環(huán)中使用 return 可以直接中止當(dāng)前函數(shù)

到此這篇關(guān)于 JavaScript 數(shù)據(jù)結(jié)構(gòu)之散列表的創(chuàng)建的文章就介紹到這了,更多相關(guān) JavaScript 散列表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: