Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
loveleicheng opened this issue May 4, 2022 · 0 comments
Open

Comments

@loveleicheng
Copy link

loveleicheng commented May 4, 2022

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant