HashMap底层实现原理

HashMap是Java中最常用的集合类之一，理解其底层实现原理对于Java开发者至关重要。

核心问题

HashMap的底层数据结构是什么？

HashMap在JDK 1.8之前使用数组+链表的结构，在JDK 1.8及之后使用数组+链表+红黑树的结构。

为什么JDK 1.8引入红黑树？

当链表长度超过8时，会将链表转换为红黑树，以提高查找效率。红黑树的时间复杂度为O(log n)，而链表的查找时间复杂度为O(n)。

HashMap的扩容机制

当HashMap中的元素数量超过容量 × 负载因子（默认0.75）时，会触发扩容。扩容会将数组大小扩大为原来的2倍，并重新计算所有元素的位置（rehash）。

关键实现细节

1. 哈希函数

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

2. 数组索引计算

int index = (n - 1) & hash;

3. 链表转红黑树的条件

• 链表长度 >= 8
• 数组长度 >= 64

常见面试题

1. HashMap为什么线程不安全？

   • 多线程环境下可能导致数据丢失
   • 扩容时可能形成环形链表
   • 使用ConcurrentHashMap解决线程安全问题

2. HashMap的负载因子为什么是0.75？

   • 平衡时间和空间复杂度
   • 0.75是经过大量实验得出的最优值

3. 为什么使用红黑树而不是AVL树？

   • 红黑树的旋转操作更少，插入和删除性能更好
   • 红黑树对平衡性的要求更宽松

性能优化建议

• 合理设置初始容量，避免频繁扩容
• 选择合适的负载因子
• 使用String作为key时，注意hashCode的实现