JavaScript數據結構之散列表怎么創建

本文小編為大家詳細介紹“JavaScript數據結構之散列表怎么創建”，內容詳細，步驟清晰，細節處理妥當，希望這篇“JavaScript數據結構之散列表怎么創建”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

一、處理散列值沖突

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

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

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

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

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

1.分離鏈接

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

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

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

2.put 方法

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

對比上篇的散列表 put 方法，你會發現差別不大，變化的部分如下：

// 變化前
this.table[pos] = new ValuePair(key, value)

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

優化后的邏輯是，在存儲數據時，將鍵值對存在一個鏈表里。如果有相同的 hash 值，則向已有的鏈表中添加一個鍵值對，這樣就避免了覆蓋。

不過這種方式也有弊端，每添加一個鍵值對就要創建一個鏈表，會增加額外的內存空間。

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 方法明顯比之前的復雜了許多。主要邏輯是根據 key 找到一個鏈表，然后再遍歷鏈表找到與參數 key 相匹配的鍵值對，最后返回找到的值。

while 循環中使用 return 可以直接中止當前函數

讀到這里，這篇“JavaScript數據結構之散列表怎么創建”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。