数据结构#

HashMap 的底层由 数组 + 链表/红黑树 组成：

1. 数组（桶数组）：每个元素称为一个 桶（Bucket），初始容量默认为 16。
2. 链表/红黑树：解决哈希冲突的链式结构。
   • 链表：当链表长度 ≤ 8 时，使用链表存储。
   • 红黑树：当链表长度 > 8 且桶数组长度 ≥ 64 时，链表转换为红黑树（时间复杂度从 O(n) 优化为 O(log n)）。

构造函数#

// 默认构造函数。
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
 }

 // 包含另一个“Map”的构造函数
 public HashMap(Map<? extends K, ? extends V> m) {
     this.loadFactor = DEFAULT_LOAD_FACTOR;
     putMapEntries(m, false);//下面会分析到这个方法
 }

 // 指定“容量大小”的构造函数
 public HashMap(int initialCapacity) {
     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }

 // 指定“容量大小”和“负载因子”的构造函数
 public HashMap(int initialCapacity, float loadFactor) {
     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
     if (initialCapacity > MAXIMUM_CAPACITY)
         initialCapacity = MAXIMUM_CAPACITY;
     if (loadFactor <= 0 || Float.isNaN(loadFactor))
         throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
     this.loadFactor = loadFactor;
     // 初始容量暂时存放到 threshold ，在resize中再赋值给 newCap 进行table初始化
     this.threshold = tableSizeFor(initialCapacity);
 }

值得注意的是上述四个构造方法中，都初始化了负载因子 loadFactor，由于 HashMap 中没有 capacity 这样的字段，即使指定了初始化容量 initialCapacity ，也只是通过 tableSizeFor 将其扩容到与 initialCapacity 最接近的 2 的幂次方大小，然后暂时赋值给 threshold ，后续通过 resize 方法将 threshold 赋值给 newCap 进行 table 的初始化。

哈希函数#

HashMap 通过哈希函数将键映射到桶的索引位置：

// JDK 1.8 哈希计算（高位扰动）
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 扰动目的：将哈希码的高位与低位混合，减少哈希冲突。
• 索引计算：index = (n - 1) & hash，其中 n 是桶数组长度。

扩容机制(重点)#

1. 触发条件：当元素数量 > capacity * loadFactor（默认容量 16，负载因子 0.75）。
2. 扩容步骤：
   • 新容量：旧容量 × 2（保证是 2 的幂）。
   • 重新哈希：遍历旧数组，将每个桶中的元素重新分配到新数组的桶中。
     • JDK 1.8 优化：利用哈希值的高位判断元素在新数组的位置（无需重新计算哈希）。
3. 性能影响：扩容是耗时的 O(n) 操作，初始化时合理设置容量可减少扩容次数。

红黑树转换（重点）#

1. 树化条件：
   • 链表长度 ≥ 8。
   • 桶数组长度 ≥ 64（否则优先扩容而非树化）。
2. 退化条件：红黑树节点数 ≤ 6 时，退化为链表。

线程安全性#

• 非线程安全：多线程并发操作可能导致数据不一致或死循环（JDK 1.7 头插法在扩容时可能形成循环链表）。
• 替代方案：
  • ConcurrentHashMap：分段锁或 CAS 实现高并发安全。
  • Collections.synchronizedMap：通过同步方法包装 HashMap。

关键参数#

使用注意事项#

1. 键对象要求：
   • 不可变性：建议使用不可变类（如 String、Integer）作为键，避免修改后哈希值变化。
   • 重写 hashCode() 和 equals()：确保哈希分布均匀和键的唯一性。
2. 性能优化：
   • 预分配容量：预估元素数量，避免频繁扩容。
   • 避免哈希冲突：设计良好的哈希函数。

总结#

1. HashMap 的工作原理？ 答：通过哈希函数计算键的桶位置，使用链表或红黑树解决哈希冲突。
2. HashMap 为什么线程不安全？ 答：并发操作可能导致数据覆盖、扩容死循环（JDK 1.7）或遍历时快速失败。
3. HashMap 和 Hashtable 的区别？ 答：HashMap 允许 null 键值、非线程安全、性能高；Hashtable 相反。
4. 如何减少哈希冲突？ 答：优化键的 hashCode() 方法，合理设置初始容量和负载因子。