Python 哈希:插入方法
Python Hash: Insert Method
我一直在尝试为我的 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" 不可迭代。
好的,我们必须从这里的第一原则开始。以下是 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
我保留在其中留下某些细微错误的权利,以防这是你应该自己做的课堂作业(实际上,我只是粗略地测试了一下 运行,所以它可能不会完全没有错误,但它与我提供的算法匹配,所以 应该 接近)。
只要你没有 return 任何东西,你的 insert() 就不会 return 可迭代。
我猜你要打印的是 MyHashTable x 本身。否则你需要将 return self
附加到 insert()
的定义中,尽管它看起来很奇怪。