本文共 323 字,大约阅读时间需要 1 分钟。
双重哈希属于开放地址哈希中的一种解决冲突方案,也就是说如果一次哈希不能解决问题的时候,要再次哈希,与再哈希方法不同的是,第二次使用的哈希函数与第一次是不同的:
(hash1(key) + i * hash2(key)) % TABLE_SIZE
一般来讲,
hash1(key) = key % TABLE_SIZEhash2(key) = PRIME – (key % PRIME)
其中PRIME
一般选一个比TABLE_SIZE
小的一个质数就可以了,例如如果TABLE_SIZE=16
,那么PRIME=13
。
注意:第二个哈希函数结果不能为0,而且第二个哈希函数要覆盖表的每一个单元。
至于i
就从1开始尝试就是了,如果有冲突,则再尝试i++
。
转载地址:http://zshii.baihongyu.com/