HashMap 核心原理深度剖析：哈希索引、鍵變更陷阱與自定義 Key 最佳實踐

經典面試題：Key 修改屬性後能否取值？

public class Person {
  private String name;
  public Person(String name) { this.name = name; }
  // 缺少 equals() 與 hashCode() 重寫
}

Map<Person, String> map = new HashMap<>();
map.put(new Person("hello"), "world");
map.get(new Person("hello")); // 返回 null！

原因：Person 未重寫 hashCode()，繼承 Object 實作 (基於記憶體位址)。兩個 new Person("hello") 是不同物件，哈希碼不同，落入不同桶位，導致查找失敗。

HashMap 底層資料結構

簡化版實作原理 (參考 Thinking in Java)

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
  static final int SIZE = 997; // 質數減少衝突
  LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];

  public V put(K key, V value) {
    int index = Math.abs(key.hashCode()) % SIZE;
    if (buckets[index] == null) buckets[index] = new LinkedList<>();
    // 遍歷鏈表尋找 key.equals() 相同節點，找到則替換，否則新增
  }

  public V get(Object key) {
    int index = Math.abs(key.hashCode()) % SIZE;
    if (buckets[index] == null) return null;
    // 遍歷鏈表比對 key.equals()
  }
}

核心結構：陣列 + 鏈表 (JDK 8+ 高頻桶位轉紅黑樹)。

JDK 實際實作關鍵點

transient Entry<K,V>[] table; // 必須是 2 的冪次
static class Entry<K,V> implements Map.Entry<K,V> {
  final K key; V value; Entry<K,V> next; int hash; // 緩存 hash 值
}

• table.length 為 2 的冪，索引計算用位運算 (n - 1) & hash 替代取模，效能更高
• hash() 方法對 key.hashCode() 二次攪拌 (高 16 位參與)，減少劣質 hashCode 導致的衝突
• 扩容門檻 loadFactor * capacity (預設 0.75)，擴容為 2 倍並重新計算索引

get() 核心流程源碼解析

public V get(Object key) {
  if (key == null) return getForNullKey(); // null key 固定放 table[0]
  Entry<K,V> entry = getEntry(key);
  return entry == null ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
  if (size == 0) return null;
  int hash = (key == null) ? 0 : hash(key); // 二次攪拌後的 hash
  for (Entry<K,V> e = table[indexFor(hash, table.length)];
       e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
      return e;
  }
  return null;
}

判斷相同鍵的條件：hash 相等 且 (同一物件引用 或 equals() 返回 true)。

public class Person {
  private String name;
  private int age;

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age && Objects.equals(name, person.name);
  }

  @Override
  public int hashCode() {
    return Objects.hash(name, age); // JDK 7+ 工具方法
  }
}