前言
上次我们分享了列表的底层原理，今天我们继续分享另外一个常用的Python数据结构，字典。字典的键值对，可以让我们可以很轻松的完成数据查询、添加和删除，说到键值对，我又不经意想到了散列表（哈希表）。
今天可以明确的告诉你，字典就是用到了哈希表的思想，全剧终。开玩笑哈，那废话不多说，开整。
哈希表
在说字典的具体实现之前，我们还是简单介绍下哈希表的原理，大可放心，我尽量讲的通俗些。
之前我们介绍过数组，通过索引我们能快速获取元素值。哈希表也是一样，但是数组的索引是0到n-1，但是哈希表是键值对，所以，哈希函数来了。
我们把键通过哈希函数转换为哈希值（这样就可以是个整数），然后将对应的值存在数组中这个哈希值索引的位置上。
dict={}dict[name]=lisi
当然哈希表没有这么简单，还会涉及哈希冲突，扩容等等问题，这里就不过多介绍了。
字典
不会吧，都年了，不会还有人说字典是无序的吧。
确实，在python3.6之前，字典是无序的，但是在python3.7开始，字典就有序了，这有序无序，恰恰就说明字典的底层发生了变化，我们来一探究竟。
无序
在python3.6之前，哈希表结构如下所示，每一行存储了哈希值（hash）、键（key）、值（value）3个元素。
table=[[--,--,--],[hash,key,value],[--,--,--],[--,--,--],[hash,key,value],]
例如dict[name]=lisi，假设name计算的hash值为1，则存储如下。
dict=[[--,--,--],[1,name,lisi],[--,--,--],[--,--,--],[--,--,--],]
所以我们没办法保证下一个插入的键值对能保证在1的后面，hash值计算出来是多少，就存储在什么位置，没法做到有序，而却这种方法也很容易让哈希表稀疏，占用大量内存。
有序
有序的字典把索引和哈希值、键、值单独分开，如下所示。
indices=[None,None,index,]table=[[hash0,key0,value0],[hash1,key1,value1],[hash2,key2,value2]]
所以前面的例子在这里保存就是这样的。
indices=[None,0,None]table=[[1,name,lisi],]
这样确保了有序。
总结
当然，Python具体用的是什么hash函数，又是怎么解决哈希冲突和扩容的，这些就留给读者了，今天的分享就到这了，我们下期再见~
*声明：本文于网络整理，版权归原作者所有，如来源信息有误或侵犯权益，请联系我们删除或授权事宜。