我一直在学习Python中的数据结构，并创建了一个简单的字典实现，如下所示。虽然这个实现最终是无用的（可以使用
这个实现选择了一个初始大小为11的值。
我的问题是：从哈希函数计算出的哈希值取决于
hash()而不是创建哈希函数等），但我对它们如何组合在一起感到很有兴趣。这个实现选择了一个初始大小为11的值。
self.capacity跟踪剩余的空闲插槽数量。添加（键，值）对时，它会减少1，一旦减少到0，每次需要新插槽时都会触发创建一个新插槽。我的问题是：从哈希函数计算出的哈希值取决于
len(self.slots)，但是当我向字典添加更多空间时，此值会不断增加。我尝试使用初始大小（11）来计算哈希函数，但是一旦字典尝试添加第12个（键，值）对，程序似乎就会卡住。这似乎表明哈希函数需要基于表的大小，并且为了继续添加元素，我需要能够增加表的大小。这引出了以下问题：
- 字典是否必须初始化为固定长度并保持该长度？如果不是，则增加元素的首选方法是什么？
- 如果字典的长度可以更改，则哈希函数应该构造为不使用字典大小吗？如何确保值仍将减少到表插槽范围内的值，而不是通过模表大小进行减少？
class HashTable:
def __init__(self):
self.size = 11
self.capacity = self.size
self.slots = [None] * self.size
self.data = [None] * self.size
def hashfunction(self, key, size):
return key%size
def rehash(self, oldhash, size):
return (oldhash+1)%size
def put(self, key, value):
hashvalue = self.hashfunction(key,len(self.slots))
if self.capacity < 1:
self.slots += [None]
self.data += [None]
self.capacity += 1
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = value
self.capacity -= 1
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data
else:
rehashed = self.rehash(hashvalue, len(self.slots))
while self.slots[rehashed] != None and self.slots[rehashed] != key:
rehashed = self.rehash(rehashed, len(self.slots))
if self.slots[rehashed] == None:
self.slots[rehashed] = key
self.data[rehashed] = value
self.capacity -= 1
else:
self.data[rehashed] = value
def get(self, key):
startslot = self.hashfunction(key, len(self.slots))
data = None
found = False
stop = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
data = self.data[key]
found = True
else:
position = self.rehash(position, len(self.slots))
if position == startslot:
stop = True
return data
def __delitem__(self, key):
hashvalue = self.hashfunction(key, len(self.slots))
if self.slots[hashvalue] == key:
self.slots[hashvalue] = None
self.data[hashvalue] = None
else:
rehashed = self.hashfunction(hashvalue, len(self.slots))
while self.slots[rehashed] != key:
rehashed = self.hashfunction(rehashed, len(self.slots))
if self.slots[rehashed] == key:
self.slots[rehashed] == None
self.data[rehashed] == None
def __contains__(self, key):
return key in self.slots
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
self.put(key, value)