Python 核心技术与实战 --02 字典和集合
什么是字典？
字典是一系列由键(key) 和 值(value) 配对组成的元素集合，在python3.7+ ， 字典被确定为有序（注意在3.6 中，字典有序是一个implementation detail, 在3.7 才正式成为语言特性），而在3.6 无法100% 保证有序性，而在3.6 之前是无序的，其长度大小可变，元素可以任意地删减和改变。
相比于列表和元组，字典的性能更优，特别是相对于查找/添加/删除的操作，字典都能在常数时间复杂度内完成。
而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的/唯一的元素组合。
首先我们来看字典和集合的创建，通常有以下几种方式
d1={‘name‘:‘jason‘,‘age‘:20}
d2=dict({‘name‘:‘jason‘,‘age‘:20})
d3=dict([(‘name‘,‘jason‘),(‘age‘,20)])
d4=dict(name=‘jason‘,age=20)
s1={1,2,3}
s2=set([1,2,3])
python 中字典和集合，无论是键还是值，都可以是混合类型。比如下面这个例子，我创建了一个元素为1，’hello‘,5.0 的集合
元素访问问题。字典访问可以直接索引键，如果不存在就抛出异常。
d ={‘name‘:jason‘,‘age‘:20}
d.get(‘name‘)
d.get(‘location‘,‘null‘)
如果不存在就返回 ‘null‘ 默认值集合
集合本质上是一个哈希表，和列表不一样。所以集合不支持索引操作。
想要判断一个元素在不在字典或集合内，我们可以用value in dict/set 来判断。
s={1,2,3}
1 in s
True
10 in s
False
d = {‘name‘:‘jason‘,‘age‘:20}
‘name‘ in d
True
‘location‘ in d
False增加/删除/更新操作
d={‘name‘:‘jason‘,‘age‘:20}
d[‘gender‘]=‘male‘
d[‘dob‘]=‘1999-02-01‘
d.pop(‘dob‘)
s={1,2,3}
s.add(4)
s.remove(4)集合的pop() 操作是删除集合中最后一个元素，可是集合本身是无序的所以你无法知道会删除哪个元素，这个操作谨慎使用
实际应用中，很多情况下，我们需要对字典或集合进行排序，比如，取出值最大的50对。
对于字典，我们通常会根据键或者值，进行升序或降序排序：
d={"a‘:1,‘c‘:3,‘d‘:4}
sorted_by_key = sorted(d.items(),key=lambda x:x[0])
sorted_by_value = sorted(d.items(),key=lambda x:x[1])字典和集合的性能
字典和集合是进行过高度性能优化的数据结构，特别是对于查找/添加/和删除操作。那接下来，我们就来看看，它们在具体的场景下的性能表现，以及与列表等其他数据结构进行对比
比如某电商企业的后台，存储了每件产品的ID/名称/和价格。现在的需求是，给定某件商品的ID，我们要求找出其价格
如果我们用列表来存储这些数据结构，并进行查找，相应代码如下
def find_product_price(products,product_id):
for id,price in products:
if id == product_id:
return price
return None
products=[(143121312,100),
(23121312,30),
(32421312,150)]假设列表中有n个元素，而查找的过程要遍历列表，那么时间复杂度为O(n). 即使我们先对列表进行排序，然后再使用二分查找，我们也需要O(logn) 的时间复杂度，更何况，列表的排序还需要O(nlogn)的时间。
但如果使用字典来存储这些数据，那么查找就会非常便捷高效，只需要O(1) 的时间复杂度就可以完成。原因很简单，刚刚提到过的，字典的内部组成是一张哈希表，你可以直接通过键的哈希值，找到其对应的值。
类似的，现在需求变成，要找出这些商品有多少种不同的价格。我们还用同样的方法来比较一下。
如果还是选择用列表，对应的代码如下，其中，A和B是两层循环。同样假设原始列表有n个元素，那么最差的情况下，需要O(n^2)的时间复杂度。
def find_unique_price_using_list(products):
unique_price_list =[]
for _,price in products:
if price not in unique_price_list:
unique_price_list.append(price)
return len(unique_price_list)但如果我们选择使用集合这个数据结构，由于集合是高度优化的哈希表，里面的元素不能重复，并且其添加和查找操作只需要O(1)的复杂度，那么，总的时间复杂度就只是O(n)
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)字典和集合的工作原理:
字典集合内部的数据结构都是一张哈希表。
对于字典而言，这张表存储了哈希值(hash)/键/值这三个元素。
而对于集合来说，区别就是哈希表内没有键值的配对，只有单一的元素。
老版本的哈希表结构:
哈希值(hash) 键(key) 值(value) --------------------------------------------- hash0 key0 value0 --------------------------------------------- hash1 key1 value1 --------------------------------------------- hash2 key2 value2 -------------------------------------------
不难想象，随着哈希表的扩张，它会变得越来越稀疏。举个例子，比如我有这样一个字典:
{‘name‘:‘mike‘,‘dob‘:‘1991-01-01‘,‘‘gender‘:‘male‘}
那么它会存储为类似下面的形式:
entries=[ [‘--‘,‘--‘,‘--‘], [-230273521,‘dob‘,‘1999-01-01‘], [‘--‘,‘--‘,‘--‘], [‘--‘,‘--‘,‘--‘], [‘1231236123‘,‘name‘,‘mike‘], [‘--‘,‘--‘,‘--‘], [9371539127‘,‘gender‘,‘male‘] ]
这样的设计结构非常浪费存储空间。为了提高内存的利用率，现在的哈希表除了字典本身的结构，会把索引和哈希值/键/值单独分开，也就是下面的这样新的结构
Indices -------------------------------------------------------------------------- None| index| None| None| index|None|index|.... ------------------------------------------------------------------------- Entries -------------------- hash0 key0 value0 ----------------------- hash1 key1 value1 ------------------------ hash2 key2 value2