python—dict使用总结和思考
在python中，dict和list是两种常见数据类型，dict用于内容空间足够、依据值快速检索的场景，list用于内存空间有限、根据下标快速检索的场景。
使用场景：
List：类似于C中的array数组，数据存储在一段连续内存空间中；根据值查询时候，需要从头到尾逐一遍历，复杂度O(N)。根据索引index查询时候，直接做索引index偏移，复杂度O(1)。
Dict：在python底层实现为可变哈希表，本质也可以看做List，区别在于List的存放地址按照先后顺序得到，而Dict的存放地址需要根据哈希函数+哈希碰撞得到。
原理说明：
List：（1）python底层实现为一个长度可变的数组，数组中存放的是每个元素的索引index，根据索引查询不受List长度和所存放的元素影响。（2）对于频繁的append和insert操作，CPython会额外进行一些技巧，比如频繁append时候会额外分配比实际需要大一些的空间，避免频繁开辟空间。
Dict：（1）可变哈希表，key通过hash函数映射为哈希值，哈希值进一步映射到哈希表大小size的位置index上，value的地址就存放在index所对应的空间上。（2）说明：Dict中的key必须是可哈希（python中不可变数据都是可哈希的，而可变数据则不可哈希），原因是一旦key可变，key发生变化之后，则无法根据变化后的新key值查询到value，也无法查询到旧key值对应的value值。（3）哈希表的内容：哈希表一行记录2个数据：key的引用和value的引用。（4）python实现，将key哈希得到哈希值之后，只是用哈希值末尾几位计算哈希表存放位置，在哈希表较拥挤触发哈希扩容之后，会增大哈希值的末尾几位。（5）cpython的哈希函数为：hash("key值")&*(2^k-1)【等价于hash("key值")%(k+1)】
注意点：
1、使用List，根据value检索会是O(N)时间复杂度，建议下标index检索数据。
2、使用Dict，根据key检索value虽然会很快，但会占用更多空间，因为哈希表会至少空出1/3的空间，insert操作会在哈希表大小达到2/3触发扩容操作。
3、底层数据存放时候，List是按操作先后顺序存放，而Dict会按照key的哈希值存放，实际value会无序存放。
4、数据要想能哈希，需要能调用python内置的hash()方法和__eq__()【数值相等性检测】方法。
常见问题（个人理解，欢迎大神指出错误）：
1、当初始化一个非空dict时，python底层进行了哪些过程？
答：
step1：开辟一段连续的内存空间用于哈希表操作。
step2：计算各个key的哈希值，再根据哈希值计算value在哈希表中的存放位置，中间可能会遇到哈希冲突和哈希表扩容。
step3：为value开辟内容空间，将具体值存放进去。
step4：将value值所在内存空间的地址存放到哈希表的相应位置空间上。
step5：将哈希表所在内存空间的地址存放到字段变量所在的空间上。
2、为什么说Dict的元素是无序存放？
答：key的哈希计算的结果无序，哈希冲突导致无序，哈希表扩容重新哈希导致无序。
3、dict进行insert时候，如何解决哈希冲突？
答：哈希冲突（碰撞）可以采用线性寻址以及其他的非线性寻址解决（伪随机探测）。
4、dict在扩容时候，如何解决扩容操作？
答：哈希表始终维持1/3的空表元（哈希表的一行称为表元，也叫做bucket），在哈希表的表元数目达到2/3时候，会启动自动扩容操作：分配一块更大的连续内存空间用以存放哈希表，而旧哈希表数据经重新哈希（在冲突或者碰撞中使用某种hash函数重新）会存到新哈希表中。
5、什么是哈希？
答：
（1）哈希是一种数据（信息）压缩编码技术，将数据（信息）以统一的格式进行编码为“指纹”（哈希值，哈希值通常比原始值长度更短），这种指纹可以对原始数据（信息）隐藏和保护，比如不论数字还是字符串。哈希之后得到的哈希值都是数字。
（2）常用哈希函数形式：hash("key值") % k，其中k是哈希表的长度，哈希之后的结果是0到k-1之间的数值。
（3）目的：通过哈希操作将原始值统一编码+打乱，尽可能均匀映射、分布到另一个区间上。
6、什么是哈希表？
答：哈希表本质是一个数组，内存空间连续分配，而且可以适时动态分配。数据元素经哈希函数计算（一般是模运算后取余数）后得到哈希表的某个bucket位置，数据原始的地址便可以存放到指定位置，遇到冲突即通过哈希冲突重新计算位置；当哈希表表元数目达到临界值时，则进行扩容处理。
7、数据存放在list或者dict中时候，实际数据是如何存放的？
答：不管是List还是Dict，数据值本身都是单独分配空间存放，数据值所在空间地址则存放到List或者Dict相应的地址空间。
8、为什么dict的key需要不可变？
答：一旦key可变，当key变化之后，key的哈希值也会变化，这时使用key变量则无法获取到value，同时因为key变化了，也无法知晓旧的哈希值。
8、哈希表扩容时候，如何合理扩容？
参考：链接4
-- over --
参考资料：
1、https://docs.python.org/3.5/faq/design.html#how-are-lists-implemented
2、https://docs.python.org/3.5/library/functions.html#hash
3、https://blog.****.net/lovebaby859450415/article/details/79620715
4、https://blog.****.net/qq_27576655/article/details/85949183
5、https://www.jianshu.com/p/68db5cff4872
6、https://blog.****.net/qq_42815145/article/details/91353624
7、https://www.cnblogs.com/gl1573/archive/2018/10/09/9758941.html
8、https://www.cnblogs.com/yc3110/p/10451431.html
9、https://blog.****.net/junjunba2689/article/details/82814166【仔细看看】
10、https://blog.****.net/siyue0211/article/details/80560783?utm_source=copy