哈希数据结构
哈希表用哈希函数把键映射到桶，再在桶中查找对应记录。哈希分布均匀、装载因子适当时，查询通常具有平均 O(1) 的时间复杂度；严重冲突时会变慢，不能保证每次都是常数时间。
例如：现在有个数组里面存放的是1到15这些数字，现在需要将这些数字存放到大小为7的哈希表里面。
哈希下标 = number 模 7
第一次存入将1-6的元素存入哈希表
第二次将7-13存入哈希表，这时候出现了一个问题，那就是出现冲突了，例如 8%7 = 1，和之前的1元素冲突了
第三次存入14，15，还是冲突了
碰撞处理方法
两个不同的值，通过同一个散列函数计算出相同的哈希值。
常见的解决方案有：
- 开放地址寻址法：冲突后按探测规则寻找其他槽位。
- 链地址法：同一个桶保存多个记录。
- 双重散列：用另一个哈希函数计算探测步长。
- 建立公共溢出区
- 杜鹃散列
- 跳房子散列
- 罗宾汉散列
后续四种方式都是很少见的，所以就简单的整理下相关概念。
开放地址寻址法
一旦发现了冲突，就会寻找下一个空的散列地址，只要空间足够大，能够找到一个空的散列地址，然后将记录写入。
例如上图，我们已经有了元素1，2，4，5，现在需要存入7，8，9，元素7不会冲突，但是元素8和元素1冲突了，所以会往后找空的散列地址，元素9也是同理。
是否会存在一个问题，那就是现在有了个元素10，但是哈希表里面的索引3已经被元素8占据了，导致无法存入的问题？
这里牵扯到部分ThreadLocal的知识，后续将会单独讲解，在 ThreadLocal 的实现中会使用斐波那契散列、索引计算累加、启发式清理、探测式清理等操作，以保证尽可能少的碰撞。
链地址法
将哈希表的每个单元作为一个链表的头节点，然后冲突了直接在对应的链表尾部插入元素，如下图所示。
注意事项
- 数组的长度必须是2的幂次方，提高模的运算效率
- 一旦链表的长度超过数组的75%，就需要进行扩容
- 计算到哈希数组对应下标里面的元素是否为空，如果为空就直接写入，不为空就判断key是否一致，一致就覆盖，不一致就使用链表存储（JDK8之后，采用的红黑树，如果链表长度大于8，将会转换为红黑树）
再哈希法
同时构造多个不同的哈希函数，如果发生了哈希冲突，那么就采用其他的哈希函数，直到不冲突。缺点是计算的时间比较长。
建立公共溢出区
设计两个表：基础表和公共溢出表。未发生冲突的数据写入到基础表，发生冲突的数据写入公共溢出表。查找的时候，计算出对应的散列地址，首先会和基础表位置进行比较，如果不相等，就到溢出表里面去寻找。
面试题
- 什么是散列表（哈希表）？有什么特征
- 拉链法和开放地址寻址法的区别
- 其他的碰撞处理办法
装载因子
装载因子是记录数与桶数的比值：α = n / m。桶数不变而记录增多时，冲突通常增加；扩容可以降低装载因子，但需要重新分配和迁移记录。
布隆过滤器是用于集合成员判断的概率型结构，存在误判，不是哈希表保存冲突记录的方法。Java HashMap 的复杂度条件见 官方说明。
评论