JAVA 中的 HashMap 工作原理

‌1. 底层数据结构‌

• ‌数组 + 链表/红黑树‌：
  HashMap 内部维护一个 ‌桶数组（Node[] table）‌，每个桶（Bucket）存储链表或红黑树的头节点。

  transient Node<K,V>[] table; // 桶数组
  static class Node<K,V> implements Map.Entry<K,V> {
      final int hash;    // 键的哈希值
      final K key;
      V value;
      Node<K,V> next;    // 链表指针
  }
  

  • ‌链表‌：哈希冲突时，冲突的键值对以链表形式存储。
  • ‌红黑树‌（JDK 8+）：当链表长度超过 ‌8‌ 时，链表转换为红黑树（优化查询效率）；当节点数减少到 ‌6‌ 时，树退化为链表。

‌2. 哈希计算与索引定位‌

• ‌哈希扰动‌：
  对键的 hashCode() 进行二次哈希（高16位异或低16位），以减少哈希碰撞概率。

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

• ‌定位桶索引‌：
  根据哈希值计算桶的位置，公式为 hash & (table.length - 1)（要求 table.length 为 2 的幂）。

‌3. 插入键值对（put(K key, V value)）‌

1. ‌计算哈希值‌：调用 hash(key) 获取哈希值。
2. ‌定位桶索引‌：通过哈希值确定键值对应存储的桶。
3. ‌处理冲突‌：
   • ‌桶为空‌：直接创建新节点存入桶中。
   • ‌桶非空‌：遍历链表或树，检查是否存在相同键（equals() 判断）：
     • ‌存在‌：更新值。
     • ‌不存在‌：插入新节点到链表/树末尾。
4. ‌树化检查‌：若链表长度 ≥8，则转换为红黑树。
5. ‌扩容检查‌：若元素总数 ≥ 容量 × 负载因子，触发扩容。

‌4. 查找值（get(Object key)）‌

1. ‌计算哈希值‌：同 put() 方法。
2. ‌定位桶索引‌：找到对应桶。
3. ‌遍历链表/树‌：通过 equals() 方法匹配键，返回对应值。若未找到，返回 null。

‌5. 删除键值对（remove(Object key)）‌

1. ‌定位桶和节点‌：类似 get() 过程找到目标节点。
2. ‌移除节点‌：若为链表节点，调整链表指针；若为树节点，调整树结构。
3. ‌退化检查‌：若树节点数 ≤6，退化为链表。

‌6. 扩容机制（Rehashing）‌

• ‌触发条件‌：当元素数量 ≥ 容量 × 负载因子（默认容量 16，负载因子 0.75）。
• ‌扩容过程‌：
  1. 新容量为旧容量的 ‌2 倍‌（保证为 2 的幂）。
  2. 遍历所有节点，重新计算索引 hash & (newCapacity - 1)。
  3. 数据迁移到新桶数组。
• ‌优化设计‌：
  • 扩容后节点的新位置为 ‌原位置‌ 或 ‌原位置 + 旧容量‌（利用哈希值的高位特征）。
  • 避免全量重新哈希，提升效率。

‌7. 关键参数与性能‌

• ‌时间复杂度‌（平均情况）：
  • 插入、删除、查找：‌O(1)‌
  • 最坏情况（全冲突）：链表 O(n)，红黑树 O(log n)。

‌8. 处理 null 键‌

• HashMap 允许 ‌一个 null 键‌，其哈希值固定为 0，存储在索引 0 的桶中。
• 查找时，需显式检查 key == null 的情况。

‌9. 线程安全问题‌

• ‌非线程安全‌：多线程并发修改可能导致数据不一致或死循环（JDK 7 及之前扩容时链表反转导致）。
• ‌解决方案‌：使用 ConcurrentHashMap 或 Collections.synchronizedMap()。

‌10. 示例代码‌

HashMap<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 5);

// 查找
System.out.println(map.get("Apple")); // 输出 10

// 删除
map.remove("Banana");

‌总结‌

HashMap 的高效性源于：

1. ‌哈希算法优化‌：扰动函数减少哈希冲突。
2. ‌动态扩容‌：平衡空间占用与操作效率。
3. ‌冲突处理‌：链表与红黑树的灵活切换。
4. ‌设计取舍‌：通过负载因子和树化阈值优化不同场景下的性能。