Skip to content

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

Description

@loveleicheng

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

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,循环就无法跳出。

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions