我正在研究哈希表,我对这个来自教科书的用 Python 编写的哈希表实现有点困惑。我理解所有这些,除了在 addEntry() 方法内部有一个 for 循环,如果 hashBucket[i][0] = 则执行
我对它的作用有点困惑。hashBucket[i] = (dictKey, dictVal)
= dictKey
class intDict(object):
def __init__(self, numBuckets):
self.buckets = []
self.numBuckets = numBuckets
for i in range(numBuckets):
self.buckets.append([])
def addEntry(self, dictKey, dictVal):
hashBucket = self.buckets[dictKey%self.numBuckets]
for i in range(len(hashBucket)):
if hashBucket[i][0] == dictKey:
hashBucket[i] = (dictKey, dictVal)
return
hashBucket.append((dictKey, dictVal))
def getValue(self, dictKey):
hashBucket = self.buckets[dictKey%self.numBuckets]
for e in hashBucket:
if e[0] == dictKey:
return e[1]
return None
def __str__(self):
result = '{'
for b in self.buckets:
for e in b:
result = result + str(e[0]) + ':' + str(e[1]) + ','
return result[:-1] + '}'
最佳答案
退后一步,考虑一下哈希表。您只有一个存储桶数组,而您获取索引来确定您将在给定键下查看哪个存储桶的方式基于某种哈希函数 f()
。想象一下,您有无限数量的 key ,但 f()
只能产生大约 20 亿个唯一的哈希值。鸽子洞原则指出,如果您有 n 个桶和 n+1 个要放入桶中的物体,那么至少 个桶将包含多个对象。您可以想象最坏的情况,f()
是一个糟糕的哈希函数,我们将所有内容放在同一个存储桶中。
确实,对于无限大的键集和有限的哈希集,没有办法保证哈希表不会发生键冲突。那么,为什么会这样呢?
for i in range(len(hashBucket)):
if hashBucket[i][0] == dictKey:
hashBucket[i] = (dictKey, dictVal)
return
这考虑了同一存储桶中可能存在两个或多个 key 的可能性。我们不仅要查找哈希值的索引,而且还必须遍历该存储桶中的所有值以确定它是否是我们要查找的值。如果是,我们还需要以某种方式用 key 存储该新值。您仍然需要确定键来确定键相等性(因为您不能相信哈希会这样做),并且您需要值来使数据结构有值(value),因此 (key, value)
元组。
关于python - 了解哈希表的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59798071/