線性探測哈希表性能測試實驗報告

1. 實驗目的

• 編程實現線性探測哈希表。
• 編程測試線性探測哈希表。
• 了解線性探測哈希表的性能特征，并運行程序進行驗證。

2. 實驗背景與理論基礎

哈希表是一種高效的數據結構，用于實現符號表（Symbol Table），支持快速的插入、查找和刪除操作。當不同的鍵哈希到同一個地址時，會發生沖突。線性探測（Linear Probing）是一種常見的開放尋址（Open Addressing）沖突解決策略，它通過探測當前位置的下一個連續槽位來尋找空閑位置。

線性探測的性能分析主要關注查找操作所需的平均探測次數。根據教材，當沖突通過線性探測解決時，哈希表大小為 $M$ 且包含 $N=\alpha M$ 個鍵時，其平均探測次數有以下理論近似值（Property 14.3）：

• 查找失敗 (misses) 的平均探測次數：
  $$\frac{1}{2}\left(1+\frac{1}{(1?\alpha {)}^2}\right)$$

其中，$\alpha =N/M$ 是哈希表的負載因子。

此外，查找失敗的平均成本也可以通過分析哈希表中形成的聚簇（clusters）來計算：
$$\text{查找失敗的平均成本}=1+\frac{N}{2M}+\frac{{\sum }_i^k{t}_i^2}{2M}$$
其中，$t_i$ 是插入過程中形成的第 $i$ 個聚簇的長度，總共有 $k$ 個聚簇。

本次實驗將重點關注查找失敗的平均成本。

根據實驗設計，我們將 $N/2$ 個隨機整數插入到大小為 $N$ 的哈希表中，因此負載因子 $\alpha =(N/2)/N=0.5$。代入查找失敗的理論公式，可計算出在此負載因子下的理論平均成本：
$$\text{理論平均成本}=\frac{1}{2}\left(1+\frac{1}{(1?0.5{)}^2}\right)=2.5$$
因此，對于本次實驗中的所有測試用例，理論上的查找失敗平均成本應為 2.5 次探測。

3. 實驗設計與實現

實驗任務： 編寫程序實現 Exercise 14.28，即插入 $N/2$ 個隨機整數到大小為 $N$ 的哈希表中，并計算查找失敗的平均成本。

Exercise1428

程序實現

1. 哈希表結構： 使用數組 st 作為哈希表，存儲 Item 指針。Item 包含 Key 和 Value。
2. 初始化 (STinit)： 根據傳入的最大元素數量 max，將哈希表大小 M 設置為 2 * max。由于實驗要求插入 $N/2$ 個元素到大小為 $N$ 的表，所以 M 在這里對應練習題中的 $N$。
3. 哈希函數 (hash)： 采用簡單的整數哈希函數 (11 * x) % M。
4. 插入 (STinsert)： 采用線性探測解決沖突。如果初始哈希位置被占用，則向右（索引遞增）探測直到找到空槽位。
5. 簇分析 (analyze_clusters)：
   • 遍歷哈希表，識別所有形成的聚簇。一個聚簇被定義為連續的被占用槽位序列。
   • 計算每個聚簇的長度 $t_i$。
   • 累加所有聚簇長度的平方和 $\sum t_i^2$。
   • 根據公式 $1+\frac{N}{2M}+\frac{{\sum }_i^k{t}_i^2}{2M}$ 計算出基于簇長度的查找失敗平均成本（即實驗值 average_cost）。
   • 同時，根據負載因子 $\alpha =N/M$ 和 Property 14.3 的公式計算理論平均成本（theory_cost）。
   • 打印實驗值和理論值以便對比。
6. 測試用例： 設計了四組測試，分別對應 $N=10^3,10^4,10^5,10^6$。在每個測試中，向表中插入 $N/2$ 個隨機整數。
   • test_insert_1000(): M=1000, 插入 500 個隨機數。
   • test_insert_10000(): M=10000, 插入 5000 個隨機數。
   • test_insert_100000(): M=100000, 插入 50000 個隨機數。
   • test_insert_1000000(): M=1000000, 插入 500000 個隨機數。
