作者:金瑞期货秦臻 | 来源:互联网 | 2023-02-10 10:51
我一直在研究python中的数据结构,我创建了一个简单的字典实现,如下所示.虽然这个实现最终没用(可能只是使用hash()
而不是创建哈希函数等),但我对它们如何组合起来的细节感兴趣.
此实现选择起始大小11.记录self.capacity
剩余的空闲时隙数.当添加(key,value)对时,它会减1,一旦它达到0,它就会在每次需要时触发一个新的槽.
我的问题是:从散列函数计算的散列值依赖于len(self.slots)
,但是当我向字典添加更多空间时,此值会不断增加.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)
Martijn Piet..
6
您需要将哈希和表格大小分开.哈希应仅基于密钥,而不是大小.每个键值条目存储以下信息:
钥匙
哈希 - 从密钥派生的常量值.确保它有呼吸以避免太多碰撞.
价值
您根据表大小和哈希选择一个插槽:
slot = hash % tablesize
然后,当您当前表中的空间不足时,生成一个新表(比如,大小增加一倍),以适应您不断增长的数据集,并重新绘制所有内容.您已经缓存了哈希值,您需要做的就是获取每个(key, hash, value)
元组并使用上面的公式重新计算新的槽,现在使用更大的表格.
你还必须决定如何处理碰撞 ; 给出当前表大小的两个哈希最终在同一个槽中.Python dict
使用开放式寻址,其中哈希以可重现的方式被"扰乱",直到找到另一个空槽.
您可能希望研究Python dict
源代码以了解它们是如何执行此操作的,请参阅有关如何处理冲突的详尽注释.您还可以观看此PyCon演示文稿,其中Brandon Rhodes使用一些非常有启发性的图形解释所有这些细节.或者你可以拿起一本美丽的代码,其中有一章关于Python的dict
实现.
1> Martijn Piet..:
您需要将哈希和表格大小分开.哈希应仅基于密钥,而不是大小.每个键值条目存储以下信息:
钥匙
哈希 - 从密钥派生的常量值.确保它有呼吸以避免太多碰撞.
价值
您根据表大小和哈希选择一个插槽:
slot = hash % tablesize
然后,当您当前表中的空间不足时,生成一个新表(比如,大小增加一倍),以适应您不断增长的数据集,并重新绘制所有内容.您已经缓存了哈希值,您需要做的就是获取每个(key, hash, value)
元组并使用上面的公式重新计算新的槽,现在使用更大的表格.
你还必须决定如何处理碰撞 ; 给出当前表大小的两个哈希最终在同一个槽中.Python dict
使用开放式寻址,其中哈希以可重现的方式被"扰乱",直到找到另一个空槽.
您可能希望研究Python dict
源代码以了解它们是如何执行此操作的,请参阅有关如何处理冲突的详尽注释.您还可以观看此PyCon演示文稿,其中Brandon Rhodes使用一些非常有启发性的图形解释所有这些细节.或者你可以拿起一本美丽的代码,其中有一章关于Python的dict
实现.