1. 深入 Python 列表的内部实现

参考文档

1.1. 列表是一个迭代器。

1.2. 内部

C 结构体。ob_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;


typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

1.3. 申请槽的算法：list_resize() 函数

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
0，4，8，16，25，35，46，58，72，88……

1.4. 操作复杂度

append, pop 复杂度都是O(1) 都是槽的尾部处理，不用查找

insert, remove复杂度都是O(n) 需要调整 槽的index

insert(index, value)

remove(index)

2. 深入 Python 字典的内部实现

参考文章

2.1 内部实现

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

me_hash为me_key的hash值
me_key与me_value都是PyObject指针类型，所以都可以指向Python任何类型

2.2 存储

1. 使用散列表进行存储

2. 使用开放定址法处理冲突

   2.1 插入, 发生冲突, 通过二次探测算法, 寻找下一个位置, 直到找到可用位置, 放入(形成一条冲突探测链)

   2.2 查找, 需要遍历冲突探测链

   2.3 删除, 如果对象在探测链上, 不能直接删除, 否则会破坏整个结构(所以不是真的删)，置标志位？？？