⭐ 题目日期：

字节 - 2024/12/16

📝 题解：

HashMap 是 Java 中基于哈希表实现的键值对集合，其核心原理和实现细节如下：

---

1. 数据结构

• 数组 + 链表/红黑树
  • 默认数组（桶）初始容量为 16，每个桶存储链表或红黑树。
  • 当链表长度超过 8 且数组容量 ≥ 64 时，链表转换为红黑树（查询复杂度从 O(n) 优化为 O(log n)）。
  • 当红黑树节点数 ≤ 6 时，退化为链表。

---

2. 哈希计算

• 索引定位
  • 通过 (n - 1) & hash 计算键的索引（n 为数组长度，必须为 2 的幂）。
  • 哈希值通过 key.hashCode() 的高 16 位与低 16 位异或（^）得到，以降低冲突概率。

---

3. 冲突解决

• 拉链法
  • 冲突的键值对以链表或红黑树形式存储在同一个桶中。

---

4. 扩容机制

• 触发条件
  • 当元素数量超过 容量 × 负载因子（默认 0.75）时，数组扩容为原大小的 2 倍。
• 优化策略
  • 扩容时，节点在新数组中的位置为 原位置 或 原位置 + 原容量（通过高位掩码快速判断，无需重新计算哈希）。

---

5. 操作流程

• put(key, value)
  1. 计算键的哈希值和索引。
  2. 若桶为空，直接插入新节点。
  3. 若桶非空，遍历链表/树：
     • 存在相同键：更新值。
     • 不存在：插入新节点，触发树化或扩容检查。
• get(key)
  1. 计算哈希值和索引。
  2. 遍历链表/树查找键对应的值。

---

6. 线程安全性

• 非线程安全
  • 多线程操作可能导致数据不一致或死循环（如并发扩容时）。推荐使用 ConcurrentHashMap 或 Collections.synchronizedMap。

---

7. 关键设计

• 容量为 2 的幂
  • 保证 (n - 1) & hash 均匀分布，等价于取模运算但更高效。
• 树化阈值
  • 平衡链表和红黑树的性能与内存开销。

---

示例代码片段（简化版）

// Node 结构（链表节点）
static class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

// 插入逻辑（简化）
V put(K key, V value) {
    int hash = hash(key);
    int index = (n - 1) & hash;
    if (table[index] == null) {
        table[index] = newNode(hash, key, value);
    } else {
        // 遍历链表/树处理冲突
    }
    // 检查扩容...
}

---

总结

HashMap 通过哈希函数、动态扩容、链表与红黑树结合的方式，在时间和空间效率间取得平衡。其核心优化点包括：

1. 位运算替代取模：提升索引计算效率。
2. 高低位异或：减少哈希冲突。
3. 树化策略：应对极端哈希冲突场景。
4. 扩容优化：减少哈希重计算次数。