Python中，字典(dict)是一种非常常用的数据结构，其实现原理是一种哈希表。
哈希表(Hash Table)，也叫散列表，是根据关键码值(Key Value)而直接进行访问的数据结构。哈希表通过把关键码值映射到哈希表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数(Hash Function)，存放记录的数组叫做哈希表(Hash Table)。
Python 3.x 中的哈希表是由一个 dictobject 类来实现的，它定义在文件 Objects/dictobject.c 中，我们可以通过阅读这个文件来了解哈希表的实现细节。
哈希表主要由三个部分组成:
哈希表本身的结构体(PyDictObject)，其成员变量包含：
a. 哈希表的大小(size)：表示哈希表中存储的键值对个数。
b. 元素个数(n_used)：表示哈希表中已经使用的大小。
c. 哈希表的表头(table)：实际存储元素的数组，它的长度必须是 2 的幂次方。
哈希函数: Python使用一种稳定的哈希函数，取模运算的方式让哈希值在0~table长度之间。
碰撞处理
a. 开放寻址：即采用线性探测法，发生冲突后，在哈希表中向后寻找下一个可用的位置。
b. 链接法：如果位置已经被占用，则把该位置的链表指针向后移动，挂接在后面。
Python采用的是链接法，即哈希表数组中的每一个元素都是一个指针，指向一个链表。当冲突发生时，它会把新元素插入到链表的头部。
当我们使用字典时，如果需要新增一个键值对就会发生插入操作，具体插入操作包括以下几个步骤：
计算键的哈希值。
使用哈希函数计算键的索引值。
检查这个索引的位置是否已经有元素。
如果这个位置没有元素，就直接将键值对插入到这个位置。
如果这个位置有元素，可能是跟这个位置对应的链表的第一个位置发生了冲突，我们需要遍历链表，找到要插入的键是否已经存在。
如果键已经存在，就用新的值覆盖旧的值。
如果键不存在，则在链表的头部插入一个新的节点。
当我们使用字典时，如果需要查找一个键是否存在，具体查找操作包括以下几个步骤：
计算键的哈希值。
使用哈希函数计算键的索引值。
检查这个索引的位置是否已经有元素。
如果这个位置没有元素，就表明键不存在。
如果这个位置有元素，可能是跟这个位置对应的链表的第一个位置发生了冲突，我们需要遍历链表，找到要查找的键是否存在。
如果键存在，就返回它的值。
如果键不存在，则返回一个 KeyError 异常。
下面我们通过两个示例来演示哈希表的实现细节。
例如，我们有一个空的字典：
d = {}
我们要向字典中添加键值对 "hello": 1，那么具体流程如下：
计算 "hello" 的哈希值。
使用哈希函数计算 "hello" 的索引值。
检查索引值所在的数组位置是否有元素。
因为这个位置没有元素，所以将键值对 "hello": 1 插入到这个数组位置。
现在字典中已经有一个元素了，所以将 n_used 加 1。
例如，我们有一个字典：
d = {"hello": 1, "world": 2}
我们要查找键 "world" 的值，那么具体流程如下：
计算 "world" 的哈希值。
使用哈希函数计算 "world" 的索引值。
检查索引值所在的数组位置是否有元素。
因为这个位置有元素，所以需要在这个元素对应的链表上查找 "world"。
找到 "world" 元素并返回它的值2。
这就是 Python 哈希表的工作原理，希望对你有所帮助。
本文链接：http://task.lmcjl.com/news/14968.html