本文作者：程序员飞云

本站地址：https://www.flycode.icu

哈希数据结构

能够将任意长度的输入，通过散列算法，变成固定长度的输出，能够通过O(1)的时间复杂度定位到指定元素。

例如：现在有个数组里面存放的是1到15这些数字，现在需要将这些数字存放到大小为7的哈希表里面。

哈希下标 = number 模 7

第一次存入将1-6的元素存入哈希表

image-20240129100816863

第二次将7-13存入哈希表，这时候出现了一个问题，那就是出现冲突了，例如 8%7 = 1，和之前的1元素冲突了

image-20240129100927913

第三次存入14，15，还是冲突了

image-20240129100948315

碰撞处理方法

两个不同的值，通过同一个散列函数计算出相同的哈希值。

常见的解决方案有：

1. 开放地址寻址法（ThreadLocal）
2. 链地址寻址法（CurrentHashMap）
3. 再哈希法（布隆过滤器）
4. 建立公共溢出区
5. 杜鹃散列
6. 跳房子散列
7. 罗宾汉散列

后续四种方式都是很少见的，所以就简单的整理下相关概念。

开放地址寻址法

一旦发现了冲突，就会寻找下一个空的散列地址，只要空间足够大，能够找到一个空的散列地址，然后将记录写入。

image-20240129101445585

例如上图，我们已经有了元素1，2，4，5，现在需要存入7，8，9，元素7不会冲突，但是元素8和元素1冲突了，所以会往后找空的散列地址，元素9也是同理。

是否会存在一个问题，那就是现在有了个元素10，但是哈希表里面的索引3已经被元素8占据了，导致无法存入的问题？

这里牵扯到部分ThreadLocal的知识，后续将会单独讲解，在 ThreadLocal 的实现中会使用斐波那契散列、索引计算累加、启发式清理、探测式清理等操作，以保证尽可能少的碰撞。

链地址法

将哈希表的每个单元作为一个链表的头节点，然后冲突了直接在对应的链表尾部插入元素，如下图所示。

image-20240129102648855

注意事项

1. 数组的长度必须是2的幂次方，提高模的运算效率
2. 一旦链表的长度超过数组的75%，就需要进行扩容
3. 计算到哈希数组对应下标里面的元素是否为空，如果为空就直接写入，不为空就判断key是否一致，一致就覆盖，不一致就使用链表存储（JDK8之后，采用的红黑树，如果链表长度大于8，将会转换为红黑树）

再哈希法

同时构造多个不同的哈希函数，如果发生了哈希冲突，那么就采用其他的哈希函数，直到不冲突。缺点是计算的时间比较长。

建立公共溢出区

设计两个表：基础表和公共溢出表。未发生冲突的数据写入到基础表，发生冲突的数据写入公共溢出表。查找的时候，计算出对应的散列地址，首先会和基础表位置进行比较，如果不相等，就到溢出表里面去寻找。

面试题

1. 什么是散列表（哈希表）？有什么特征
2. 拉链法和开放地址寻址法的区别
3. 其他的碰撞处理办法

贡献者

• flycodeu

版权所有

版权归属：flycodeu

许可证：署名 4.0 国际 (CC-BY-4.0)