数据结构系列五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*KeyB对应连续紧凑地对上数组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探测增量以冲突索引 为起始点(indexi)%table_sizei1,2,3...线性探测以常量1为增量 一个个往后 增键值化索引 探测找空位放1.1.1.2填空分布线性探测一个个往后填空位的方式在后面会使得空位被填成冲突点成线性成块直线连续1.1.1.3退出条件理想情况下是直到有次找空位 找到回 起始冲突点时说明表已填满 而去扩表但实际肯定会在表满之前 负载因子挺高时就直接退出探测 去扩表了1.1.1.4空间利用率填空的直线分布会导致后续的每次找空位 都会连续地遍历表近O(n)时间复杂度会变得很高所以不会等到 表真的全填满在负载因子超过一定数值后 表就留空位用不上 而去扩表了而且线性探测时 负载因子会设得很低每次表留的空位会很多维护的表的空间利用率很低1.1.2二次探测方式1.1.2.1探测增量以冲突索引 为起始点(indexi²)%table_sizei1,2,3...二次探测以探寻次数i的平方变量为增量 往后跳跃 增键值化索引 去探测空位放1.1.2.2表容量要求用二次探测的表 的容量要设置为table_size4k3的质数这样能保证 二次探测能探测到 表的所有位置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.空间利用率哈希表的闭散列冲突解决方式的 空间利用率是很低的虽然开散列的空间利用率不会像闭散列 低得很明显但空间利用率低就是哈希本质的缺陷
【数据结构】哈希表
数据结构系列五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*KeyB对应连续紧凑地对上数组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探测增量以冲突索引 为起始点(indexi)%table_sizei1,2,3...线性探测以常量1为增量 一个个往后 增键值化索引 探测找空位放1.1.1.2填空分布线性探测一个个往后填空位的方式在后面会使得空位被填成冲突点成线性成块直线连续1.1.1.3退出条件理想情况下是直到有次找空位 找到回 起始冲突点时说明表已填满 而去扩表但实际肯定会在表满之前 负载因子挺高时就直接退出探测 去扩表了1.1.1.4空间利用率填空的直线分布会导致后续的每次找空位 都会连续地遍历表近O(n)时间复杂度会变得很高所以不会等到 表真的全填满在负载因子超过一定数值后 表就留空位用不上 而去扩表了而且线性探测时 负载因子会设得很低每次表留的空位会很多维护的表的空间利用率很低1.1.2二次探测方式1.1.2.1探测增量以冲突索引 为起始点(indexi²)%table_sizei1,2,3...二次探测以探寻次数i的平方变量为增量 往后跳跃 增键值化索引 去探测空位放1.1.2.2表容量要求用二次探测的表 的容量要设置为table_size4k3的质数这样能保证 二次探测能探测到 表的所有位置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.空间利用率哈希表的闭散列冲突解决方式的 空间利用率是很低的虽然开散列的空间利用率不会像闭散列 低得很明显但空间利用率低就是哈希本质的缺陷
