详细说一下你理解的字典底层原理？

Answer 1

字典是 Python 中最通用的数据结构之一。可以将一组唯一的键映射到相应的值。?CPython 使用伪随机探测(pseudo-random probing)的散列表(hashtable)作为字典的底层数据结构。由于这个实现细节，只有可哈希的对象才能作为字典的键。?Python 中所有不可变的内置类型都是可哈希的。可变类型(列表，字典、集合)是不可哈希的，因此不能作为字典的键。?字典的三个基本操作(添加，获取、删除)的平均事件复杂度为 O(1)，但是他们的平摊最坏情况复杂度要高得多，为 O(N)?开放寻址法:在 Python3.6 版本之前字典为无序的，使用开放寻址法实现 hash 数组(散列表);所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个候选位置还是有冲突，那么不断通过探测函数往下找，直到找一个空槽来存放待插入的元素。? hash 数组只用数组一种数据结构存储，继承了数组的优点，对 CPU 缓冲友好，易于序列化。但是对内存并不如拉链法，且冲突的代价更高。当数据量比较小、装载因子(扩容因子)小的时候，适合采用开放寻址法。?拉链法:在 Python3.6 版之后，字典变为有序，底层实现为拉链法;将所有关键词为同义词的记录储存在一个单链表中(称为同义词子表)，在哈希表中只存储同义词子表的头指针，不存在之前开放寻址法的 hash 冲突，遇到冲突直接追加至当前位置链表尾部即可，但是极端情况下，可能冲突都进入同一链表，会导致当前遍历查找元素时间较长。?哈希碰撞(冲突):对进行 hash 运算之后得到的位置进行存储，但已被占用。?扩容因子:当 hash 数组即将达到总大小的 2/3 时，会进行扩容，复制到另外一块更大内存中，常见的扩容因子为 0.75。