字典和哈希表空间复杂性

Question

我对字典和哈希表有些困惑，我想澄清一下，假设我有当前的字典和当前运行的python哈希的当前输出。在

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

其输出为

^{pr2}$

所以据我所知，哈希表就是一个数组，其中hash是哈希表的索引。例如，“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。所以你的物品实际上在第四位。通过构造查找算法，没有项可以在数组之外有索引。在

这里还有一些更复杂的事情，比如散列碰撞。例如，如果另一个项具有散列98499，则该散列也映射到3。在这种情况下，有一些冲突解决策略可以选择不同的索引。他们大多尝试大步均匀地行走在阵列中。在

那么，为什么你的dict是8号的？因为那是default size in python。一旦您的dict太小，就必须调整大小。与数组不同的是，这是在dict实际上已满之前完成的，即在two thirds filling处。这样做是为了减少哈希冲突-如果您的dict已满99%，那么实际上可以保证发生碰撞。对于大小为8的dict，在调整大小之前必须输入5-6个条目，即doubles its capacity到16。在

---

注意，CPython 3.6+和{a5}使用two-stage data structure表示{}。第一阶段是哈希表，但第二阶段不是。这将密钥映射（第一阶段）和数据存储（第二阶段）分开。稀疏的第一阶段提供了紧凑的第二阶段的索引：

# 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]]

该方案在算法上对于查找（由于间接寻址）更为复杂，但对于迭代（直接在数据存储上）则不那么复杂，并且更节省内存。只有索引表是稀疏的，需要过大。除非删除项，否则数据存储将完全根据需要而定。在