乐趣区

关于java:面试复盘哈希冲突的常见解决方案

jiezi

哈希抵触是指在哈希表中，两个或多个元素被映射到了同一个地位的状况。

String str1 = "3C";
String str2 = "2b";
int hashCode1 = str1.hashCode();
int hashCode2 = str2.hashCode();
System.out.println("字符串:" + str1 + ", hashCode:" + hashCode1);
System.out.println("字符串:" + str2 + ", hashCode:" + hashCode2);

程序的运行后果如下：

不同的字符串，却领有了雷同的 hashCode 这就是哈希抵触。因为元素的地位是依据 hashCode 的值进行定位的，此时它们的 hashCode 雷同，但一个地位只能存储一个值，这就是哈希抵触。

解决哈希抵触

在 Java 中，解决哈希抵触的罕用办法有以下三种：链地址法、凋谢地址法和再哈希法。

  1. 链地址法（Separate Chaining）：将哈希表中的每个桶都设置为一个链表，当产生哈希抵触时，将新的元素插入到链表的开端。这种办法的长处是简略易懂，实用于元素数量较少的状况。毛病是当链表过长时，查问效率会升高。
  2. 凋谢地址法（Open Addressing）：当产生哈希抵触时，通过肯定的探测办法（如线性探测、二次探测、双重哈希等）在哈希表中寻找下一个可用的地位。这种办法的长处是不须要额定的存储空间，实用于元素数量较多的状况。毛病是容易产生汇集景象，即某些桶中的元素过多，而其余桶中的元素很少。
  3. 再哈希法（Rehashing）：当产生哈希抵触时，应用另一个哈希函数计算出一个新的哈希值，而后将元素插入到对应的桶中。这种办法的长处是简略易懂，实用于元素数量较少的状况。毛病是须要额定的哈希函数，且当哈希函数不够随机时，容易产生汇集景象。

链地址法 VS 凋谢地址法

链地址法和凋谢地址法集体感觉以下几点不同：

  1. 存储构造不同：链地址法规定了存储的构造为链表（每个桶为一个链表），每次将值存储到链表的开端；而凋谢地址法未规定存储的构造，所以它能够是链表也能够是树结构等。
  2. 查找形式不同：链地址法查找时，先通过哈希函数计算出哈希值，而后在哈希表中查找对应的链表，再遍历链表查找对应的值。而凋谢地址法查找时，先通过哈希函数计算出哈希值，而后在哈希表中查找对应的值，如果查找到的值不是要查找的值，就持续查找下一个值，直到查找到为止。
  3. 插入方法不同：链地址法插入时，先通过哈希函数计算出哈希值，而后在哈希表中查找对应的链表，再将值插入到链表的开端。而凋谢地址法插入时，是通过肯定的探测办法，如线性探测、二次探测、双重哈希等，在哈希表中寻找下一个可用的地位。所以链地址法插入方法实现非常简单，而凋谢地址法插入方法实现绝对简单。

线性探测 VS 二次探测

线性探测是产生哈希抵触时，线性探测会在哈希表中寻找下一个可用的地位，具体来说，它会查看哈希表中下一个地位是否为空，如果为空，则将元素插入该地位；如果不为空，则持续查看下一个地位，直到找到一个闲暇的地位为止。

二次探测是产生哈希抵触时，二次探测会应用一个二次探测序列来寻找下一个可用的地位，具体来说，它会计算出一个二次探测序列，而后顺次查看哈希表中的每个地位，直到找到一个闲暇的地位为止。二次探测的长处是绝对于线性探测来说，它更加平均地散布元素，毛病是当哈希表的大小扭转时，须要从新计算二次探测序列。

具体来说，二次探测序列是一个二次函数，它的模式如下：

f(i) = i^2

其中，i 示意探测的步数，f(i) 示意探测的地位。

例如，当产生哈希抵触时，如果哈希表中的第 k 个地位曾经被占用，那么二次探测会顺次查看第 k+1^2、第 k-1^2、第 k+2^2、第 k-2^2、第 k+3^2、第 k-3^2……等地位，直到找到一个闲暇的地位为止。

二次探测的长处是绝对于线性探测来说，它更加平均地散布元素，但毛病是容易产生二次探测汇集景象，即某些桶中的元素过多，而其余桶中的元素很少。

HashMap 如何解决哈希抵触？

在 Java 中，HashMap 应用的是凋谢地址法解决哈希抵触的，因为在 JDK 1.8 之后（蕴含 JDK 1.8），HashMap 应用的数组 + 链表或红黑树的构造来存储数据了，所以显然不能应用链地址法来解决哈希抵触。

本文已收录至《Java 面试突击》，专一 Java 面试 100 年，查看更多：www.javacn.site

退出移动版