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

有人知道python的内置字典类型是如何实现的吗?我的理解是它是某种哈希表，但我还没有找到任何确定的答案。

130332 次浏览
小开

Python字典使用开放寻址 (漂亮代码中的引用)

正如维基百科所指出的，NB ! 开放寻址，也就是闭散列，不应该与它的反义词开散列!混淆

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

小开

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

  • Python字典被实现为哈希表。

  • 哈希表必须允许哈希碰撞，即即使两个不同的键具有相同的哈希值，表的实现也必须有一个策略来明确地插入和检索键和值对。

  • Python dict使用开放寻址来解决哈希冲突(下面解释)(参见dictobject.c: 296 - 297)。

  • Python哈希表只是一个连续的内存块(有点像一个数组，所以你可以通过索引进行O(1)查找)。

  • 表中的每个槽可以存储一个且只能存储一个条目。这很重要。

  • 表中的每个条目实际上是三个值的组合:这是作为C结构体实现的(参见dictobject.h: 51-56)。

  • 下图是Python哈希表的逻辑表示形式。在下面的图中，左边的0, 1, ..., i, ...是哈希表中槽的索引(它们只是为了说明目的，显然不会与表一起存储!)

      # Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
i|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
n|      ...        |
-+-----------------+
  • 当一个新的字典被初始化时，它以8 槽开始。(见dictobject.h: 49)

  • 当向表中添加条目时，我们从某个槽i开始，它基于键的哈希值。CPython最初使用i = hash(key) & mask(这里是mask = PyDictMINSIZE - 1，但这并不重要)。只需要注意，被检查的初始槽i取决于键的哈希。

  • 如果该槽位为空，则将该条目添加到该槽位(通过条目，我的意思是<hash|key|value>)。但如果那个位置被占用了怎么办!?很可能是因为另一个条目具有相同的哈希(哈希冲突!)

  • 如果槽已被占用，CPython(甚至是PyPy)将槽中条目的哈希和键(这里的比较指的是==比较，而不是is比较)与当前要插入的条目的哈希和键(dictobject.c: 337344 - 345)分别进行比较。如果这两个匹配，则认为该条目已经存在，放弃并移动到下一个要插入的条目。如果哈希或键不匹配，则启动探索。

  • 探测仅仅意味着它逐个槽搜索槽以找到空槽。从技术上讲，我们可以一个接一个地i+1, i+2, ...，并使用第一个可用的(这是线性探测)。但是由于评论中漂亮解释的原因(参见dictobject.c: 33 - 126)， CPython使用随机调查。在随机探测中，以伪随机顺序选择下一个插槽。条目被添加到第一个空槽中。对于本文的讨论，用于选择下一个插槽的实际算法并不真正重要(探测算法请参阅dictobject.c: 33 - 126)。重要的是一直探测这些槽，直到找到第一个空槽。

  • 同样的事情也发生在查找中，只是从初始槽i开始(其中i取决于键的哈希值)。如果哈希和键都不匹配插槽中的条目，则开始探测，直到找到匹配的插槽。如果所有槽位都已耗尽，则报告失败。

  • BTW，如果dict满了三分之二，它将被调整大小。这避免了查找速度变慢。(见dictobject.h: 64 - 65)

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

小开

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

以下是短期课程:

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

    有序方面在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个字节。

    这将占用大量空间，但是查找时间是相当稳定的。键比较算法是计算哈希，到达预期位置，比较键的id，如果它们是相同的对象，它们是相等的。如果不是，则比较哈希值，如果它们不相同，则它们不相等。否则，最后比较是否相等的键，如果相等，则返回值。最终的相等比较可能相当慢，但早期的检查通常会缩短最终的比较，使查找非常快。

    碰撞会降低速度，理论上攻击者可以使用哈希碰撞来执行拒绝服务攻击，因此我们随机化了哈希函数的初始化，以便它为每个新的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__。为了得到这个行为，我相信你需要在实例化你的下一个对象(参见PEP 412)之前完成填充你的__dict__。这意味着你应该在__init__或__new__中分配所有属性，否则你可能无法节省空间。

    然而，如果你在执行__init__时知道你的所有属性，你也可以为你的对象提供__slots__，并保证根本没有创建__dict__(如果在父类中不可用)，甚至允许__dict__，但保证你预期的属性无论如何都存储在插槽中。有关__slots__， 点击这里查看我的答案的更多信息。

    参见:


提交答案