python - 哈希表中的冲突和探测长度有什么区别？如何跟踪它们？

Question

嗨，我是 Python 新手，我实现了一个哈希表类，它通过线性探测来解决冲突。

现在我正在尝试编写一个函数来跟踪碰撞次数和探头长度。我已经编写了函数来跟踪碰撞次数，但我不知道如何跟踪探头长度，因为我以为他们是一样的？

def getCollisionAndProbeLength(self, key, value):
    position = self.hash_value(key)
    collision=0
    probeLength=0

    for i in range(self.table_size):
        if self.array[position] is None || self.array[position][0]==key && self.array[position][1]==value :#correct item or collision resolved
            break
        elif self.array[position][0]==key && self.array[position][1]!=value:
            collision+=1
            position = (position+1) % self.table_size
 return [collision,probeLength]

编辑：好吧，显然碰撞意味着 hash(key) 给出的位置已经被占用。探测长度是在那之后你做了多少次尝试，直到你找到一个位置（在开放寻址中）。

所以我猜应该是这样的：

 elif self.array[position][0]==key && self.array[position][1]!=value:
            collision+=1
            probeLength=collision-1
            position = (position+1) % self.table_size

Answer 1

好吧，显然碰撞意味着 hash(key) 给出的位置已经被占用。探测长度是在那之后你做了多少次尝试，直到你找到一个位置（在开放寻址中）。