如何实现Python的内置词典? [英] How are Python's Built In Dictionaries Implemented?

问题描述

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

Does anyone know how the built in dictionary type for python is implemented? My understanding is that it is some sort of hash table, but I haven't been able to find any sort of definitive answer.

推荐答案

以下是我能够汇总的有关Python字典的所有内容(可能比任何人都想知道的要多；但是答案很全面).

Here is everything about Python dicts that I was able to put together (probably more than anyone would like to know; but the answer is comprehensive).

• Python字典被实现为哈希表.
• 哈希表必须允许哈希冲突，即，即使两个不同的键具有相同的哈希值，该表的实现也必须具有明确插入和检索键和值对的策略.
• Python dict使用开放式寻址解决哈希冲突(如下所述)(请参见 dictobject.h:51- 56 ).

• 下图是Python哈希表的逻辑表示.在下图中，左侧的0, 1, ..., i, ...是哈希表中插槽的索引(它们仅用于说明目的，与表显然没有存储！).

• 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 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|      ...        |
-+-----------------+

初始化新字典时，它以8个 slots 开头. (请参见 dictobject.h:49 )

When a new dict is initialized it starts with 8 slots. (see dictobject.h:49)

注意:我对Python Dict的实现进行了研究，以回应我自己的问题关于字典中可以有多个条目的问题具有相同的哈希值.我在此处发布了对此回复的略作修改的版本，因为所有的研究也都与此问题相关.

NOTE: I did the research on Python Dict implementation in response to my own question about how multiple entries in a dict can have same hash values. I posted a slightly edited version of the response here because all the research is very relevant for this question as well.

这篇关于如何实现Python的内置词典?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！