我正在构建一个表,当发生冲突时,尝试在表中插入一个新键遵循序列{hash(x)+i,其中i=1,2,3,…。}. 如果我正在使用线性探测构建哈希表,那么我的insert()算法是否会执行如下操作:
hashValue = hash(x)
while hashValue is taken in table
hashValue += 1
其中,我只在发生冲突时添加增量值,或者在i=1时将增量值从一开始就添加到散列中,如下所示:
hashValue = hash(x) + 1
while hashValue is taken in table
hashValue += 1
最佳答案
只要你始终如一地去做,这无关紧要。向哈希代码中添加一个(或任何其他常量)的效果对表的组成没有影响,只是存储桶编号将被常量“偏移”所“偏移”既然bucket编号是have表的私事,没人应该在意。
本质上,线性探测哈希函数是
H(x, i) = (H(x) + i) % N
其中
N
是桶的数量。传统的做法是从零开始i
,这意味着只有在发生冲突时才增加hash的值。