python - 了解哈希表的实现

标签 python algorithm hashtable

我正在研究哈希表,我对这个来自教科书的用 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/

相关文章:

c - 使用 C 查找数组中的重复项

algorithm - 是否正在哈希表中搜索不存在 O(n) 的值? (线性探测)

python - 使用 python 3.3 在 Django 1.9 中导入 WeakMethod 错误

python - 初学者 Python 键盘 GUI 设置

python - 如何有效地将运算符应用于两个数组的笛卡尔积?

Python JSON 到 CSV 不起作用

java - 哪个更快——正则表达式匹配还是我自己的匹配函数?

arrays - 通过旋转和反向操作进行数组置换

algorithm - 能用递归解决的问题都能用循环解决吗?

python - 将 python 字典的最坏情况时间复杂度优化为 O(1)