字典和集合基础
字典是一系列由键（key）或值（value）配对组成的元素的集合，在Python3.7+，字典被确定为有序，而3.6之前是无序的，其长度大小可变，元素可以任意地删减和改变。相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。
在3.6中，字典有序是一个implementation detail，在3.7才正式成为语言特性，因为3.6中无法100%确保其有序性。
而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。下面是字典和集合的创建几种方式：
>>>'''字典创建的方式'''
>>> d1 = {"name":'Dawn', 'age':20, 'gender':'male'}
>>> d2 = dict({"name":'Dawn', 'age':20, 'gender':'male'})
>>> d3 = dict([("name", 'Dawn'), ('age', 20), ('gender','male')])
>>> d4 = dict(name='Dawn', age=20, gender='male')
>>> d1 == d2 == d3 == d4
True
>>>'''集合创建的方式'''
>>> s1 = {1, 2, 3}
>>> s2 = set([1, 2, 3])
>>> s1 == s2
True
-
字典的访问：按键值、get(key, default)
-
集合的访问：**集合并不支持索引操作，因为集合本质上是一个哈希表，和列表不一样，**所以针对一个集合使用
s[0]这种方式访问是错的。 -
元素是否在字典或集合里面：使用value in dict/set来判断
-
字典和集合的增加、删除、更新：
>>> s = {1,2,3}
>>> s.add(4)
>>> s
{1, 2, 3, 4}
>>> s.remove(4)
>>> s
{1, 2, 3}
集合的pop()操作是删除集合中最后的一个元素，可是集合本身是无序的，你无法知道会删除哪个元素，因此这个操作得谨慎使用。
- 字典和集合的排序
>>> d = {'b':1, 'a':3, 'c':2}
>>> dSortedByKey = sorted(d.items(), key=lambda x:x[0])
>>> dSortedByKey
[('a', 3), ('b', 1), ('c', 2)]
>>> dSortedByValue = sorted(d.items(), key=lambda x:x[1])
>>> dSortedByValue
[('b', 1), ('c', 2), ('a', 3)] # 默认是升序排列
>>> dSortedByValue = sorted(d.items(), key=lambda x:x[1], reverse=True)
>>> dSortedByValue
[('a', 3), ('c', 2), ('b', 1)] # 想要降序，reverse=True即可
>>> s = {3, 4, 2, 1}
>>> sorted(s)
[1, 2, 3, 4]
- 字典的键值和集合中的元素必须是要
hashable，如下所示['education']就是不可哈希的，那么是错误的
d = {'name': 'jason', ['education']: ['Tsinghua University', 'Stanford University']}
字典和集合性能
字典和集合是进行过性能高度优化的数据结构，特别是对于查找、添加和删除操作。下面把它们和列表进行比较：
字典和列表比较
假如我们现在需要给定某件商品的ID，我们要找出其价格，假如使用列表存储并进行查找的话，代码和列表存储示例如下：
def find_product_price(products, product_id):
for id, price in products:
if id == product_id:
return price
return None
products = [
(143121312, 100),
(432314553, 30),
...
(32421912367, 150)
]
find_product_price(products, 432314553) # 查找
假设products中有n个元素，而查找的过程中要遍历列表，那么时间复杂度为O(n)。假如用字典来存储我们这些数据，那么查找就会非常便捷高效，只需要O(1)的时间复杂度就可以完成，因为字典的内部组成是一张哈希表。使用字典存储结构如下所示：
products = {
143121312: 100,
432314553: 30,
...
32421912367: 150
}
products[432314553] # 查找
集合和列表进行比较
跟上述数据类似，只是这次我们要找出有多少不同的价格，假如使用列表数据结构来存储这些价格，那么需要$O(n^2)$的时间复杂度：
# list version
def find_unique_price_using_list(products):
unique_price_list = []
for _, price in products: # A
if price not in unique_price_list: #B
unique_price_list.append(price)
return len(unique_price_list)
products = [
(143121312, 100),
(432314553, 30),
...
(32421912367, 150),
(937153201, 30)
]
find_unique_price_using_list(products)
但是假如我们选择使用集合这个数据结构，由于集合是高度优化的哈希表，里面的元素不能重复，并且添加、删除操作只需O(1)的复杂度，那么总的时间复杂度就只有O(n):
# set version
def find_unique_price_using_set(products):
unique_price_set = set()
for _, price in products:
unique_price_set.add(price)
return len(unique_price_set)
products = [
(143121312, 100),
(432314553, 30),
...
(32421912367, 150),
(937153201, 30)
]
find_unique_price_using_set(products)
为了有一个更加直观的感受，下面对上述两种方法进行测试，测试代码如下：
import time
id = [x for x in range(0, 10000)]
price = [x for x in range(20000, 30000)]
products = list(zip(id, price))
# 计算列表版本的时间
start_using_list = time.perf_counter()
find_unique_price_using_list(products)
end_using_list = time.perf_counter()
print("使用列表测试的时间: {}".format(end_using_list - start_using_list))
# 计算集合版本的时间
start_using_set = time.perf_counter()
find_unique_price_using_set(products)
end_using_set = time.perf_counter()
print("使用集合方式测试的时间: {}".format(end_using_set - start_using_set))
测试的结果如下，很明显集合这种方式会更高效：
使用列表测试的时间: 0.770091052909779
使用集合方式测试的时间: 0.0012316425773241102
字典和集合推荐初始化方法
同列表和元组初始化方法一样，字典和集合的初始化方法有以下几种，那么更高效的是第一种初始化方法，原理同列表那的类似。
# 字典第一种初始化方法
d = {'name': 'Dawn', 'age': 20, 'gender': 'male'}
# 字典第二种初始化方法
d = dict({'name': 'Dawn', 'age': 20, 'gender': 'male'})
上述的测试效果如下：
>>> import timeit
>>> timeit.timeit("d = {'name': 'Dawn', 'age': 20, 'gender': 'male'}",number=100000)
0.0157328343314731
>>> timeit.timeit("d = dict({'name': 'Dawn', 'age': 20, 'gender': 'male'})",number=100000)
0.045083716705413224
字典和集合的内部实现
上面演示了字典和集合与列表的性能比较，那么为什么字典和集合能够如此高效，特别是查找、插入和删除操作。这与字典和集合的内部结构都是一张哈希表密不可分。其中对于字典而言，这张表存储了哈希值（hash）、键和值这3个元素，而对于集合来说区别就是哈希表内只有单一的元素。
字典的内部实现
字典是通过哈希表实现的，也就是说，字典是一个数组，而数组的索引是键值经过哈希函数处理后得到的。如我们有如下这样的一个字典：
{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}
那么实际上存储中这是一个数组，如下所示，即键值经过哈希函数得到的哈希值为（哈希值，键，值）在数组中存储的索引：
entries = [
...
[-1749738411985517803, 'gender', 'male'],
...
[-1129878167999217704, 'dob', '1999-01-01'],
...
[-599462501662173341, 'name', 'mike'],
...
]
然而这种方式显然非常浪费存储空间，为了提高存储空间的效率。Python内部实现中，将存储字典的数组初始大小设置为8，并且数组的索引在原来直接得到的哈希值的基础之上加上了掩码，改变后的索引=哈希值&掩码，即index=hash(key)&mask，其中mask=PyDict_MINSIZE - 1，PyDict_MINSIZE 为Python内部实现中存储字典的数组的长度，初始值为8，当存放的数据量超过数组的大小的2/3，那么会调整数组的长度，PyDict_MINSIZE 值也会变化，并且所有元素的位置都会重新计算，重新存储。那么对于刚刚的例子来说，会初始一个大小为8的数组，此时mask为7，那么通过&操作后得到的索引情况如下所示：
>>> hash('name')&7
3
>>> hash('dob')&7
0
>>> hash('gender')&7
5
那么数组的存储情况如下所示：
entries = [
...
[-1749738411985517803, 'gender', 'male'],
...
[-1129878167999217704, 'dob', '1999-01-01'],
...
[-599462501662173341, 'name', 'mike'],
...
]
其中['---','---','---']表示为空，这样子就在一定程度上提高了空间利用率。下面我们具体来讲一下针对插入、查找、删除操作的内部流程。
插入操作
跟上述所阐述的类似，向字典中插入时，会首先计算键的哈希值，即hash(key)，再和mask进行与操作，计算这个元素应该插入数组的位置index = hash(key)&mask。如果该位置为空，那么则将值被插入其中，而如果此位置已被占用，Python便会判断这两个的键值是否相等，如果相等，则表明这个元素已经存在，如果值不同则更新值，假如不相等，那么就是哈希冲突。这种情况下，便会寻找表中空余的位置，直到找到位置为止。最简单的方式就是线性寻址，当然，Python内部对此进行了优化，让这个步骤更加高效。
index = hash(key) & mask # mask = PyDicMinSize - 1
if slot[index] is empty:
slot[index] -> value
else if key is old key:
slot[index] -> new value
else
find a new index: slot[new index] -> new value
查找操作
与插入操作类似，Python会根据index = hash(key)&mask找到index位置，假如index位置为空，那么抛出异常，假如不为空比较这个位置的键值和查找的键值是否相等，如果相等，则直接返回，如果不等，则按照上述哈希冲突的方法继续查找，直到找到或者找到空位为止。
index = hash(key) & mask # mask = PyDicMinSize - 1
if slot[index] is empty:
raise KeyError
if slot[index] is not empty and slot[index].key == key:
return slot[index]
else:
find all slot until find or find null(raise KeyError)
删除操作
对于删除操作，同样会进行同查找的步骤。但是当找到之后，并不是真正的删除而是暂时会对这个位置赋予一个特殊的值，等待重新调整哈希表的大小时，再将其删除。
集合的内部实现
集合和字典的实现原理都是一样的，都是将实际的值放到一个数组中，不同的地方在于hash函数操作的对象，对于字典而言，hash函数操作的是key，而对于集合来说是直接操作它的元素。所以集合中的对象必须是hashable的。这里就不再赘述了。
- index = hash(key) & mask # mask = PyDicMinSize - 1
- if slot[index] is empty: slot[index] -> value
- else if key is old key: slot[index] -> new value
- else find a new index: slot[new index] -> new value
本文参考内容
- 个人博客_Python 容器
- 伯乐在线_深入 Python 字典的内部实现
- 极客时间_Python核心技术与实战
