哈希 - 将值插入哈希表

Question

谁能帮我修复在哈希表中插入值的 put 函数？现在我得到了一个充满 None 的哈希表的输出例如 [无、无、无、无、无]

class BasicHashTable:
def __init__(self,size=7):
    self.size = size
    self.slots = [None] * self.size
def hash_function(self, key):
    return key%len(self.slots)
def rehash(self, old_pos):
    return (old_pos + 1) % self.size
def put(self, key):
    hash_value = key%len(self.slots)    
    probe_seq=[]     
    insert_pos=hash_value     
    probe_seq+=[insert_pos]     
    probes=1     
    while(self.slots[insert_pos]!=None):         
        probes+=1         
        insert_pos=(insert_pos+1)%len(self.slots)         
        probe_seq+=[insert_pos]     
        self.slots[insert_pos]=key     
    return insert_pos

测试：

hash_t = BasicHashTable() 
hash_t.put(3)
hash_t.put(20)
hash_t.put(10)
print(hash_t.slots)

给出 [无、无、无、3、10、无、20]

Answer 1

它不会添加到地图中，因为在开始时，插槽都是None的，所以 while 中的代码永远不会执行。此代码包括将值分配给槽的代码。您可以通过执行以下操作来解决此问题：

# code
while(self.slots[insert_pos]!=None):         
    #code  
self.slots[insert_pos]=key  # unindented
# code

Answer 2

你走在正确的轨道上。首先，您应该使用您创建的 rehash 方法。因此，如果无法立即插入密钥，您将生成一个新的哈希。您将继续这样做，直到找到一个空插槽，然后将密钥插入该插槽。

def put(self, key):
    insert_pos = self.hash_function(key)
    if self.slots[insert_pos] == None:
        self.slots[insert_pos] = key
    else:
        insert_pos = self.rehash(insert_pos)
        while self.slots[insert_pos] != None and self.slots[insert_pos] != key:
            insert_pos = self.rehash(insert_pos)
        if self.slots[insert_pos] == None:
            self.slots[insert_pos] = key

一旦所有插槽都被填满，如果您尝试添加新密钥，程序将无限循环;我会让你找到解决这个问题的方法。当您开始向密钥添加数据时，您可能会找到解决方案。

此外，您还应该使用您创建的 size 属性，如下所示：

def hash_function(self, key):
    return key%self.size