在 Python 中有一个字典，可以看作是一个 Key Value 对，其代码是通过哈希表实现，也就是说，字典是一个数组，而数组的索引是键经过哈希函数处理后得到的。

Python 字典是用哈希表 (hash table) 实现，哈希表是一个数组，它的索引是对键运用哈希函数计算求得的。

这里简单结合 Python 中 Hash 函数的实现。

字典使用

一个好的哈希函数会将冲突数量降到最小，将各个值均匀分布到数组中，不过，对于 Python 中的哈希函数 (主要用于字符串和整数) 很常规，冲突时采用开放寻址法，相比于链表来说，其 CPU Cache 的命中率更高。

如下是经常的使用方法。

----- 创建初始化字典对象
info = {"name" : "foobar", "gender": "male"}
info = dict(name = 'foobar', gender = 'male')

----- 对于第二种方式，在如下场景时可能会出现隐藏的bug
key = 'name'
info = { key :'foobar'}     # {'name':'foobar'}
info = dict(key = 'foobar') # {'key': 'foobar'}

----- 可以通过fromkeys函数进行初始化，值默认是None，也可以通过第二个参数指定默认值
info = {}.fromkeys(['name', 'gender'])              # {'gender' : None, 'name' : None}
info = dict().fromkeys(['name', 'gender'])          # {'gender' : None, 'name' : None}
info = {}.fromkeys(['name', 'gender'], 'invalid')   # {'gender' : 'invalid', 'name' : 'invalid'}

----- 获取值
print info['name']                 # 不存在时会触发KeyError异常
print info.get('name')             # 不存在返回None而非异常
print info.get('notexist', 'oops') # 不存在时返回指定的默认值

----- 更新、添加、删除
info['name'] = 'kidding'
info.update({'name':'kidding', 'gender':'female'})
info.update(name='kidding', blog='female')
del info['name']                   # 或者info.pop('name')

d.keys()
for key, value in info.items():
    print key, ':',  value

如上，key 可以是 int 和 string 的混合。

setdefault

Python 地址中有一个 setdefault 函数，主要是用于获取信息，如果获取不到就按照它的参数设置该值。

a = { "key": "hello world" }
a.setdefault("key", "456"))   # 因为之前已经设置了key对应的值，此时不会设置

a.setdefault("key_sth", "123"))   # 之前没有设置，此时会设置

源码解析

实际上，计算的 Hash 值，可以通过如下的函数进行计算。

>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-6456208310023038713, -6456208310023038716, -6456208310023038715, -6456208310023038718]

Entry

准确来说，是 CPython 中的实现，其对应的结构体如下。

typedef struct {
	Py_ssize_t me_hash; // 缓存me_key的hash值，防止每次查询都要计算
	PyObject *me_key;
	PyObject *me_value;
} PyDictEntry;

每个 PyDictEntry 包含了三种状态：

Unused me_key == me_value == NULL 初始状态。
Active me_key != NULL and me_key != dummy and me_value != NULL 插入元素后就成了 Active 状态，这是 me_value 唯一不为 NULL 的情况，删除元素时 Active 状态刻转换成 Dummy 状态。
Dummy me_key == dummy and me_value == NULL dummy 实际上一个 PyStringObject 对象，仅作为指示标志。

Dummy 的元素可以在插入元素的时候将它变成 Active ，但它不能再变成 Unused 。

Why Dummy

为什么 entry 有 Dummy 状态呢？

在开放寻址法中，如果某元素经过哈希计算应该插入到 A 处，但是此时 A 处有元素的，通过探测函数计算得到下一个位置 B，仍然有元素，直到找到位置 C 为止。

此时 ABC 构成了探测链，查找元素时如果 hash 值相同，那么也是顺着这条探测链不断往后找，当删除探测链中的某个元素时，比如 B，如果直接把 B 从哈希表中移除，即变成 Unused 状态，那么 C 就不可能再找到了，因为 AC 之间出现了断裂的现象。

正是如此才出现了第三种状态 Dummy，这是一种类似的伪删除方式，保证探测链的连续性。

Dict

struct _dictobject {
	PyObject_HEAD
	Py_ssize_t ma_fill;          // Active+Dummy
	Py_ssize_t ma_used;          // Active
	Py_ssize_t ma_mask;          // 总共有ma_mask+1个slots，可以通过key_hash&ma_mask得到对应的slot
	PyDictEntry *ma_table;       // 保存的hash表
	PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
	PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

参考

详细可以参考深入 Python 字典的内部实现以及其原文 Python dictionary implementation 。

Python 字典对象实现

字典使用 #

setdefault #

源码解析 #

Entry #

Why Dummy #

Dict #

参考 #