⽬录
⼀、了解哈希表及哈希冲突
哈希表：是⼀种实现关联数组抽象数据类型的数据结构，这种结构可以将关键码映射到给定值。简单来说哈希表（key-value）之间存在⼀个映射关系，是键值对的关系，⼀个键对应⼀个值。
哈希冲突：当两个不同的数经过哈希函数计算后得到了同⼀个结果，即他们会被映射到哈希表的同⼀个位置时，即称为发⽣了哈希冲突。简单来说就是哈希函数算出来的地址被别的元素占⽤了。 ⼆、解决哈希冲突办法
1、开放定址法：我们在遇到哈希冲突时，去寻⼀个新的空闲的哈希地址。
举例：就是当我们去教室上课，发现该位置已经存在⼈了，所以我们应该寻新的位⼦坐下，这就是开放定址法的思路。如何寻新的位置就通过以下⼏种⽅法实现。
（1）线性探测法
当我们的所需要存放值的位置被占了，我们就往后⾯⼀直加1并对m取模直到存在⼀个空余的地址供我们存放值，取模是为了保证到的位置在0~m-1的有效空间之中。
公式：h(x)=(Hash(x)+i)mod (Hashtable.length);（i会逐渐递增加1）
举例：
专项审计>bpr存在问题：出现⾮同义词冲突（两个不想同的哈希值，抢占同⼀个后续的哈希地址）被称为堆积或聚集现象。
（2）平⽅探测法（⼆次探测）
当我们的所需要存放值的位置被占了，会前后寻⽽不是单独⽅向的寻。
公式：h(x)=(Hash(x) +i)mod (Hashtable.length);（i依次为+(i^2)和-(i^2)）
举例：
batista手术>彝药2、再哈希法：同时构造多个不同的哈希函数，等发⽣哈希冲突时就使⽤第⼆个、第三个……等其他的哈希函数计算地址，直到不发⽣冲突为⽌。虽然不易发⽣聚集，但是增加了计算时间。
3、链地址法：将所有哈希地址相同的记录都链接在同⼀链表中。
北京电视台台长
公式：h(x)=xmod(Hashtable.length);氯仿
4、建⽴公共溢出区：将哈希表分为基本表和溢出表，将发⽣冲突的都存放在溢出表中。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议