【Java面试】讲讲HashMap的常用方法，以及底层实现？

1. 底层数据结构

• 数组+链表+红黑树（JDK 1.8+）：
  • 数组（Node[] table）存储桶（bucket），每个桶是链表或红黑树的头节点。
  • 链表解决哈希冲突，当链表长度 ≥ 8 且数组容量 ≥ 64 时转为红黑树（查找复杂度从O(n)优化到O(log n)）。

2. 核心方法原理

• put()流程：

  1. 计算键的哈希值（hash(key)），通过扰动函数（高16位异或低16位）减少冲突。
  2. 定位桶位置：index = (n - 1) & hash。
  3. 若桶为空直接插入；若冲突则遍历链表/红黑树：
     • 相同key：覆盖旧值；
     • 不同key：尾插法（JDK 1.8）或树化（链表长度 ≥ 8）。
  4. 扩容条件：元素数 > 容量 × 负载因子（默认0.75）。

• get()流程：通过哈希值定位桶，遍历链表/红黑树，用equals()匹配key。

3. 扩容机制

• 容量翻倍：新建2倍数组，重新哈希迁移数据（JDK 1.8优化：仅需判断高位哈希位，减少重新计算）。
• 线程不安全问题：多线程扩容可能导致死循环（JDK 1.7头插法）或数据丢失。

4. 线程安全与替代方案

• 非线程安全：多线程操作需使用ConcurrentHashMap（分段锁/CAS）或Collections.synchronizedMap。

5. 关键参数与优化

• 初始容量：默认16，建议预估设置以减少扩容开销。
• 哈希冲突优化：重写hashCode()和equals()确保键对象分布均匀。

6. 与其他Map对比

特性	HashMap	LinkedHashMap	TreeMap
顺序性	无序	插入/访问顺序	键的自然/自定义排序
线程安全	否	否	否
适用场景	高频增删查	需保留插入顺序	需排序或范围查询

---

总结：HashMap通过哈希表实现高效查询（平均O(1)），但需注意哈希冲突、扩容成本及线程安全问题。JDK 1.8引入红黑树优化极端情况性能，适用于单线程高频操作场景。