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 存储
使用散列表进行存储
-
使用开放定址法处理冲突
2.1 插入, 发生冲突, 通过二次探测算法, 寻找下一个位置, 直到找到可用位置, 放入(形成一条冲突探测链)
2.2 查找, 需要遍历冲突探测链
2.3 删除, 如果对象在探测链上, 不能直接删除, 否则会破坏整个结构(所以不是真的删)，置标志位？？？
