无限 while 循环在哈希 Table - Python 上使用开放寻址实现 Remove 函数

Question

我正在尝试通过散列 table.

上的线性探测来实现 remove 函数

我遇到了问题，当我尝试调用函数删除时它进入了无限循环。

我该如何解决这个问题？

我用伪代码编写了函数：

remove(t, k):
    z = 0
    repeat
        x = hash_function (k, z)
        if hash_table[x] == k:
             hash_table[x] = deleted return x
        z = z+1
     until hash_table[x] == NIL or z == m
     return NIL

这是代码变成了class：

class lin_prob:
    def __init__(self, table_size):
        
        self.hash_table = [None]*table_size
        self.n_prime = 109169
        self.a = random.randint(2, self.prime-1)
        self.b = random.randint(2, self.prime-1)
        self.n_keys = 0
    
    def remove(self, k):
        z = 0
        while self.hash_table[x] != None or z < len (hash_table):
            x = self.hash_function(k)
            if self.hash_table[x] == k:
                self.hash_table[x] = "deleted"
                return x
            else :
                z = z+1
        return "NIL"

    
    def hash_function(self, k):
        return ((self.a*k + self.b) % self.prime_number) % len(self.hash_table)
    
    def len(self):
        return self.n_keys

Answer 1

如果要否定 until 条件以创建 while 条件，则必须将 or 更改为 and:

while self.hash_table[x] != None and z < len (hash_table):
    ...

此外，您的代码无法工作，因为 x 在您的 remove 方法中未知。

Answer 2

问题出在你放入 while 循环的条件 while self.hash_table[x] != None and z < len (hash_table): 因为等于 == 的否定不等于 !=。我相信它会解决你的问题。

无限 while 循环在哈希 Table - Python 上使用开放寻址实现 Remove 函数

Infinite while loop implementing Remove function using Open Addressing on Hash Table - Python

python

hashtable