1. 基本概念

• 定義：通過鍵（Key）直接訪問值（Value）的數據結構，基于哈希函數將鍵映射到存儲位置。

• 核心操作：

  • put(key, value)：插入鍵值對

  • get(key)：獲取鍵對應的值

  • remove(key)：刪除鍵值對

• 時間復雜度（平均）：

  • 插入、查找、刪除：O(1)

  • 最壞情況（哈希沖突嚴重時）：O(n)

---

2. 哈希函數設計

• 作用：將任意大小的鍵轉換為固定大小的哈希值（通常為整數）。

• 設計要求：

  • 一致性：相同鍵必須產生相同哈希值

  • 均勻性：不同鍵應均勻分布，減少沖突

• 常見哈希函數：

  // Java的String.hashCode()實現
  public int hashCode() {int h = 0;for (char c : value) {h = 31 * h + c;}return h;
  }

---

3. 哈希沖突解決

當不同鍵映射到同一位置時：

• 鏈地址法（Separate Chaining）：

  • 每個桶（bucket）存儲鏈表或紅黑樹（如Java 8+的HashMap）

  • 沖突時，新元素添加到鏈表末尾

• 開放尋址法：

  • 線性探測：沖突后順序查找下一個空槽

  • 平方探測：按平方步長跳躍查找

---

4. 負載因子與擴容

• 負載因子（Load Factor）：

  • 定義：元素數量 / 桶數量（默認0.75）

  • 作用：觸發擴容的閾值（如Java HashMap）

• 擴容機制：

  • 新容量通常為原來的2倍

  • 重新計算所有鍵的哈希位置（rehash）

---

5. 常見實現對比

	HashMap	Hashtable	ConcurrentHashMap
線程安全	不安全	安全（全表鎖）	安全（分段鎖）
Null鍵值	允許	不允許	不允許
性能	高	低	中等

---

6. Java中的關鍵實現細節

• HashMap的樹化優化：

  • 當鏈表長度≥8且桶數量≥64時，鏈表轉為紅黑樹（防止DoS攻擊）

• 哈希擾動函數：

  
  static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  • 通過異或高位和低位，減少哈希沖突

---

7. 經典應用場景

1. 快速查找：

   • 如兩數之和（LeetCode 1）

   
   // 兩數之和解法
   Map<Integer, Integer> map = new HashMap<>();
   for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{map.get(complement), i};}map.put(nums[i], i);
   }

2. 緩存實現（如LRU Cache）

3. 去重統計（如統計詞頻）

---

8. 常見面試問題

• Q1：HashMap如何解決哈希沖突？
  A：鏈地址法（鏈表+紅黑樹）。

• Q2：為什么負載因子默認是0.75？
  A：空間和時間成本的折中（數學證明較優）。

• Q3：HashMap為什么線程不安全？
  A：多線程擴容可能導致死循環或數據丟失。

---

9. 手寫簡易Hashtable（Java示例）

class MyHashtable<K, V> {private Node<K,V>[] table;private int size;private static final int DEFAULT_CAPACITY = 16;static class Node<K,V> {final K key;V value;Node<K,V> next;// 構造方法...}public V put(K key, V value) {int hash = key.hashCode();int index = (table.length - 1) & hash;Node<K,V> node = table[index];while (node != null) {if (node.key.equals(key)) {V oldValue = node.value;node.value = value;return oldValue;}node = node.next;}Node<K,V> newNode = new Node<>(key, value, table[index]);table[index] = newNode;size++;return null;}
}

---

掌握這些核心知識點后，你就能在面試和實際開發中游刃有余地使用哈希表！