面试题：Java HashMap哈希算法的优化点分析

Question

在Java的HashMap中，哈希算法做了哪些优化来减少哈希冲突，提高存储和查找效率？请详细说明这些优化措施及其背后的原理。

Answer 1

优化措施及原理

1. 扰动函数（哈希值计算优化）
   • 措施：在JDK 1.8之前，HashMap通过hash()方法对键的哈希码进行扰动处理。在JDK 1.8及之后，简化为(h = key.hashCode()) ^ (h >>> 16)。这里将哈希码的高16位与低16位进行异或运算。
   • 原理：因为在计算数组索引时，使用的是(n - 1) & hash（n为数组长度），主要是低位起作用。通过这种扰动，将高位的特征也混合到低位中，使得哈希值更均匀地分布，减少哈希冲突，例如不同哈希码高位不同但低位相同的键，经过扰动后能分散到不同桶中。
2. 负载因子与扩容机制
   • 措施：HashMap默认负载因子为0.75，当哈希表中的键值对数量达到capacity * loadFactor（capacity为当前哈希表容量）时，就会进行扩容，新容量为原来的2倍。
   • 原理：负载因子是一个权衡空间和时间效率的参数。如果负载因子设置过大，哈希表利用率高但哈希冲突的概率增加，查找效率降低；如果设置过小，虽然哈希冲突减少，但空间利用率低。扩容机制则是在哈希冲突可能影响性能时，通过扩大数组容量来重新分配键值对，降低冲突概率，提高存储和查找效率。
3. 链表转红黑树
   • 措施：在JDK 1.8中，当链表长度大于等于8且哈希表容量大于等于64时，链表会转化为红黑树存储；当红黑树节点数小于等于6时，又会退化为链表。
   • 原理：链表在长度较短时，插入和查询的时间复杂度为O(n)。随着链表长度增加，查找效率会显著降低。红黑树是一种自平衡二叉查找树，插入、删除和查找的平均时间复杂度为O(log n)，将长链表转换为红黑树能在链表长度较大时提高查找效率，减少哈希冲突带来的性能损耗。