double hash 是啥

双重哈希是开放寻址哈希表中的冲突解决技术。双重哈希的思想是在发生冲突时对键做第二个哈希函数。

双重哈希可以处理 :

(hash1(key) + i * hash2(key)) % TABLE_SIZE

这里 hash1() 、 hash2() 是hash 函数， TABLE_SIZE 是hash表大小

(如果发生冲突，i递增然后重复运算)

通俗的二次Hash函数：hash2(key) = PRIME – (key % PRIME)

PRIME一般选择小于 TABLE_SIZE 的质数

优质的二次Hash函数应该具备这些条件：

二次Hash函数结果不能为0

第二个哈希函数要可以覆盖表的每一个单元