Python 字典对象实现

2017-01-08 Sunday     python

在 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]

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

typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

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



如果喜欢这里的文章,而且又不差钱的话,欢迎打赏个早餐 ^_^


About This Blog

Recent Posts

Categories

Related Links

  • RTEMS
    RTEMS
  • GNU
  • Linux Kernel
  • Arduino

Search


This Site was built by Jin Yang, generated with Jekyll, and hosted on GitHub Pages
©2013-2018 – Jin Yang