38、hashtable中解决冲突有哪些方法?

记住前三个:

线性探测

使用hash函数计算出的位置如果已经有元素占用了,则向后依次寻找,找到表尾则回到表头,直到找 到一个空位

开链

每个表格维护一个list,如果hash函数计算出的格子相同,则按顺序存在这个list中

再散列

发生冲突时使用另一种hash函数再计算一个地址,直到不冲突

二次探测

使用hash函数计算出的位置如果已经有元素占用了,按照$1^2$、$2^2$、$3^2$...的步长依次寻找,如 果步长是随机数序列,则称之为伪随机探测

公共溢出区

一旦hash函数计算的结果相同,就放入公共溢出区

上一篇:为什么有了HashMap 还产生了HashTable


下一篇:哈希表的伟大之处!