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 個雜湊表加入到一個新的雜湊表中

Samual Sam

更新於：2020年6月15日

1K+ 次瀏覽

啟動你的職業生涯

完成課程獲得認證

開始學習