學習資源

https://labuladong.online/algo/data-structure-basic/hashtable-chaining/

學習記錄

今天是學習的第 13 天，主要學習了用拉鏈法實現哈希表：

哈希衝突

在上一個單元苦痛之路 Day 13 - 哈希表核心原理中，我們有提到當發生哈希衝突時，有兩種常見的解決方案：

1. 拉鏈法
   • 原理：陣列中每個位置存放一個鏈表
   • 衝突處理：多個 key-value 對存儲在同一個鏈表中
   • 查找過程：計算索引後遍歷對應鏈表
   • 時間複雜度：最壞情況 O(K)，K 為鏈表長度
2. 線性探查法（開放尋址法）
   • 原理：發現衝突時，依序檢查下一個位置
   • 衝突處理：從 index + 1 開始尋找空位置
   • 查找過程：需要連續探查直到找到目標或空位置
   • 時間複雜度：最壞情況 O(K)，K 為連續探查次數

拉鏈法的基本思想是：當多個鍵值經過哈希函數計算後得到相同的索引時，將這些鍵值對儲存在同一個位置的鏈表中。

實現原理

資料結構設計

• 底層使用陣列作為哈希表的主體
• 陣列中每個位置存儲一個鏈表
• 鏈表節點包含完整的鍵值對（key-value）

[[KVnode], [KVNode], ..., [KVNode]]

核心操作邏輯

1. 查詢：通過哈希函式定位到陣列索引，然後遍歷該位置的鏈表找到目標鍵
2. 插入：先檢查鍵是否已存在（更新值），否則在鏈表末尾添加新節點
3. 刪除：定位到對應鏈表後，遍歷找到目標節點並移除

重要技術點

哈希函式設計

• 簡化版本使用取模運算：hash(key) = key % table.length

hash(key) {
    return key % this.table.length;
}

• 完整版本結合 hashCode 方法，提供更好的分佈均勻性

hash(key) {
    return Math.abs((key.hashCode ? key.hashCode() : this.defaultHash(key)) % this.table.length);
}

動態擴縮容機制

• 負載因子達到 0.75 時進行擴容

// 如果元素數量超過了負載因子，進行擴容
if (this.size >= this.table.length * 0.75) {
    this.resize(this.table.length * 2);
}

• 負載因子低於 0.125 時進行縮容

// 當負載因子小於 0.125 時，進行縮容
if (this.size <= this.table.length / 8) {
    this.resize(Math.floor(this.table.length / 4));
}

• 擴縮容時需要重新計算所有元素的位置

學習總結

• 拉鏈法的原理是陣列中每個位置存放一個鏈表，鏈表節點包含完整的鍵值對（key-value）
• 哈希函式使用 hashCode 方法，提供更好的分佈均勻性
• 負載因子達到 0.75 時進行擴容；負載因子低於 0.125 時進行縮容