以下是關於 HashMap 的常見面試題及其答案整理，涵蓋底層原理、使用場景和優化技巧

1. HashMap 的底層數據結構是什麼？

• 答案：
  JDK 1.8 之前：數組 + 鏈表（鏈表解決哈希衝突）。
  JDK 1.8 及之後：數組 + 鏈表/紅黑樹（當鏈表長度 ≥8 且數組長度 ≥64 時，鏈表轉為紅黑樹，提高查詢效率）。

2. HashMap 的工作原理（put/get 過程）？

put 過程：

1. 計算鍵的哈希值：hash(key) = (key == null) ? 0 : key.hashCode() ^ (hashCode >>> 16)（擾動函數減少哈希衝突）。
2. 根據哈希值確定數組下標：index = (n - 1) & hash（n 為數組長度）。

3. 若該位置為空，直接插入鍵值對；否則遍歷鏈表/紅黑樹：

   • 若鍵已存在，更新值；
   • 若鍵不存在，插入到鏈表尾部（或紅黑樹）。
4. 插入後判斷是否需要擴容。

get 過程：

1. 計算鍵的哈希值，確定數組下標。
2. 遍歷鏈表/紅黑樹，通過 equals() 方法匹配鍵，返回對應的值。

3. 為什麼 HashMap 線程不安全？

• 原因：

  • 多線程擴容：擴容時鏈表可能形成環形結構，導致 get() 死循環（JDK 1.7 問題，1.8 已優化）。
  • 數據覆蓋：多線程同時插入且哈希衝突時，可能覆蓋已存在的鍵值對。
  • 可見性問題：未使用同步機制，修改對其他線程不可見。

4. HashMap 的哈希衝突如何解決？

• 拉鍊法（鏈地址法）：將衝突的鍵值對存儲在鏈表或紅黑樹中。
• 開放尋址法：HashMap 未使用，但其他類（如 ThreadLocal）可能採用。

5. 為什麼鏈表長度超過 8 會轉為紅黑樹？

• 設計依據：根據泊松分佈，哈希衝突時鏈表長度達到 8 的概率極低（約 1/千萬次），此時轉為紅黑樹可平衡查詢效率與樹化成本。
• 退化條件：當紅黑樹節點數 ≤6 時，退化為鏈表。

6. HashMap 的初始容量、負載因子與擴容機制？

• 默認初始容量：16。
• 負載因子（Load Factor）：默認 0.75（平衡時間與空間開銷）。
• 擴容條件：當元素數量 > 容量 × 負載因子時，擴容為原來的 2 倍。

• 擴容過程：

  1. 創建新數組（容量翻倍）。
  2. 重新計算鍵的哈希並分配到新位置（JDK 1.8 優化：鏈表節點保持原順序，避免環形鏈表）。

7. HashMap 允許鍵/值為 null，而 ConcurrentHashMap 不允許？

• HashMap：設計為單線程使用，允許 null 鍵值簡化代碼邏輯（例如表示“無值”）。
• ConcurrentHashMap：多線程場景下，null 可能導致歧義（無法區分“鍵不存在”和“鍵存在但值為 null”）。

8. HashMap 與 Hashtable 的區別？

9. 如何設計一個高效的鍵類型（如自定義對象作為 Key）？

• 重寫 hashCode() 和 equals()：確保哈希分佈均勻且相等對象返回相同哈希。

• 示例：

  @Override
  public int hashCode() {
      return Objects.hash(id, name); // 使用工具類生成複合哈希
  }
  
  @Override
  public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null || getClass() != obj.getClass()) return false;
      MyKey other = (MyKey) obj;
      return id == other.id && Objects.equals(name, other.name);
  }

10. 如何解決 HashMap 的多線程問題？

• 方案：

  1. 使用 ConcurrentHashMap：分段鎖（JDK 1.7）或 CAS + synchronized（JDK 1.8+）。
  2. Collections.synchronizedMap()：包裝 HashMap，但性能較低。
  3. 避免在多線程中直接操作 HashMap。

11. HashMap 的遍歷方式有哪些？

• EntrySet 遍歷：效率最高（直接獲取鍵值對）。

  for (Map.Entry<String, Integer> entry : map.entrySet()) {
      String key = entry.getKey();
      int value = entry.getValue();
  }

• KeySet 遍歷：需額外調用 get()，可能觸發多次哈希計算。

• Lambda 表達式（Java 8+）：

  map.forEach((k, v) -> System.out.println(k + ": " + v));

總結

1. 數據結構與紅黑樹轉換。
2. 哈希衝突解決與擴容機制。
3. 線程安全與替代方案。
4. hashCode() 與 equals() 的設計。
5. JDK 1.7 與 1.8 的差異（如頭插法改尾插法、樹化優化）。