了解哈希表的实现

Question

我正在研究哈希表，我对教科书中用Python编写的哈希表实现有点困惑。除了在addEntry（）方法中有一个for循环执行hashBucket[i] = (dictKey, dictVal)如果hashBucket[i][0] == 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] + '}' 

Answer 1

退一步，考虑一个哈希表。您只需要一个bucket数组，而获取索引以确定给定键将查看哪个bucket的方法是基于一些散列函数，f()。假设你有无限多的键，但是f()只能产生，比如说20亿个唯一的散列。鸽子洞原则指出，如果您有n个桶和n个+1个对象要放入桶中，那么至少一个桶将包含多个对象。您可以想象最坏的情况，即f()是一个糟糕的哈希函数，我们将所有内容都放在同一个桶中

实际上，对于无限大的一组键和有限的一组哈希，无法保证哈希表不会发生键冲突。那么，为什么会这样

for i in range(len(hashBucket)):
    if hashBucket[i][0] == dictKey:
        hashBucket[i] = (dictKey, dictVal)
            return

这就是同一个存储桶中可能存在两个或多个密钥的原因。我们不仅要找到散列值的索引，还必须遍历该bucket中的所有值，以确定它是否是我们正在寻找的值。如果是，我们还需要以某种方式用一个键存储该新值。碰巧，这个实例中的key和dict值存储为(key, value)元组