在 Python 3.5(含) 以前, 字典是不能保证顺序的, 键值对 A 先插入字典, 键值对 B 后插入字典, 但是当你打印字典的 Keys 列表时, 你会发现 B 可能在 A 的前面.
但是从 Python 3.6 开始, 字典是变成有顺序的了. 你先插入键值对 A, 后插入键值对 B, 那么当你打印 Keys 列表的时候, 你就会发现 B 在 A 的后面.
不仅如此, 从 Python 3.6 开始, 下面的三种遍历操作, 效率要高于 Python 3.5 之前:
for key in 字典
for value in 字典. values()
for key, value in 字典. items()
从 Python 3.6 开始, 字典占用内存空间的大小, 视字典里面键值对的个数, 只有原来的 30%~95%.
Python 3.6 到底对字典做了什么优化呢? 为了说明这个问题, 我们需要先来说一说, 在 Python 3.5(含) 之前, 字典的底层原理.
当我们初始化一个空字典的时候, CPython 的底层会初始化一个二维数组, 这个数组有 8 行, 3 列, 如下面的示意图所示:
- my_dict = {}
- '''
- 此时的内存示意图
- [[---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---]]
- '''
现在, 我们往字典里面添加一个数据:
- my_dict['name'] = 'kingname'
- '''
- 此时的内存示意图
- [[---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [1278649844881305901, 指向 name 的指针, 指向 kingname 的指针],
- [---, ---, ---],
- [---, ---, ---]]
- '''
这里解释一下, 为什么添加了一个键值对以后, 内存变成了这个样子:
首先我们调用 Python 的 hash 函数, 计算 name 这个字符串在当前运行时的 hash 值:
- >>> hash('name')
- 1278649844881305901
特别注意, 我这里强调了『当前运行时』, 这是因为, Python 自带的这个 hash 函数, 和我们传统上认为的 Hash 函数是不一样的. Python 自带的这个 hash 函数计算出来的值, 只能保证在每一个运行时的时候不变, 但是当你关闭 Python 再重新打开, 那么它的值就可能会改变, 如下图所示:
假设在某一个运行时里面, hash('name') 的值为 1278649844881305901. 现在我们要把这个数对 8 取余数:
- >>> 1278649844881305901 % 8
- 5
余数为 5, 那么就把它放在刚刚初始化的二维数组中, 下标为 5 的这一行. 由于 name 和 kingname 是两个字符串, 所以底层 C 语言会使用两个字符串变量存放这两个值, 然后得到他们对应的指针. 于是, 我们这个二维数组下标为 5 的这一行, 第一个值为 name 的 hash 值, 第二个值为 name 这个字符串所在的内存的地址 (指针就是内存地址), 第三个值为 kingname 这个字符串所在的内存的地址.
现在, 我们再来插入两个键值对:
- my_dict['age'] = 26
- my_dict['salary'] = 999999
- '''
- 此时的内存示意图
- [[-4234469173262486640, 指向 salary 的指针, 指向 999999 的指针],
- [1545085610920597121, 执行 age 的指针, 指向 26 的指针],
- [---, ---, ---],
- [---, ---, ---],
- [---, ---, ---],
- [1278649844881305901, 指向 name 的指针, 指向 kingname 的指针],
- [---, ---, ---],
- [---, ---, ---]]
- '''
那么字典怎么读取数据呢? 首先假设我们要读取 age 对应的值.
此时, Python 先计算在当前运行时下面, age 对应的 Hash 值是多少:
- >>> hash('age')
- 1545085610920597121
现在这个 hash 值对 8 取余数:
- >>> 1545085610920597121 % 8
- 1
余数为 1, 那么二维数组里面, 下标为 1 的这一行就是需要的键值对. 直接返回这一行第三个指针对应的内存中的值, 就是 age 对应的值 26.
当你要循环遍历字典的 Key 的时候, Python 底层会遍历这个二维数组, 如果当前行有数据, 那么就返回 Key 指针对应的内存里面的值. 如果当前行没有数据, 那么就跳过. 所以总是会遍历整个二位数组的每一行.
每一行有三列, 每一列占用 8byte 的内存空间, 所以每一行会占用 24byte 的内存空间.
由于 Hash 值取余数以后, 余数可大可小, 所以字典的 Key 并不是按照插入的顺序存放的.
注意, 这里我省略了与本文没有太大关系的两个点:
开放寻址, 当两个不同的 Key, 经过 Hash 以后, 再对 8 取余数, 可能余数会相同. 此时 Python 为了不覆盖之前已有的值, 就会使用开放寻址技术重新寻找一个新的位置存放这个新的键值对.
当字典的键值对数量超过当前数组长度的 2/3 时, 数组会进行扩容, 8 行变成 16 行, 16 行变成 32 行. 长度变了以后, 原来的余数位置也会发生变化, 此时就需要移动原来位置的数据, 导致插入效率变低.
在 Python 3.6 以后, 字典的底层数据结构发生了变化, 现在当你初始化一个空的字典以后, 它在底层是这样的:
- my_dict = {}
- '''
- 此时的内存示意图
- indices = [None, None, None, None, None, None, None, None]
- entries = []
- '''
当你初始化一个字典以后, Python 单独生成了一个长度为 8 的一维数组. 然后又生成了一个空的二维数组.
现在, 我们往字典里面添加一个键值对:
- my_dict['name'] = 'kingname'
- '''
- 此时的内存示意图
- indices = [None, 0, None, None, None, None, None, None]
- entries = [[-5954193068542476671, 指向 name 的指针, 执行 kingname 的指针]]
- '''
为什么内存会变成这个样子呢? 我们来一步一步地看:
在当前运行时, name 这个字符串的 hash 值为 - 5954193068542476671, 这个值对 8 取余数是 1:
- >>> hash('name')
- -5954193068542476671
- >>> hash('name') % 8
- 1
所以, 我们把 indices 这个一维数组里面, 下标为 1 的位置修改为 0.
这里的 0 是什么意思呢? 0 是二位数组 entries 的索引. 现在 entries 里面只有一行, 就是我们刚刚添加的这个键值对的三个数据: name 的 hash 值, 指向 name 的指针和指向 kinganme 的指针. 所以 indices 里面填写的数字 0, 就是刚刚我们插入的这个键值对的数据在二位数组里面的行索引.
好, 现在我们再来插入两条数据:
- my_dict['address'] = 'xxx'
- my_dict['salary'] = 999999
- '''
- 此时的内存示意图
- indices = [1, 0, None, None, None, None, 2, None]
- entries = [[-5954193068542476671, 指向 name 的指针, 执行 kingname 的指针],
- [9043074951938101872, 指向 address 的指针, 指向 xxx 的指针],
- [7324055671294268046, 指向 salary 的指针, 指向 999999 的指针]
- ]
- '''
现在如果我要读取数据怎么办呢? 假如我要读取 salary 的值, 那么首先计算 salary 的 hash 值, 以及这个值对 8 的余数:
- >>> hash('salary')
- 7324055671294268046
- >>> hash('salary') % 8
- 6
那么我就去读 indices 下标为 6 的这个值. 这个值为 2.
然后再去读 entries 里面, 下标为 2 的这一行的数据, 也就是 salary 对应的数据了.
新的这种方式, 当我要插入新的数据的时候, 始终只是往 entries 的后面添加数据, 这样就能保证插入的顺序. 当我们要遍历字典的 Keys 和 Values 的时候, 直接遍历 entries 即可, 里面每一行都是有用的数据, 不存在跳过的情况, 减少了遍历的个数.
老的方式, 当二维数组有 8 行的时候, 即使有效数据只有 3 行, 但它占用的内存空间还是 8 * 24 = 192 byte. 但使用新的方式, 如果只有三行有效数据, 那么 entries 也就只有 3 行, 占用的空间为 3 * 24 =72 byte, 而 indices 由于只是一个一维的数组, 只占用 8 byte, 所以一共占用 80 byte. 内存占用只有原来的 41%.
来源: https://www.cnblogs.com/xieqiankun/p/python_dict.html