數據結構中的散列：函數、技術 [附示例]

介紹

散列是一種重要的數據結構，旨在解決在數組中高效查找和存儲數據的問題。 例如，如果您有一個包含 20000 個號碼的列表，並且您指定了一個要在該列表中搜索的號碼 - 您將掃描列表中的每個號碼，直到找到匹配項。

您需要花費大量時間來搜索整個列表並找到該特定號碼。 這種手動掃描過程不僅耗時而且效率低下。 通過數據結構中的散列，您可以縮小搜索範圍並在幾秒鐘內找到數字。

本博客將通過示例讓您更深入地了解哈希方法、哈希表和線性探測。

什麼是數據結構中的散列？

數據結構中的散列是一種使用散列函數將大量數據映射到小表中的技術。 它也被稱為消息摘要功能。 它是一種從類似項目的集合中唯一標識特定項目的技術。

它使用哈希表以數組格式存儲數據。 數組中的每個值都分配了一個唯一的索引號。 哈希表使用一種技術為以數組格式存儲的每個值生成這些唯一索引號。 這種技術稱為散列技術。

您只需要查找所需項目的索引，而不需要查找數據。 通過索引，您可以快速掃描整個列表並檢索您想要的項目。 當您需要在特定位置插入數據時，索引還有助於插入操作。 無論表有多大或多小，您都可以在幾秒鐘內更新和檢索數據。

數據結構中的散列是一個兩步過程。

1. 散列函數將項目轉換為小整數或散列值。 該整數用作存儲原始數據的索引。
2. 它將數據存儲在哈希表中。 您可以使用哈希鍵快速定位數據。

數據結構中的散列示例

以下是數據結構中散列的真實示例-

• 在學校，老師為每個學生分配一個唯一的捲號。 稍後，教師使用該卷號檢索有關該學生的信息。
• 圖書館有無限多的書。 圖書管理員為每本書分配一個唯一的編號。 這個唯一編號有助於識別書架上書籍的位置。

結帳：數據結構中的排序

哈希函數

數據結構中的散列函數將任意大小的數據映射到固定大小的數據。 它返回以下值：一個小整數值（也稱為散列值）、散列碼和散列和。

哈希=哈希函數（鍵）

索引 = 哈希 % array_size

has 函數必須滿足以下要求：

• 一個好的散列函數很容易計算。
• 一個好的散列函數永遠不會卡在集群中，並且在散列表中均勻分佈鍵。
• 當兩個元素或項目分配給相同的哈希值時，一個好的哈希函數可以避免衝突。

哈希表

數據結構中的散列使用散列表來存儲鍵值對。 然後哈希表使用哈希函數生成索引。 散列使​​用此唯一索引來執行插入、更新和搜索操作。

數據結構中的散列是如何工作的？

在散列中，散列函數將字符串或數字映射到一個小的整數值。 散列表使用散列函數從列表中檢索項目。 散列技術的目標是在數組中均勻分佈數據。 散列為所有元素分配一個唯一鍵。 哈希表使用這個鍵來訪問列表中的數據。

哈希表將數據存儲在鍵值對中。 密鑰充當散列函數的輸入。 然後散列函數為每個存儲的值生成一個唯一的索引號。 索引號保留與該鍵對應的值。 散列函數返回一個小的整數值作為輸出。 散列函數的輸出稱為散列值。

讓我們通過一個例子來理解數據結構中的散列。 想像一下，您需要在一個包含 30 個單元格的哈希表中存儲一些項目（以鍵值對的形式排列）。

值為： (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

哈希表如下所示：

另請閱讀： Python 中的數據結構類型

碰撞解決技術

如果在哈希表中為兩個鍵分配了相同的索引號，則數據結構中的哈希會發生衝突。 衝突產生了一個問題，因為哈希表中的每個索引都應該只存儲一個值。 數據結構中的散列使用幾種衝突解決技術來管理散列表的性能。

線性探測

數據結構中的散列會導致數組索引已被佔用以存儲值。 在這種情況下，散列會執行搜索操作并線性探測下一個空單元格。

線性探測示例

假設您被要求將一些項目存儲在大小為 30 的哈希表中。這些項目已經以鍵值對格式排序。 給出的值是： (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

hash(n) 是使用散列函數計算的索引，T 是表大小。 如果 slot index = ( hash(n) % T) 已滿，那麼我們通過添加 1 ((hash(n) + 1) % T) 來尋找下一個 slot index。 如果 (hash(n) + 1) % T 也滿了，那麼我們嘗試 (hash(n) + 2) % T。如果 (hash(n) + 2) % T 也滿了，那麼我們嘗試 (hash( n) + 3) % T。

哈希表如下所示：

雙重哈希

雙散列技術使用兩個散列函數。 當第一個函數引起衝突時，第二個哈希函數開始使用。 它提供了一個偏移索引來存儲該值。

雙散列技術的公式如下：

(firstHash(key) + i * secondHash(key)) % sizeOfTable

其中 i 是偏移值。 這個偏移值不斷增加，直到找到一個空槽。

例如，您有兩個散列函數：h1 和 h2。 您必須執行以下步驟才能找到空槽：

1. 驗證 hash1(key) 是否為空。 如果是，則將值存儲在此插槽中。
2. 如果 hash1(key) 不為空，則使用 hash2(key) 找到另一個槽。
3. 驗證 hash1(key) + hash2(key) 是否為空。 如果是，則將值存儲在此插槽中。
4. 繼續遞增計數器並重複 hash1(key)+2hash2(key)、hash1(key)+3hash2(key) 等，直到找到一個空槽。

雙散列示例

假設您需要將一些項目存儲在大小為 20 的哈希表中。給出的值是：(16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1)。

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

結論

雙散列的計算成本很高，但它比線性探測方法更快地搜索下一個空閒槽。 文章中給出的示例僅用於說明目的。 您可以根據您的要求修改上面給出的語句。 在這篇博客中，我們了解了數據結構中散列的概念。

你可以試試這個例子來加強你的數據結構知識。 如果您想了解更多關於數據結構的信息，請查看全棧開發課程中的 upGrad Executive PG Program 。 本課程專為在職專業人士而設計，並提供嚴格的培訓和頂級公司的工作安排。