字典和哈希表的空间复杂度

Question

字典和哈希表的空间复杂度

6

我对字典和哈希表有些困惑，希望能够澄清一下。假设我有当前的字典以及当前 Python 运行的哈希值输出。

Dict = dict()
print(hash('a'))
print(hash('b'))
print(hash('c'))
Dict['a'] = 1
Dict['b'] = 2
Dict['c'] = 3
print(Dict)

输出了

1714333803
1519074822
1245896149
{'a': 1, 'c': 3, 'b': 2}

据我所知，哈希表就是一个数组，其中哈希是哈希表的索引。例如，'a' 的哈希值为 1714333803，因此我的哈希表索引 1714333803 具有值 'a'。所以我很困惑哈希表有多少个索引，哈希函数如何产生结果？它是否使用模数并具有固定的索引范围？因为给定的字典输出为 {'a':1, 'c':3, 'b':2}，但是可以假设即使输出这个，字典实际上也只是至少包含1714333803个索引的数组，因为那似乎过于浪费空间，仅用来容纳3个元素，并且无值的索引中有什么，在哈希表中呢？

- memelord23

1

你可以动态地调整数组大小，但需要为每个键重新计算哈希值。这个链接看起来很有趣：http://www.laurentluce.com/posts/python-dictionary-implementation/ - SnoozeTime

“索引没有值，空值”是什么意思？是指没有哈希的键吗？还是数组中未填充的位置？ - MisterMiyagi

也可以看看这个视频：https://www.youtube.com/watch?v=C4Kc8xzcA68 - juanpa.arrivillaga

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MisterMiyagi · Accepted Answer

实际上，dict 的大小取决于实现方式，但在您的情况下，它可能是8。那么，这是如何工作的？ dict（或哈希映射）的工作原理是为每个键计算一个数值哈希。例如，在您的情况下，hash("a") == 1714333803。现在，哈希并不直接用作索引。相反，它被映射到字典的大小。

一个简单的方法是取模运算符 (%)。假设您的 dict 大小为8。那么 hash("a") % 8 == 1714333803 % 8 == 3。所以您的项实际上在第4个位置。通过查找算法的构造，没有任何项可以在数组外部具有索引。

这里还有一些更复杂的事情，例如哈希冲突。例如，如果另一项的哈希值为 98499，则它也映射到 3。在这种情况下，有冲突解决策略会选择一个不同的索引。它们大多试图均匀地沿着数组行走。

那么，为什么你的dict大小是8？因为这是Python中的默认大小（default size in python）。一旦你的dict变得太小，它就必须被重新调整大小。与数组不同，这是在dict实际上还没有填满时完成的 - 也就是说，在填充到三分之二时完成。这样做是为了减少哈希冲突 - 如果你的dict已经填满了99％，那么碰撞几乎是肯定的。对于大小为8的dict，您需要输入5-6个项目才能使其调整大小，即将其容量翻倍至16。

请注意，CPython 3.6+和长期使用的PyPy在dict中使用了两阶段数据结构。第一阶段是哈希表，但第二阶段不是。这将键映射（第一阶段）和数据存储（第二阶段）分开。稀疏的第一阶段提供了紧密打包的第二阶段的索引：

# based on Raymond Hettingers mail on python-dev
# the key mapping, using a hashtable
# indices[hash(key) % length] => data index
indices =  [None, None, None, 0, None, 2, 1, None]

# the data storage, packed in insertion order
# entries[index] => hash(key), key, value
entries =  [[1714333803, 'a', 1],
            [1519074822, 'b', 2],
            [1245896149, 'c', 3]]

这种方案在查找时算法更加复杂（因为需要间接寻址），但在迭代时更简单（直接对数据存储进行操作），并且更节省内存。只有索引表是稀疏的，需要过度尺寸。数据存储的大小恰好符合要求，除非删除了项目。