万网制作网站,免费制作企业网站,做一个学校网站,网站需要数据库吗在Python 3.5#xff08;含#xff09;以前#xff0c;字典是不能保证顺序的#xff0c;键值对A先插入字典#xff0c;键值对B后插入字典#xff0c;但是当你打印字典的Keys列表时#xff0c;你会发现B可能在A的前面。
但是从Python 3.6开始#xff0c;字典是变成有顺序…在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)
-5954193068542476671hash(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)
7324055671294268046hash(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%。
