计算机知识散列表处理冲突方法思维导图

当di = 0，1，-1^2，2^2，-2^2，3^2，-3^2....k^2, -k^2 (k <= m/2)

散列表长度m必须可以表示成 4k+3的素数，又称二次探测法

避免“堆积”问题，但不能探测到散列表的所有单元，但至少能探测到一半

当di = Hash2(key)时，称为再散列法/双散列法

需要两个散列函数，当第一个散列函数发生冲突时，利用第二个散列函数Hash2（key）计算该关键字的地址增量

Hi = （H(key)+i*Hash2(key)）%m

初始探测位置H0=H(key)%m，i是冲突次数，初始为0

最多经过m-1次探测会遍历表中所有位置，会到H0

di为伪随机序列

当di = 0，1，2，3....m-1时，称为线性探测法

当发生冲突时，循环查找散列表下一个空闲的单元（到m-1下一个要找的就是0）可能会查遍全表