7. 隨機數生成： 使用 srand(time(NULL)) 進行隨機數播種，以確保每次程序運行生成不同的隨機序列。

4. 實驗結果

程序運行后，得到以下輸出：

Table(M=1000):the average cost of unsuccessful search in that table is 1.558000, theory cost: 2.500000
Table(M=10000):the average cost of unsuccessful search in that table is 2.488200, theory cost: 2.500000
Table(M=100000):the average cost of unsuccessful search in that table is 2.481630, theory cost: 2.500000
Table(M=1000000):the average cost of unsuccessful search in that table is 2.503940, theory cost: 2.500000

5. 結果分析

這些結果清晰地展示了線性探測哈希表在不同規模下，查找失敗平均成本的實驗值與理論值之間的關系。

1. M=1000 (表大小為 1000，插入 500 個元素)：

   • 實驗平均成本為 1.558000，而理論平均成本為 2.500000。
   • 分析： 在這種較小規模的哈希表中，實驗結果與理論值存在較明顯的偏差。這是因為理論平均值是基于大量隨機插入的統計結果，而單次運行（尤其在數據量較小的情況下）可能因隨機數的具體序列偶然地形成了比平均情況更少或更短的簇，從而導致實際觀察到的探測次數低于理論預測。這反映了小樣本量下的統計波動性。

2. M=10000 (表大小為 10000，插入 5000 個元素)：

   • 實驗平均成本為 2.488200，理論平均成本為 2.500000。
   • 分析： 實驗結果與理論值已非常接近。這表明隨著哈希表規模的增大（以及插入元素數量的增加），線性探測在隨機插入下的實際行為開始向其統計平均值收斂。隨機性帶來的局部波動效應被更大量的數據所平均。

3. M=100000 (表大小為 100000，插入 50000 個元素)：

   • 實驗平均成本為 2.481630，理論平均成本為 2.500000。
   • 分析： 實驗結果繼續保持與理論值的高度吻合，進一步證實了這種收斂性。

4. M=1000000 (表大小為 1000000，插入 500000 個元素)：

   • 實驗平均成本為 2.503940，理論平均成本為 2.500000。
   • 分析： 實驗結果與理論值幾乎完全一致，僅存在微小的正常波動。這完美地展示了當數據量足夠大時，線性探測在半滿情況下的性能是如何精確符合理論模型的。

6. 結論

該程序 Exercise1428 的運行結果有力地驗證了以下幾點：

• 理論公式的有效性： 教材中關于線性探測查找失敗平均成本的理論公式 (Property 14.3) 在實踐中是準確的預測器。通過實驗結果與理論值的對比，可以清晰地看到二者的高度吻合，尤其是在大規模數據量下。
• 規模效應： 隨著哈希表規模的增大，線性探測在隨機插入條件下的實際性能會越來越接近其理論平均值。小規模表的結果可能因隨機性而有較大波動，但隨著 $N$ 的增長，這種波動逐漸減小。
• 線性探測的特性： 即使在負載因子為 $0.5$（即哈希表半滿）這種相對較低的情況下，查找失敗的平均成本也不是理想的 $1$ 次探測，而是大約 $2.5$ 次。這反映了線性探測固有的“初級聚簇”（primary clustering）問題：即使表不滿，連續的占用槽位也會導致查找路徑變長，從而產生額外的探測成本。這也解釋了為什么在線性探測中，通常建議將負載因子保持在更低的水平（例如，遠小于 0.5），以避免性能隨著表接近滿而急劇下降。

本次實驗成功地編程實現了線性探測哈希表，并通過對比實驗結果與理論預測，加深了對線性探測性能特征及其“初級聚簇”問題的理解。