企业官网建设流程全解析

数据结构系列五：Map与Set(二)

哈希原理

一、冲突避免

1.哈希函数设计

1.1除留余数法：

1.2线性定制法：

2.负载因子调控

扩表：

二、冲突解决

1.深度存储(二次分配)

1.1闭散列分配

1.1.1线性探测方式

1.1.1.1探测增量

1.1.1.2填空分布

1.1.1.3退出条件

1.1.1.4空间利用率

1.1.2二次探测方式

1.1.2.1探测增量

1.1.2.2表容量要求

1.1.2.3填空分布

1.1.2.4退出条件

1.1.2.5空间利用率

1.1.3删除方式

1.2开散列分配

减短链长：

2.深度搜索(二次搜索)

三、优点与缺陷

1.时间复杂度

2.空间利用率

哈希原理

把节点的键值 通过哈希函数 计算映射成索引 直接确定在数组中的存储位置，相较于 进去搜寻与一个个比较的 比较确定方式，维护的映射确定存储 能使得哈希表实现对数据的极速定位 来操作(存储、查询、修改、删除)

一、冲突避免

不同元素的不同键值多个对应映射到 哈希表相同索引处时，存储冲突就发生了，为尽量避免哈希表里面去深度存储或降低深度存储时的复杂度，我们要做的就是降低键值存储时的冲突率，通过合理的哈希函数设计或 存储的键值多时 去扩表调控负载因子

1.哈希函数设计

哈希函数要使得 要来的键值都能 且尽量均匀少重叠地 对应转为哈希数组的索引范围内

1.1除留余数法：

键值%数组长度的值域为0~数组长度-1，即刚好面向 存储的哈希数组 所有位置存放，且对于大部分套数据，不规则的模上 数组长度 得到的也是不规则值域 最后散落在哈希数组中均匀分布的

1.2线性定制法：

如果套数据连续紧凑，也可以设置成线性函数A*Key+B对应连续紧凑地对上数组

2.负载因子调控

填入表中的元素越多时，元素之间的 存储冲突概率就会变大，大到一定程度时 就通过扩表 将表的存储冲突率再降下去，动态地调控 使表的冲突率维持在一个范围之下

扩表：

扩表时，表的容量改变，如果哈希函数与表的容量相关的，哈希函数也改变，键值映射到的索引也会改变需要更新，即要把所有元素去重新哈希重新映射存储

扩表代码

private void resize() { Node[] tmpArr = new Node[array.length*2]; //遍历原来的数组 将所有的元素《重新哈希》到新的数组当中 for (int i = 0; i < array.length; i++) { Node cur = array[i]; while (cur != null) {//每个索引桶里面的链表全部节点都要重新哈希 //记录当前链表节点的下个节点 Node curNext = cur.next; //重新映射的索引 int newIndex = cur.key % tmpArr.length; //头插 cur.next = tmpArr[newIndex]; tmpArr[newIndex] = cur; cur = curNext; } } array = tmpArr; }

二、冲突解决

1.深度存储(二次分配)

元素的键值多个对应映射到 哈希表相同索引处时，存储冲突就发生了，要把冲突元素进行二次分配：

1.1闭散列分配

• 闭散列把冲突元素分配到哈希表的其它空位上

如果键值存储计算的索引 冲突了，那么将冲突的键值按照规定的探测方式找到并放到表中其它剩余的空位里，下次查询时都是如果遇到已填上 就按照约定 以约定的探测方法 会再往后查查看

1.1.1线性探测方式

1.1.1.1探测增量

以冲突索引 为起始点，(index+i)%table_size（i=1,2,3...）线性探测以常量1为增量 一个个往后 增键值化索引 探测找空位放

1.1.1.2填空分布

线性探测一个个往后填空位的方式在后面会使得空位被填成冲突点成线性成块直线连续

1.1.1.3退出条件

理想情况下是直到有次找空位 找到回 起始冲突点时，说明表已填满 而去扩表，但实际肯定会在表满之前 负载因子挺高时就直接退出探测 去扩表了

1.1.1.4空间利用率

填空的直线分布会导致后续的每次找空位 都会连续地遍历表近O(n)，时间复杂度会变得很高，所以不会等到 表真的全填满，在负载因子超过一定数值后 表就留空位用不上 而去扩表了，而且线性探测时 负载因子会设得很低，每次表留的空位会很多，维护的表的空间利用率很低

1.1.2二次探测方式

1.1.2.1探测增量

以冲突索引 为起始点，(index+i²)%table_size（i=1,2,3...）二次探测以探寻次数i的平方变量为增量 往后跳跃 增键值化索引 去探测空位放

1.1.2.2表容量要求

用二次探测的表 的容量要设置为table_size=4k+3的质数，这样能保证 二次探测能探测到 表的所有位置

1.1.2.3填空分布

能不规则地整体均匀地探测存储冲突率小

1.1.2.4退出条件

• 二次探测的不规则跳跃性 常常会重复探测 已探测过的 不为空的位置，所以不能以 再找回冲突点而停下，要继续找
• 如果表已满时也会 再也找不到空位，所以不能以 找到空位而停下

所以探测找空位循环的结束条件 就设置成的是探测次数超过表容量时就停下

1.1.2.5空间利用率

以 不规则跳跃性地 探测，表容量次中 肯定会有很多次的重复探测而且越到后面就会呈现出很多空位点实际而且是需要不止表容量次 才能探测到的，就会出现表实际还有很多空位而认为表满 而退出去扩表，这样的一直维护 就会导致 任意次每次创的表中 都会有很多空位创建来 而用不上 填不上去存储 而就又去扩表的，再加上负载因子条件的 主动退出填表，表的空间利用率会低（二次探测因为不规则的存储与跳跃探测，能承受的负载因子 会更高时 再去扩表，空间利用率比线性探测的 会高点）

1.1.3删除方式

删除元素时，采用墓碑标记删除，节点还是存储在那 存在，仅把节点的状态 标记为删除

• 下次探测到此位置时根据节点存在与删除的信息 会继续往后探测 不断探测链
• 下次扩表重新哈希时再将墓碑节点删去 不去映射存储

墓碑实现代码

class HashEntry { final int key; String value; boolean isDeleted; // 标记删除时不清空数据 void delete() { isDeleted = true; } }

1.2开散列分配

• 开散列把冲突元素分配到同桶的链式结构上

分配放到的 桶存储链式结构 可以是链表、红黑树、或又是一个哈希表

减短链长：

链式结构的链条过长时，通过扩表或转红黑树减短链长

2.深度搜索(二次搜索)

不管是以 开散列还是闭散列 去二次分配冲突元素 来解决冲突，冲突其实都已导致了元素去深度存储，相对应地后面就需要去深度搜索获取

三、优点与缺陷

1.时间复杂度

虽然有时候需要进行二次分配、二次搜索，但经过合理的哈希函数设计、调控负载因子的扩表，哈希表的冲突率 调控得是比较低的，每索引桶里面如果有冲突，冲突元素的个数也是常量级的，二次存储的结构也就比较简单，往二次存储结构搜索的时间复杂度也是O(1)，所以总体哈希表的 定位元素去插删查 的时间复杂度是O(1)

2.空间利用率

哈希表的闭散列冲突解决方式的 空间利用率是很低的，虽然开散列的空间利用率不会像闭散列 低得很明显，但空间利用率低就是哈希本质的缺陷