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

Question

我对想澄清的字典和哈希表有些困惑，假设我有当前的字典以及当前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个元素似乎太可笑了，更不用说浪费了多少的空间。同样对于散列表，索引中没有值的内容为null吗？

Answer 1

实际大小dict取决于实现，但是在您的情况下，可能是8。那么，这如何工作？

dict（通常是哈希图）的工作原理是为每个键计算数字哈希。以您的情况hash("a") == 1714333803为例。现在，哈希不再直接用作索引。而是将其映射到字典的大小。

一种简单的方法是取模（%）。假设您的dict尺寸为8。然后hash("a") % 8 == 1714333803 % 8 == 3。因此，您的商品实际上位于第4位。通过查找算法的构造，任何项目都无法在数组外部具有索引。

这里有一些更复杂的事情，例如哈希冲突。例如，如果另一个项目具有哈希值98499，则该哈希值也映射到3。在这种情况下，有一些冲突解决策略可以选择不同的索引。他们大多试图使阵列大步向前走。

那么，为什么您dict的尺码是8？因为那是python中的默认大小。一旦dict尺寸太小，就必须重新调整尺寸。与数组相反，此操作是在数组dict实际满之前完成的，即在三分之二的填充之前完成。这样做是为了减少哈希冲突-如果您dict的硬盘已满99％，则实际上可以保证发生冲突。对于大小为8的字典，在调整大小之前，您必须输入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]]

该方案在算法上因查找而更为复杂（由于间接的原因），而对于迭代（直接在数据存储上）则更为复杂，并且内存效率更高。仅索引表是稀疏的，需要超大。除非删除项目，否则数据存储将完全根据需要存储。