Python 哈希：插入方法

Question

我一直在尝试为我的 MyHashTable: class.

编写一个 insert(self, key): 方法

应该使用线性探测来处理冲突解决。如果密钥已经在 table 中，则方法 returns -2。如果密钥不在 table 中并且存在空槽，则将密钥输入到 hash_function 返回的空槽号中，并返回该槽号。如果密钥不在散列 table 中并且没有空槽那么它 returns -1.

这是我的 class:

class MyHashTable:

def __init__(self, capacity):
    self.capacity = capacity
    self.slots = [None] * self.capacity

def __str__(self):
    return str(self.slots )

def __len__(self):
    count = 0
    for i in self.slots:
        if i != None:
            count += 1
    return count

def hash_function(self, key):
    i = key % self.capacity
    return i

def insert(self, key):
    slot = self.hash_function(key)
    if key in self.slots[slot]:
        return -2
    elif key in self.slots[slot] == False:
        return -1
    else:
        self.slots[slot].append(key)
        return slot

测试是：

x = MyHashTable(2)
print("Add 3, return:", x.insert(3))
print("Hashtable:", x)
print("Add 3, return:", x.insert(3))  #duplicate
print("Hashtable:", x)

结果应该是：

Add 3, return: 1
Hashtable: [None, 3]
Add 3, return: -2
Hashtable: [None, 3]

我尝试了几种方法，但一直出现错误。 "Nonetype" 不可迭代。

Answer 1

好的，我们必须从这里的第一原则开始。以下是 insert 需要为您的案例做的事情：

通过调用hash_function获取基于密钥的初始槽号。保存这个插槽位置以备后用，我们需要它来检测哈希 table 是否已满。
检查当前插槽是否为空。如果是，则在该点插入密钥，return 成功。
如果密钥已经在那个插槽中，return -2，它是重复的。
否则，该插槽中有一些 other 键，因此将插槽推进到下一个（如果超出容量，则返回到插槽 0）。如果您循环回到第 1 步中保存的原始插槽，return -1 因为 table 已满。
否则返回第 2 步继续寻找钥匙或空槽。

这基本上就是线性探测散列的预期工作方式。

我敦促你尝试自己实现它，你会成为一个更好的编码员，付出一些血汗和泪水:-)

完成后，看看它与我的初始剪辑相比如何：

def insert(self, key):
    slot = self.hash_function(key)
    orig = slot
    while True:
        if self.slots[slot] is None:
            self.slots[slot] = key
            return slot

        if self.slots[slot] == key:
            return -2

        slot = (slot + 1) % self.capacity
        if slot == orig:
            return -1

我保留在其中留下某些细微错误的权利，以防这是你应该自己做的课堂作业（实际上，我只是粗略地测试了一下运行，所以它可能不会完全没有错误，但它与我提供的算法匹配，所以应该接近）。

Answer 2

只要你没有 return 任何东西，你的 insert() 就不会 return 可迭代。

我猜你要打印的是 MyHashTable x 本身。否则你需要将 return self 附加到 insert() 的定义中，尽管它看起来很奇怪。

Python 哈希：插入方法

Python Hash: Insert Method

python

hash

insert

hashtable