四种解决哈希冲突的方法
可阿奇 2023/6/9 C++
# 1. 了解哈希表及哈希冲突
哈希表：是一种实现关联数组抽象数据类型的数据结构，这种结构可以将关键码映射到给定值。简单来说哈希表（key-value）之间存在一个映射关系，是键值对的关系，一个键对应一个值。
哈希冲突：当两个不同的数经过哈希函数计算后得到了同一个结果，即他们会被映射到哈希表的同一个位置时，即称为发生了哈希冲突。简单来说就是哈希函数算出来的地址被别的元素占用了。
# 2. 解决哈希冲突办法
# 2.1 开放定址法：我们在遇到哈希冲突时，去寻找一个新的空闲的哈希地址。
# 2.1.1 线性探测法
当我们的所需要存放值的位置被占了，我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值，取模是为了保证找到的位置在0~m-1的有效空间之中。
公式：h(x)=(Hash(x)+i) mod (Hashtable.length);(i会逐渐递增加1)
举例：
存在问题：出现非同义词冲突（两个不相同的哈希值，抢占同一个后续的哈希地址）被称为堆积或聚集现象。
# 2.1.2 平方探测法（二次探测）
当我们的所需要存放值的位置被占了，会前后寻找而不是单独方向的寻找。
公式：h(x)=(Hash(x) +i) mod (Hashtable.length);(i依次为+(i^2)和-(i^2))
举例：
# 2.2 再哈希法：同时构造多个不同的哈希函数，等发生哈希冲突时就使用第二个、第三个……等其他的哈希函数计算地址，直到不发生冲突为止。虽然不易发生聚集，但是增加了计算时间。
# 2.3 链地址法：将所有哈希地址相同的记录都链接在同一链表中。
公式：h(x)=x mod (Hashtable.length);
举例：
