数据结构——哈希表（Hash表）、哈希碰撞_哈希碰撞和哈希冲突

作者：Gausst松鼠会 | 2024-06-08 06:32:33

踩

哈希碰撞和哈希冲突

哈希表（也叫散列表），是根据键（Key）直接访问在内存存储位置的数据结构。就是一种以键-值(key-value) 存储数据的结构，我们只要输入key，就可查找到其对应的值。

hash函数就是根据key计算出该存储地址的位置，hash表就是基于hash函数建立的一种查找表。

当使用hash表查询时，就是使用hash函数将key转换成对应的数组下标，并定位到该下标的数组空间里获取value，这样就充分利用到数组的定位性能进行数据定位。

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希碰撞，也叫哈希冲突。

（1）链地址法：在冲突的地方通过链表来解决

优点：处理形式简单，没有数据堆积，平均查找时间相对较短

缺点：如果哈希冲突比较大，卡槽存储的数据可能就会比较多

（2）线性探测法：

线性探测函数：H(i)=i或者H(i)=i*c(c是常量)

随机探测：H(i)=randon(i)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/688768