我正在构建一个表,当发生冲突时,尝试在表中插入一个新键遵循序列{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的值。

07-26 09:29
查看更多