核心载体哈希表Hash Table字典本质就是封装好的哈希表利用哈希函数实现O1快速查找一、Python2字典底层结构开放寻址法 固定结构Entry1.存储单元Entry结构Entry 数组就是哈希桶数组哈希表底层主体是一维数组哈希数组数组里的每一个下标位置就是一个 bucket哈希桶 / 槽位2.冲突解决方式开放寻址法线性探测①根据 hash 算出桶下标i hash % 桶总长度②如果桶 i 为空直接存入 Entry③如果桶 i 被占用冲突i (i1) % 容量向后依次找空位线性探测3.扩容规则根据具体版本而定扩容后桶数量翻倍所有 key 重新计算哈希、重新安放位置4.Python2字典缺陷字典有序性无法保证 扩容、新增元素后Entry 存放位置会打乱遍历顺序随机5.删除机制开放寻址不能直接清空桶 如果直接删除 Entry探测链条断裂后续 key 找不到解决方案设置哑标记dummy标记这个位置曾经有元素、现在被删除可以写入新数据但查找时不停止二、Python3.6底层做结构拆分两套数组1、哈希桶数组indices 索引数组只存下标数字很小的整数数组节省内存2、Entry 实体数组entries顺序保存真正的 hash、key、value内存大幅节约indices 只存整数不再存完整 Entryentries 数组按照插入顺序追加写入
