Python字典底层是如何构建和操作的？

本文共计1012个文字，预计阅读时间需要5分钟。

前言：上次我们分享了列表的底层原理，今天我们继续分享另一个常用的Python数据结构——字典。

字典的键值对，可以让我们的数据查询、添加和删除变得非常轻松。下面我们来具体看看：

1. 字典的键值对，键可以是任何不可变类型，如数字、字符串、元组等。

2.字典的值可以是任意类型。

3.通过键值对，我们可以轻松实现数据的查询、添加和删除。

举例来说：

python

创建一个字典my_dict={'name': 'Alice', 'age': 25}

查询print(my_dict['name']) # 输出：Alice

添加my_dict['city']='New York'print(my_dict) # 输出：{'name': 'Alice', 'age': 25, 'city': 'New York'}

删除del my_dict['age']print(my_dict) # 输出：{'name': 'Alice', 'city': 'New York'}

以上就是字典的基本用法，希望对大家有所帮助。

前言

上次我们分享了列表的底层原理，今天我们继续分享另外一个常用的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函数，又是怎么解决哈希冲突和扩容的，这些就留给读者了，今天的分享就到这了，我们下期再见~