了解哈希的实现 table

Question

我正在研究散列 tables，我对用 Python 编写的散列 table 实现有点困惑，它来自教科书。除了在 addEntry() 方法内部有一个 for 循环之外，我了解所有这一切 hashBucket[i] = (dictKey, dictVal) if 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

退一步，考虑一个散列table。您只有一个存储桶数组，并且您可以获得索引以确定在给定键的情况下您将查看哪个存储桶的方式是基于某种哈希函数 f()。想象一下，您有无限数量的键，但 f() 只能产生大约 20 亿个唯一哈希值。鸽子洞原则指出，如果你有 n 个桶和 n+1 个要放入桶中的对象，那么至少其中一个桶将包含多个对象。您可以想象一个最坏的情况，即 f() 是一个糟糕的哈希函数，我们将所有内容都放在同一个桶中。

真的，对于无限大的键集和有限的哈希集，没有办法保证散列 table 不会发生键冲突。那么，这是为什么？

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

这说明了同一个存储桶中可能存在两个或更多键的可能性。我们不仅要找到散列值的索引，而且必须遍历该桶中的所有值以确定它是否是我们要查找的值。如果是，我们还需要以某种方式使用键存储该新值。您仍然需要确定密钥以确定密钥相等性（因为您不能相信散列这样做），并且您需要该值来使数据结构有价值，因此 (key, value) 元组。

了解哈希的实现 table

Understand implementation of a hash table

python

algorithm

hashtable