python_data_structures_and_algorithms icon indicating copy to clipboard operation
python_data_structures_and_algorithms copied to clipboard

哈希表的二次探测函数有bug,会出现无限循环

Open loveleicheng opened this issue 2 years ago • 0 comments

大佬,你这里哈希表的二次探测函数,会出现无限循环的情况。

def _find_slot_for_insert(self, key):
    index = self._hash(key)
    _len = len(self._table)
    while not self._slot_can_insert(index):  # 直到找到一个可以用的槽
        index = (index * 5 + 1) % _len
    return index

def _slot_can_insert(self, index):
    return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)

如上,如果index为5,此时5的位置上如果存在数据了,则需要继续找。假设此时_len为7,index为5, 则:(5 * 5 + 1)% 7 结果最终还是5,循环就无法跳出。

loveleicheng avatar May 04 '22 15:05 loveleicheng