Привет, я новичок в 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]
EDIT:
Хорошо, очевидно, столкновение означает, что позиция, заданная хешем (ключом), уже занята. Длина зонда - это количество попыток, которое вы делаете после этого , пока не найдете позицию (при открытой адресации).
Итак, я думаю, это должно быть так:
elif self.array[position][0]==key && self.array[position][1]!=value:
collision+=1
probeLength=collision-1
position = (position+1) % self.table_size