前言
上次我们分享了列表的底层原理，今天我们继续分享另外一个常用的Python数据结构，字典。字典的键值对，可以让我们可以很轻松的完成数据查询、添加和删除，说到键值对，我又不经意想到了散列表（哈希表）。
今天可以明确的告诉你，字典就是用到了哈希表的思想，全剧终。开玩笑哈，那废话不多说，开整。
哈希表
在说字典的具体实现之前，我们还是简单介绍下哈希表的原理，大可放心，我尽量讲的通俗些。
之前我们介绍过数组，通过索引我们能快速获取元素值。哈希表也是一样，但是数组的索引是0到n-1，但是哈希表是键值对，所以，哈希函数来了。
我们把键通过哈希函数转换为哈希值（这样就可以是个整数），然后将对应的值存在数组中这个哈希值索引的位置上。
dict = {}
dict['name'] = 'lisi'
当然哈希表没有这么简单，还会涉及哈希冲突，扩容等等问题，这里就不过多介绍了。
字典
不会吧，都2021年了，不会还有人说字典是无序的吧。
确实，在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函数，又是怎么解决哈希冲突和扩容的，这些就留给读者了，今天的分享就到这了，我们下期再见~
网友评论