Python的内建字典是如何实现的?

以下是短期课程:

它们是哈希表。(参见下面的Python实现细节。) 从Python 3.6开始，一种新的布局和算法使它们按键插入和排序占用更少的空间，在性能上几乎没有成本。当字典共享密钥(在特殊情况下)时，另一种优化节省了空间。

有序方面在Python 3.6中是非正式的(以便其他实现有机会跟上)，但在Python 3.7中是正式的。

Python的字典是哈希表

很长一段时间，它都是这样工作的。Python将预先分配8个空行，并使用散列来确定键值对的位置。例如，如果键的哈希值以001结尾，它将把它放在1(即第2个)索引中(如下面的例子所示)。

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

在64位架构中，每行占用24个字节，在32位架构中占用12个字节。(请注意，列标题只是我们这里的标签——它们实际上并不存在于内存中。)

如果散列的结尾与先前存在的键的散列相同，则这是一个碰撞，然后它将键-值对固定在不同的位置。

存储5个键值后，当添加另一个键值对时，哈希冲突的概率太大，因此字典的大小增加了一倍。在一个64位进程中，在调整大小之前，我们有72个字节是空的，在调整大小之后，由于10个空行，我们浪费了240个字节。

This takes a lot of space, but the lookup time is fairly constant. The key comparison algorithm is to compute the hash, go to the expected location, compare the key's id - if they're the same object, they're equal. If not then compare the hash values, if they are not the same, they're not equal. Else, then we finally compare keys for equality, and if they are equal, return the value. The final comparison for equality can be quite slow, but the earlier checks usually shortcut the final comparison, making the lookups very quick.

碰撞会降低速度，理论上攻击者可以使用哈希碰撞来执行拒绝服务攻击，因此我们随机化了哈希函数的初始化，以便它为每个新的Python进程计算不同的哈希值。

上面所描述的浪费空间导致我们修改了字典的实现，增加了一个令人兴奋的新特性，现在字典是按插入顺序排列的。

新的紧凑哈希表

相反，我们首先为插入的索引预分配一个数组。

因为我们的第一个键值对在第二个槽中，所以我们像这样索引:

[null, 0, null, null, null, null, null, null]

我们的表只是按照插入顺序填充:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

因此，当我们查找一个键时，我们使用哈希来检查我们期望的位置(在这种情况下，我们直接到数组的索引1)，然后去哈希表中的索引(例如索引0)，检查键是否相等(使用前面描述的相同算法)，如果相等，则返回值。

我们保持了恒定的查找时间，在某些情况下速度略有下降，在另一些情况下速度有所提高，好处是我们在已有的实现上节省了相当多的空间，并且我们保留了插入顺序。唯一浪费的空间是索引数组中的空字节。

Raymond Hettinger于2012年12月在python-dev上引入了这一点。它最终在Python 3.6中加入了CPython。通过插入排序被认为是3.6的一个实现细节，以便让其他Python实现有机会赶上来。

共享密钥

另一个节省空间的优化是共享密钥的实现。因此，我们不再使用占用所有空间的冗余字典，而是使用重用共享键和键的散列的字典。你可以这样想:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

对于64位机器，每个额外字典的每个键最多可以节省16个字节。

自定义对象和替代品的共享密钥

这些共享键字典用于自定义对象的__dict__。为了得到这个行为，我相信你需要在实例化你的下一个对象之前完成你的__dict__填充(见PEP 412)。这意味着你应该在__init__或__new__中分配所有属性，否则你可能无法节省空间。

然而，如果你在执行__init__时知道你的所有属性，你也可以为你的对象提供__slots__，并保证根本不会创建__dict__(如果在父类中不可用)，甚至允许__dict__，但保证你预期的属性无论如何都存储在slots中。有关__slots__的更多信息，请参见我的回答。

参见:

PEP 509—将私有版本添加到dict PEP 468—保留函数中**kwarg的顺序。 PEP 520—保留类属性定义顺序 PyCon 2010: The Might Dictionary - Brandon Rhodes PyCon 2017:词典更强大-布兰登·罗兹 PyCon 2017:现代Python词典汇集了十几个伟大的想法- Raymond Hettinger dicobject . C——CPython在C语言中的实际dict实现。

2017-06-12 21:54:15

Python字典使用Open寻址(在Beautiful代码中引用)

NB !正如维基百科所指出的那样，开放寻址，也就是封闭哈希，不应该与相反的开放哈希混淆!

开放寻址意味着字典使用数组槽，当在字典中获取对象的主位置时，使用“扰动”方案在同一数组中的不同索引处寻找对象的位置，其中对象的哈希值起作用。

2010-06-08 11:00:37

这里是我能把Python字典放在一起的所有东西(可能比任何人都想知道的要多;但答案是全面的)。

Python dictionaries are implemented as hash tables. Hash tables must allow for hash collisions i.e. even if two distinct keys have the same hash value, the table's implementation must have a strategy to insert and retrieve the key and value pairs unambiguously. Python dict uses open addressing to resolve hash collisions (explained below) (see dictobject.c:296-297). Python hash table is just a contiguous block of memory (sort of like an array, so you can do an O(1) lookup by index). Each slot in the table can store one and only one entry. This is important. Each entry in the table is actually a combination of the three values: < hash, key, value >. This is implemented as a C struct (see dictobject.h:51-56). The figure below is a logical representation of a Python hash table. In the figure below, 0, 1, ..., i, ... on the left are indices of the slots in the hash table (they are just for illustrative purposes and are not stored along with the table obviously!). # Logical model of Python Hash table -+-----------------+ 0| <hash|key|value>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+ When a new dict is initialized it starts with 8 slots. (see dictobject.h:49) When adding entries to the table, we start with some slot, i, that is based on the hash of the key. CPython initially uses i = hash(key) & mask (where mask = PyDictMINSIZE - 1, but that's not really important). Just note that the initial slot, i, that is checked depends on the hash of the key. If that slot is empty, the entry is added to the slot (by entry, I mean, <hash|key|value>). But what if that slot is occupied!? Most likely because another entry has the same hash (hash collision!) If the slot is occupied, CPython (and even PyPy) compares the hash AND the key (by compare I mean == comparison not the is comparison) of the entry in the slot against the hash and key of the current entry to be inserted (dictobject.c:337,344-345) respectively. If both match, then it thinks the entry already exists, gives up and moves on to the next entry to be inserted. If either hash or the key don't match, it starts probing. Probing just means it searches the slots by slot to find an empty slot. Technically we could just go one by one, i+1, i+2, ... and use the first available one (that's linear probing). But for reasons explained beautifully in the comments (see dictobject.c:33-126), CPython uses random probing. In random probing, the next slot is picked in a pseudo random order. The entry is added to the first empty slot. For this discussion, the actual algorithm used to pick the next slot is not really important (see dictobject.c:33-126 for the algorithm for probing). What is important is that the slots are probed until first empty slot is found. The same thing happens for lookups, just starts with the initial slot i (where i depends on the hash of the key). If the hash and the key both don't match the entry in the slot, it starts probing, until it finds a slot with a match. If all slots are exhausted, it reports a fail. BTW, the dict will be resized if it is two-thirds full. This avoids slowing down lookups. (see dictobject.h:64-65)

注意:我对Python Dict实现进行了研究，以回答我自己的问题，即一个Dict中的多个条目如何具有相同的散列值。我在这里发布了一个稍微编辑过的版本，因为所有的研究都与这个问题非常相关。