理解字典与集合

字典基础

集合基础

1.散列表

字典和集合对于查找、添加、删除操作都能在常数时间复杂度完成，其内部实现依赖于散列表
散列表其实是一个稀疏的数组，散列表的单元叫做表元。在dict的散列表中，每个键值对会占用一个表元，每个表元会有两个部分，一个是键的引用，一个是对值的引用。因为每个表元的大小一致，所以可以通过偏移量来读取某个表元。python会设法保证大概三分之一的表元是空的。所以快要达到这个阈值的时候，原有的散列表会复制到一个更大的表元里。
散列表算法：为了获取dict[key]背后的值，python会调用hash(key),来计算key的散列值，去查找表元，若找到的表元为空，则抛出KeyEror的异常。若不为空，则表元中有一对 found_key：found_value，这时候会检验search_key == found_key 是否为真，相等的话，就会返回found_value

因此字典的键一定是可散列的（内部实现了__hash__()方法和__eq__()方法），集合的值是可散列的
散列表的实现导致python字典集合的空间开销特别大，但是新版本python会把索引和哈希值、键、值单独分开，使得空间利用率得到很大的提高。

Python 3.5（含）之前，字典的底层原理。

当我们初始化一个空字典的时候，CPython的底层会初始化一个二维数组，这个数组有8行，3列，如下面的示意图所示：

my_dict = {}


'''

此时的内存示意图

[[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---]]

'''

现在，我们往字典里面添加一个数据：

my_dict['name'] = 'kingname'
'''
此时的内存示意图

[[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[---, ---, ---],

[1278649844881305901, 指向name的指针, 指向kingname的指针],

[---, ---, ---],

[---, ---, ---]]

'''

在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的指针]]

'''

新的这种方式，当我要插入新的数据的时候，始终只是往 entries的后面添加数据，这样就能保证插入的顺序。当我们要遍历字典的Keys和Values的时候，直接遍历 entries即可，里面每一行都是有用的数据，不存在跳过的情况，减少了遍历的个数。

老的方式，当二维数组有8行的时候，即使有效数据只有3行，但它占用的内存空间还是 8 * 24 = 192 byte。但使用新的方式，如果只有三行有效数据，那么 entries也就只有3行，占用的空间为3 * 24 =72 byte，而 indices由于只是一个一维的数组，只占用8 byte，所以一共占用 80 byte。内存占用只有原来的41%。

所以Python 3.7以后字典有序并且效率更高

字典和集合的工作原理

插入操作：