雜湊表

雜湊表，又稱為哈希表，是一種廣泛用於資料儲存和檢索的資料結構。它利用哈希函數將鍵映射到特定的索引位置，以實現快速查找和存取相對應的值。雜湊表的主要優勢在於其卓越的查找效率，平均情況下，查找操作的時間複雜度為O(1)。

基本結構

雜湊表通常由多個桶（Bucket）組成，每個桶包含多個槽（Slot），每個槽可以容納一條記錄。當雜湊函數將資料映射到一個已滿的桶時，就會發生碰撞（Collision）。在無碰撞的情況下，雜湊搜索只需要一次讀取，同時也保持高度的保密性，因為如果不知道雜湊函數，則無法讀取資料。此外，雜湊表還可以應用於資料壓縮，將廣泛分佈的鍵映射到有限的表格位置，從而節省記憶體空間。

雜湊表的優勢

• 溢位處理：如果雜湊函數對應的桶已滿，稱為溢位。在無碰撞的情況下，雜湊搜索僅需要一次讀取。

• 高保密性：若不知道雜湊函數，無法讀取資料。

• 資料壓縮：雜湊表可用於資料壓縮，將廣泛分佈的鍵映射到有限的表格位置。

良好的哈希函數特點

優秀的哈希函數需滿足以下特點：

1. 計算簡單：好的雜湊函數應高效計算，確保大量鍵的雜湊操作也能快速完成。

2. 碰撞少：雜湊函數應均勻映射不同的鍵到表格不同位置，減少碰撞的發生。

3. 避免局部偏重：應避免相似前綴的鍵映射到相同位置，以減少群聚問題。

Hashing 基本原理

雜湊函數是這種資料結構的基礎，將鍵映射到索引或數字，這個索引被稱為雜湊碼（Hash Code）。優秀的雜湊函數應均勻地映射鍵到雜湊表的不同位置，減少碰撞。

以下是一些常見的雜湊函數和方法：

• 中位數平方法（Middle Square Method）：將鍵的平方值取中位數，然後將其作為索引。這方法有助於均勻分佈索引位置。

• 除法散列法（Division Hashing）：將鍵除以一選定的數字（通常是表格大小），使用餘數作為索引位置。這是簡單且常見的雜湊函數。

• 摺疊相加法（Folding Addition Method）：將鍵分割成多部分，然後將這些部分相加以生成索引位置。通常用於處理不同長度的鍵。

• 位數值分析法（Digital Analysis Method）：適用於已知鍵的範圍，分析每個鍵的位數，並根據分析生成索引。

概念和方法

雜湊表包括一些重要的概念和方法，包括：

• 碰撞處理（Collision Handling）：當雜湊函數將不同的鍵映射到相同的索引位置時，稱為碰撞。常見處理方法包括鏈接法（Separate Chaining）和開放地址法（Open Addressing）。

• 負載因子（Load Factor）：這是衡量雜湊表容量利用率的指標，通常表示為已儲存的鍵值對數量除以桶的總數。當負載因子超過預定閾值時，雜湊表可能需要調整大小（重新雜湊）以維持查找效率。

• 動態調整大小（Dynamic Resizing）：當雜湊表的負載因子超過某個閾值時，通常會創建一個更大的雜湊表，然後重新雜湊現有的鍵值對以實現更好的性能。這過程稱為動態調整大小。

儘管哈希表提供了極高的查找效率，但在某些情況下，由於哈希碰撞和動態調整大小的成本，它的性能可能會受到影響。因此，在選擇使用哈希表時，需要根據應用程序的需求和特點來權衡考慮。

處理碰撞（Collision）

碰撞處理是在實現雜湊表時必須處理的情況之一，當雜湊函數將不同的鍵映射到相同的索引位置時，即發生碰撞。以下是一些處理碰撞的方法：

• 鏈接法（Separate Chaining）：在這種方法中，雜湊表的每個項目被視為一個鏈結串列的起點，用於存儲具有相同雜湊碼的多個鍵-值對。當碰撞發生時，新的鍵-值對被插入到相應項目的鏈結串列中。這種方法容易實現，且適用於處理碰撞的情況，但可能會產生額外的記憶體消耗。

• 線性探測（Linear Probing）：另一種方法是使用線性探測。在這種方法中，表格的大小是固定的，不需要使用指標。雜湊函數將決定索引值在表格中的位置，如果該位置已經被佔據，則將嘗試放置在其後的第一個空位上。這種方法可以節省記憶體，但可能導致二次碰撞的情況，進而產生群聚問題。為了減輕這種情況，可以考慮使用雙重哈希（Double Hashing）方法，雖然這可能需要更多的計算量。雙重哈希法的主要優勢在於減輕了群聚效應，但需要更多的計算量。

• 開放地址法（Open Addressing）：這種方法中，碰撞的鍵值對被插入到雜湊表的其他位置，而不是鏈結串列。這可以通過不同的方法實現，如線性探測、二次探測和雙重哈希等。

• 再散置（Rehashing）：當雜湊表的容量不足以處理碰撞時，可以創建一個更大的雜湊表，然後重新雜湊現有的鍵值對以實現更好的性能。這個過程稱為動態調整大小。

雜湊表的應用

雜湊表主要用於插入和搜尋操作。其基本思想相當簡單：當資料的索引值介於0到1之間時，儲存是相對簡單的。但如果索引值介於1到M之間，其中M是電腦所能表示的最大索引值，我們可能會面臨分配空間的困難。

舉個例子，假設我們想要為250名學生分配身分證字號，我們無法只使用大小為1的記憶體來儲存所有身分證資訊。即使我們只考慮後三碼，我們仍然需要一個大小為1000的陣列，但在這250名學生中，可能會有相同的後三碼，這將導致所需的記憶體空間增加，同時減低了空間的有效利用率。

因此，我們需要一個稱為雜湊函數的函數，將原本的索引值映射到特定的位置上，這個想法是非常重要的。我們試圖將索引值存儲在表格的特定位置，例如，將1兆映射到大小為1000的集合中，每個索引值將存儲在大小為M的表格中。因為1兆非常大，而1000非常小，所以容易出現多個索引值映射到相同位置的情況，這就是所謂的碰撞。

以上是關於雜湊表的一些基本概念和方法，它們在資料結構和演算法中具有廣泛的應用，用於解決各種資料儲存和檢索的問題。

不論好與壞，都是生活的一部分，都有價值。