JavaScript 中的雜湊表資料結構

雜湊表是一種以關聯方式儲存資料的資料結構。在雜湊表中，資料以陣列格式儲存，其中每個資料值都有其自己的唯一索引值。如果我們知道所需資料的索引，則訪問資料將變得非常快。

因此，它成為一種資料結構，其中插入和搜尋操作非常快，而不管資料的大小如何。雜湊表使用陣列作為儲存介質，並使用雜湊技術生成要插入元素或從中定位元素的索引。

雜湊

雜湊是一種將一系列鍵值轉換為陣列索引範圍的技術。我們將使用模運算子來獲取一系列鍵值。考慮一個大小為 20 的雜湊表的示例，以及要儲存的以下專案。專案採用 (鍵，值) 格式。

這裡我們有一個雜湊函式，它接收鍵併為表生成索引。這些索引讓我們知道值儲存在哪裡。現在，每當我們想要搜尋與鍵關聯的值時，我們只需要再次對鍵執行雜湊函式，並在幾乎恆定的時間內獲取值。

雜湊函式的設計相當困難。讓我們舉個例子 -

假設我們有以下雜湊函式 -

示例

function modBy11(key) {
   return key % 11;
}

然後我們開始對要儲存的鍵值對執行此函式，例如 -

  • (15, 20) - 雜湊碼：4
  • (25, 39) - 雜湊碼：3
  • (8, 55) - 雜湊碼：8
  • (26, 84) - 雜湊碼：4

在這裡我們看到發生了衝突，即，如果我們首先儲存 15，然後遇到使用此雜湊函式的鍵 26，它將嘗試將此條目固定在同一個位置。這稱為衝突。為了處理這種情況，我們需要定義衝突處理機制。有一些定義明確的簡單衝突解決演算法。例如 -

  • 線性探測：在此演算法中，我們可以透過檢視下一個單元格直到找到空單元格來搜尋陣列中的下一個空位置。在我們的示例中，由於位置 4 已佔用，因此我們可以在位置 5 中填充它。
  • 分離連結：在此實現中：我們將雜湊表中的每個位置與一個列表關聯。每當我們遇到衝突時，我們都會將鍵值對追加到此列表的末尾。如果鏈不斷變長，這可能會導致更長的搜尋時間。

現在我們瞭解了雜湊表的工作原理以及如何使用衝突解決，讓我們實現 HashTable 類。

我們將實現的方法

我們將在我們的實現中實現這些方法 -

  • put(key, value)：將新的鍵值對新增到雜湊表
  • get(key)：獲取與鍵關聯的值
  • remove(key)：從表中刪除鍵值對
  • forEach()：允許迭代所有鍵值對
  • static join()：一個靜態方法，用於將 2 個雜湊表連線到一個新的雜湊表中

更新於： 2020年6月15日

1K+ 瀏覽量

啟動您的 職業生涯

透過完成課程獲得認證

開始學習
廣告