面试题：Java中HashMap哈希算法的基本原理是什么

Question

请简述Java中HashMap的哈希算法基本原理，包括如何计算哈希值以及如何处理哈希冲突。

Answer 1

哈希算法基本原理

1. 计算哈希值：
   • 在Java 8及之前，HashMap中计算哈希值主要通过key的hashCode方法，然后对hashCode进行一系列位运算。例如：

   static final int hash(Object key) {
       int h;
       return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
       // 如果key为null，哈希值为0；否则，将key的hashCode与它右移16位的值进行异或运算
   }
   

   • 在Java 8中这样做是为了让哈希值更分散，结合了高位和低位的特征，减少哈希冲突。
2. 处理哈希冲突：
   • 链地址法：HashMap使用数组加链表（Java 8开始当链表长度超过8且数组长度大于等于64时会转换为红黑树）的方式来处理哈希冲突。
   • 当计算出的哈希值确定了数组的索引位置后，如果该位置已经有元素（即发生了哈希冲突），新元素会以链表节点的形式插入到该位置的链表头部（Java 8之前）或尾部（Java 8开始）。如果链表长度达到一定阈值（默认为8），并且数组长度大于等于64，链表会转换为红黑树，以提高查找效率。当红黑树节点数量小于6时，又会退化为链表。