网站建设 自己的服务器,石家庄网站平台,网站定制公司推荐,wordpress百度分享文章目录 一、什么是哈希表#xff1f;二、什么是哈希冲突#xff1f;怎样解决#xff1f;三、哈希表的大小为什么是质数#xff1f;四、链表法五、开放地址法线性探测法平方探测法双哈希(Double Hashing) 六、哈希表满了怎么办#xff1f;七、完美哈希八、一些使用哈希解… 文章目录 一、什么是哈希表二、什么是哈希冲突怎样解决三、哈希表的大小为什么是质数四、链表法五、开放地址法线性探测法平方探测法双哈希(Double Hashing) 六、哈希表满了怎么办七、完美哈希八、一些使用哈希解决的算法题 在我以往的认知中哈希就是进行唯一映射指定一个关键字就能映射唯一的值。平时经常使用linux下的
md5sum命令用来比较两个文件是否相同。至于如何哈希原理它们是怎样进行唯一映射的一直没有去梳理如今该填的洞还是得补上。 一、什么是哈希表
我们知道普通数组能够直接寻址在O(1)时间内能访问到数组中的任意位置。它需要足够大的空间为每一个关键字保留一个位置。当关键字取值的范围很大储存空间又有限时能不能同样用数组的形式实现O(1)查找
哈希表(Hash Table)就是这样的数据结构当实际储存的关键字集合比所有可能的关键字的全集小许多时使用一个长度有限的数组去储存这些关键字从而节省大量的空闲空间。它也被称作为散列表因为它的键是分散存储在数组中的。
如图黄色区域为键的全集范围为0~99绿色区域为实际存储的键。直接寻址需要为所有的键开辟空间而哈希映射仅需为需要储存的键分配空间储存空间比直接寻址少得多。 哈希表的核心思想是将键转换为数组的索引位置以便快速查找对应的值。它使用哈希函数将键映射到数组的索引位置这个索引位置称为哈希值。哈希映射是唯一映射一个键永远只能产生一个哈希值这种映射关系就是我们所说的哈希函数。常见的哈希函数包括MD5、SHA-1、SHA-256等。 二、什么是哈希冲突怎样解决
通过取某运算保持了哈希表中查找一个元素只要O(1)时间的优势。但细心的朋友会发现上图中当键为717时两个键会映射到同一个哈希值。我们称这种情形为哈希冲突由于哈希函数不够“随机”不同的键通过哈希函数计算得到相同的哈希值。
有人会说简单将哈希表增大某上一个更大的值函数不就行了吗可是可以但哈希的精髓在于尽可能的节省空间与查找时间。最普通的哈希表就是一个直接寻址的数组。不过还有其它更高效的方法解决哈希冲突如链表法开放地址法等这个后面再讲。
当哈希表中存储的键越来越多时冲突的概率会不断增大总会有哈希表再也装不下键的时候。所以合理的控制一个哈希表的大小也极为重要。通常将哈希表的大小设置为一个质数是需要储存的键的数量的两倍。 三、哈希表的大小为什么是质数
当哈希表的大小选择为一个合数非质数时键的哈希值可能与哈希表的大小存在公因子。这种情况下多个键的哈希值可能会映射到相同的索引位置导致哈希冲突的概率增加。
让我们通过一个例子来说明这个问题。假设我们有一个哈希表大小为10键的哈希函数将键映射到0到9的索引位置。我们有两个键15和25。它们的哈希值分别为5和5。由于它们的哈希值都映射到相同的索引位置5发生了哈希冲突。
倘若我们选择一个质数作为哈希表的大小比如13再次计算这两个键的哈希值。键15的哈希值为2键25的哈希值为12。由于13是质数与13存在公因子的数字较少因此键的哈希值在13以内相同的概率会少很多。
通过选择质数作为哈希表的大小可以减少键的哈希值与哈希表大小之间存在公因子的情况从而减少哈希冲突的概率。这样可以更均匀地分布键值对提高哈希表的性能和效率。 四、链表法
链表法其实很简单就是将映射到同一地址的元素都放在一个链表中。哈希表中每个槽都有一个指针指向所有映射到同一位置的元素链表表头如果当前槽位没有这样的元素头指针为空。 采用双向链表结构是为了删除与插入操作都能控制时间在O(1)范围内。每一个槽位链表的长度就是它的负载因子。通过上述结构不难看出查找需要遍历链表查找的时间取决于链表的长度。并且当散列不均匀时某一些链过长有一些链很短查找的效率也是不稳定的。
所以一个好的哈希函数不应该将太多的输入映射到相同的输出。 五、开放地址法
除了链表法解决哈希冲突外还可以通过开放地址的方式来解决哈希冲突。之所以叫开放地址是因为它们都是通过将冲突的键存放到哈希表空闲的其它地址中去将未使用的地址开放出来直到表空间耗尽。开方地址有多种方法下面一一介绍。
线性探测法
探测(Probe)是指当地址冲突后会继续去寻找表中可用的地址。线性探测则是顺着当前位置向后查找。
如图将关键字以线性探测的方式插入到哈希表中哈希表的长度为13。 不难看出线性探测随着填充因子的增加冲突会聚集在一起形成聚集效应。负载因子需要控制在70%左右否则冲突次数飙升。数据分布本身不均匀也会导致冲突分布不均匀。线性探测法实现简单但随着负载增加性能下降明显。 平方探测法
如果遇到冲突就往原始位置 i2的位置寻找空位i为查找次数。
如图 平方探测法是解决哈希冲突的一种开放地址法。当发生哈希冲突时,它按一定的平方序列探测下一个位置。
优点:
降低了聚集效应。冲突分配更加均匀。减少了聚簇内的查找时间。可以提高负载因子。平均查找长度较短。
缺点:
需要计算平方序列值实现较为复杂。当Step超过表大小时计算会溢出。随机性较差数据分布不均会影响性能。二次方探测发生冲突的概率较大。删除操作会产生空洞需要惰性删除避免影响。
总体而言平方探测法通过牺牲部分实现复杂度和冲突计算时间来减轻聚集效应在较高负载下性能较好。仍需要考虑非全域性问题。 什么是惰性删除? 惰性删除(Lazy deletion) 是一种常用的哈希表优化方法,主要应用于开放定址法中的删除操作。其基本思路是: 当删除键值对时,先将其标记为已删除,而不直接从散列表中删除记录。对后续插入操作,会扫描标记的已删除槽位并进行插入。直到被后续插入覆盖,标记的删除状态才真正删除。 优点是可以避免删除后产生的空槽位保证使用空间的连续性减少冲突次数提高效率。 缺点是需要扫描已删除槽位增加查询的开销。 主要应用在平方探测法、线性探测法等开放定址中的删除操作使得开放定址法的执行效率大为提升。是哈希表优化的重要手段之一。也可视作是一种延迟紧缩、空间换时间的实现。 双哈希(Double Hashing)
除了第一个哈希函数外还有一个哈希函数用于解决冲突。
如果遇到冲突新位置 原始位置 i * hash2(key)i为查找次数。 hash2(key) R - (key % R) R要取比数组尺寸小的质数。 例如哈希表长度为13R 7hash2(key) 7 - (key % 7) 也就是说第二次哈希结果在1-7之间不会等于0。 举例
双哈希法的主要优点: 采用双重散列冲突分布更加均匀。相比线性探测可以有效减少聚集问题。指数增长级别更低平均查找长度较短。算法和实现都比较简单。允许删除而不产生过多空槽。 双哈希法通过两次散列的思想改进了性能和冲突分布是一种效率较好的开方地址方法。 六、哈希表满了怎么办
再哈希(rehash) 当哈希表的插槽被占用了70%后查找效率会严重下降需要对哈希表进行扩展。 新表长度为原来长度的2倍且为质数。 将旧表中的关键字通过新的哈希函数重新填充到新表中。
由此我们也能看到哈希表有以下缺点 当表中的元素逐渐增多时哈希冲突的概率会增加查找效率会下降。 哈希表扩展时需要将旧表的关键字重新哈希迁移到新表中性能成本大。 一个好的哈希表依赖哈希函数的合理性。 七、完美哈希
完美哈希(Perfect Hashing)是一种解决哈希冲突的方法它通过构建一个无冲突的哈希函数来实现。
完美哈希通过两级哈希的方式来解决哈希冲突。首先使用一个一级哈希函数将键映射到一组桶bucket中。然后在每个桶中使用二级哈希函数将键映射到具体的索引位置。通过这种方式每个键都被映射到唯一的索引位置从而实现了完全散列。
完美哈希在某些特定场景下非常有用特别是当键的集合是已知的且静态的情况下。它可以在预处理阶段构建完全散列函数然后在查询时实现O(1)的查找时间复杂度而无需处理冲突。然而构建完美哈希函数的过程可能会比较复杂且耗时特别是在键的集合较大的情况下。
需要注意的是完美哈希并不适用于动态的键集合因为当键的数量发生变化时可能需要重新构建哈希函数。 八、一些使用哈希解决的算法题 两数之和给定一个整数数组和一个目标值找出数组中和为目标值的两个数的索引。可以使用哈希表来存储数组元素和其索引的映射关系然后遍历数组查找目标值与当前元素的差值是否存在于哈希表中。 两数之和 https://blog.csdn.net/qq_41099859/article/details/112464038 两个数组的交集给定两个整数数组求它们的交集。可以使用哈希集合来存储一个数组中的元素然后遍历另一个数组判断元素是否存在于哈希集合中。 两个数组的交集 https://blog.csdn.net/ShenHang_/article/details/107319514
