一、哈希表是什麼？¶
想象一下，你在圖書館找一本書，管理員會告訴你這本書的“索書號”，你直接根據索書號就能定位到書架（類似“數組位置”），不需要一本本翻找。哈希表的作用和這完全一樣：通過一個“鑰匙”（哈希函數）快速找到數據的“位置”（數組索引），讓查找、插入、刪除操作變得非常高效。
簡單來說，哈希表是一種鍵值對（key-value） 存儲結構，它用一個“哈希函數”把“鍵”（比如學號、姓名）轉換成數組的索引，然後把“值”（比如成績、電話號碼）存在對應的數組位置。
二、哈希表如何存儲數據？¶
1. 哈希表的核心結構¶
哈希表的底層是一個數組，數組的每個位置稱爲“桶”（bucket）。每個桶可以存儲一個值，當發生衝突時，可能會在桶裏存多個值（取決於衝突解決方法）。
2. 存儲步驟：鑰匙→位置→存值¶
- 確定鍵值對：比如要存儲學生信息：
學號=123，成績=90。 - 計算哈希值：用“哈希函數”把鍵轉換成數組索引。最簡單的哈希函數是
哈希值 = 鍵 % 數組長度（比如數組長度爲10，123 % 10 = 3，所以哈希值是3）。 - 存入數組：把“值”存在哈希值對應的數組位置（即第3個桶）。
示例：用哈希表存3個學生成績¶
假設數組長度爲10（桶編號0~9），哈希函數爲 鍵 % 10：
- 學生A：學號12 → 哈希值 12%10=2 → 數組[2]存成績85。
- 學生B：學號23 → 哈希值 23%10=3 → 數組[3]存成績76。
- 學生C：學號34 → 哈希值 34%10=4 → 數組[4]存成績92。
此時數組狀態：[ , ,85,76,92, , , , , ]（空位置用逗號分隔）。
查詢時，直接用學號計算哈希值（比如查學號12，哈希值2），直接訪問數組[2]就能得到成績85，無需遍歷整個數組！
三、什麼是衝突？¶
當兩個不同的鍵通過哈希函數計算出相同的哈希值時，就會發生衝突。比如：
- 學號12和學號22，數組長度10，哈希函數%10：12%10=2，22%10=2。
此時，兩個學生要存在數組[2]，但數組位置只有一個，就衝突了！
四、衝突解決方法（圖解）¶
衝突是哈希表的“攔路虎”，但有兩種經典方法解決：鏈地址法（拉鍊法） 和 開放定址法（線性探測）。
方法1：鏈地址法（拉鍊法）¶
原理：數組的每個桶是一個鏈表的“頭節點”，衝突的元素直接掛在對應鏈表的尾部。
示例：繼續存儲學號22（成績70），此時數組[2]已有85，發生衝突：
- 數組[2]變成鏈表：85 → 70（學生A的成績掛在鏈表頭，學生E的成績掛在尾部）。
- 其他學生繼續存入各自的哈希值對應的桶。
鏈地址法示意圖（文字模擬）：
數組索引 → 桶 → 鏈表（衝突元素）
0 → []
1 → []
2 → [85] → [70] （學號12和22衝突，都存在鏈表中）
3 → [76] （學號23）
4 → [92] （學號34）
...
優點：實現簡單，插入/刪除方便，無聚集問題。
缺點：需要額外鏈表空間，適合初學者理解。
方法2：開放定址法（線性探測）¶
原理：衝突時，按順序“探測”下一個空桶。線性探測的規則是：衝突位置h→h+1→h+2→…，直到找到空桶。
示例：數組長度10，存儲學號12（85）和22（70）：
- 學號12：哈希值2 → 數組[2]爲空，存85。
- 學號22：哈希值2 → 數組[2]被佔，探測h+1=3（空），存70。
線性探測示意圖（文字模擬表格）：
| 數組位置 | 0 | 1 | 2 | 3 | 4 | … |
|----------|—|—|—|—|—|-----|
| 狀態 | | | 85 | 70 | 92 | … |
優點：無需額外數據結構，純數組操作。
缺點：可能形成“聚集”（連續空桶被佔用），影響效率。
五、總結¶
哈希表通過哈希函數將鍵映射到數組位置，實現了O(1)級別的快速操作。衝突不可避免，但通過鏈地址法（拉鍊法）或開放定址法（線性探測）可解決。
- 鏈地址法更直觀，適合初學者，衝突元素用鏈表串聯；
- 線性探測用數組自身空間解決衝突，簡單但需注意聚集問題。
掌握哈希表的核心是理解“哈希函數→衝突→解決方法”的邏輯，這是後續學習更復雜數據結構的基礎！