前言：

上一篇我們介紹了什么是散列表，并且用通俗的語言解析了散列表的存儲結(jié)構(gòu)，最后動手實現(xiàn)了一個散列表，相信大家對散列表已經(jīng)不陌生了。

如果還不清楚散列表，請先閱讀上一篇文章：JavaScript 數(shù)據(jù)結(jié)構(gòu)之散列表的創(chuàng)建(1)

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

一、處理散列值沖突

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

我們知道在 JavaScript 對象當中，如果賦值時指定的 key 已存在，那么就會覆蓋原有的值，

比如這個例子：

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

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

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

1.分離鏈接

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

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

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

2.put 方法

首先還是基本的類結(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 類是標準的鏈表類，在鏈表篇講過如何實現(xiàn)，這里直接使用

對比上篇的散列表 put 方法，你會發(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)化后的邏輯是，在存儲數(shù)據(jù)時，將鍵值對存在一個鏈表里。如果有相同的 hash 值，則向已有的鏈表中添加一個鍵值對，這樣就避免了覆蓋。

不過這種方式也有弊端，每添加一個鍵值對就要創(chuàng)建一個鏈表，會增加額外的內(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 方法明顯比之前的復雜了許多。主要邏輯是根據(jù) key 找到一個鏈表，然后再遍歷鏈表找到與參數(shù) key 相匹配的鍵值對，最后返回找到的值。

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

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

最新評論