在C++的STL中,map是一种关联容器,采用红黑树的方式,其搜索效率大约为O(logN),以2为底。但是在python中,dict采用的则是散列表,有名哈希表,虽然python中的dict也是关联容器,其搜索效率为O(1)。散列表有一个索引,当散列表的装载率为2/3以上时,散列冲突的概率非常大,因此在python中,使用开链法进行探测序列,防止出现散列冲突。
我们把关联容器的一对键值成为entry,python中一个entry的定义如下:
[code lang=”C”]
typedef struct {
/* Cached hash code of me_key. Note that hash codes are C longs.
* We have to use Py_ssize_t instead because dict_popitem() abuses
* me_hash to hold a search finger.
*/
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
[/code]
从代码中可以看出,PyDictObject中其实存放的就是PyObject*的指针,entry三种状态,Unused态,Active态,Dummy态。当me_key和me_value都为NULL时,处于Unused态,键值存在时为Active态,键值删除时为处于Dummy态,如下图所示:
关联容器的实现如下:
当容器中元素不超过8个时,不会在开辟空间,反之则会像list那样在开辟另外的内存空间。具体如下图所示:
PyDictObject和其他的python对象一样,都有一个对象缓冲池,这一点,dict和list非常像,都是当一个容器的元素全部清空之后只是将ma_table指针所指的内存释放掉,并不是将整个容器对象释放掉。
dict的操作中,无论是插入还是删除,内存都会发生位置变化,这个和list略有一点点不同。
OK,讲完了。