Python2和Python3字典底层原理

核心载体：哈希表（Hash Table），字典本质就是封装好的哈希表，利用哈希函数实现O（1）快速查找

一、Python2字典底层结构

开放寻址法 + 固定结构Entry

1.存储单元Entry结构

Entry 数组就是哈希桶数组

哈希表底层主体是一维数组（哈希数组），数组里的每一个下标位置，就是一个 bucket（哈希桶 / 槽位）

2.冲突解决方式：开放寻址法（线性探测）

①根据 hash 算出桶下标i = hash % 桶总长度

②如果桶 i 为空：直接存入 Entry

③如果桶 i 被占用（冲突）：i = (i+1) % 容量，向后依次找空位（线性探测）

3.扩容规则（根据具体版本而定）

扩容后桶数量翻倍，所有 key 重新计算哈希、重新安放位置

4.Python2字典缺陷

字典有序性无法保证， 扩容、新增元素后，Entry 存放位置会打乱，遍历顺序随机

5.删除机制

开放寻址不能直接清空桶， 如果直接删除 Entry，探测链条断裂，后续 key 找不到

解决方案：

设置哑标记（dummy），标记这个位置曾经有元素、现在被删除，可以写入新数据，但查找时不停止

二、Python3.6+

底层做结构拆分，两套数组：

1、哈希桶数组（indices 索引数组）：只存下标数字（很小的整数数组，节省内存）
2、Entry 实体数组（entries）：顺序保存真正的 hash、key、value

内存大幅节约：indices 只存整数，不再存完整 Entry
entries 数组按照插入顺序追加写入