前言字典(dict)和集合(set),字典和集合在Python被广泛使用,并且性能进行了高度优化。字典是一系列由键(key)和值(value)配对组成的元素的集合。Python 3.7 及之后dict 是保证插入顺序的。相比于列表和元组字典的性能更优特别对于查找、添加和删除操作字典都能在常数时间复杂度内完成。字典和集合的创建及操作d1{name:jason,age:20,gender:male}d2dict({name:jason,age:20,gender:male})d3dict([(name,jason),(age,20),(gender,male)])d4dict(namejason,age20,gendermale)print(d1,d2,d3,d4)print(d1d2d3d4)##true结果如下{name:jason,age: 20,gender:male}{name:jason,age: 20,gender:male}{name:jason,age: 20,gender:male}{name:jason,age: 20,gender:male}Trues1{1,2,3}s2set([1,2,3])print(s1,s2)print(s1s2)s{1,hello,5.0}print(s)结果如下{1,2,3}{1,2,3}True{1,hello,5.0}d{name:jason,age:20}print(d[name])print(d.get(name))print(d.get(location,null))###nullprint(d[location])####KeyError: location结果如下jason jason null Traceback(most recent call last): print(d[location])####KeyError: locationKeyError:location集合不支持索引操作因为集合本质上是一个哈希表和列表不一样。要想判断一个元素在不在字典或集合内我们可以用value in dict/set来判断。s{1,2,3}print(1ins)print(10ins)结果如下True Falsed{name:jason,age:20}print(nameind)print(locationind)结果如下True False除了创建和访问字典和集合页同样支持增加、删除、更新等操作。d{name:jason,age:20}d[gender]male# 增加元素对gender: maled[dob]1999-02-01# 增加元素对dob: 1999-02-01print(d)d[dob]1998-01-01# 更新键dob对应的值print(d)d.pop(dob)# 删除键为dob的元素对print(d)结果如下{name:jason,age: 20,gender:male,dob:1999-02-01}{name:jason,age: 20,gender:male,dob:1998-01-01}{name:jason,age: 20,gender:male}s{1,2,3}s.add(4)# 增加元素4到集合print(s)s.remove(4)# 从集合中删除元素4print(s)结果如下{1,2,3,4}{1,2,3}对字典或集合进行排序d{b:1,a:2,c:10}d_sorted_by_keysorted(d.items(),keylambdax:x[0])# 根据字典键的升序排序print(d_sorted_by_key)d_sorted_by_valuesorted(d.items(),keylambdax:x[1])# 根据字典值的升序排序print(d_sorted_by_value)结果如下[(a,2),(b,1),(c,10)][(b,1),(a,2),(c,10)]这里返回了一个列表列表中的每个元素由原字典的键值组成的元组。s{3,4,2,1}sorted(s)# 对集合的元素进行升序排序print(s)resultsorted(s,reverseTrue)print(result)结果如下{1,2,3,4}[4,3,2,1]需要注意的是集合set本身是无序的。当你使用 sorted(s) 对集合进行排序后返回的结果不再是集合而是一个列表list。字典和集合的性能前面提到过字典和集合是进行过性能高度优化的数据结构特别是对于查找、添加和删除等操作。接下来让我们就看一下它们在具体场景下的性能表现。假设列表有n个元素,而查找过程需要遍历列表那么时间复杂度为O(n)。即使我们先对列表进行排序然后使用二分查找也会需要O(logn)的时间复杂度。更何况列表的排序还需要O(logn)的时间。 但如果用字典来存储这些数据那么查找会非常便捷高效时间复杂度为O(1),因为字典的内部就是一张哈希表你可以根据键的哈希值找到对应的值。字典和集合的工作原理字典和集合为什么会如此高效呢特别是查找、插入和删除操作呢因为字典和集合的内部结构都是一张哈希表。对于字典而言这个表存储了哈希值键和值这三个元素。而对于集合来说区别就在于哈希表里面没有键值配对了只有一个元素。字典存储结构如下比如我有这样一个字典{‘name’: ‘mike’, ‘dob’: ‘1999-01-01’, ‘gender’: ‘male’}新的存储结构类似这样Indices----------------------------------------------------None|index|None|None|index|None|index...----------------------------------------------------Entries--------------------hash0 key0 value0---------------------hash1 key1 value1---------------------hash2 key2 value2---------------------...---------------------它会存储为类似下面的形式indices [None, 1, None, None, 0, None, 2]entries [[1231236123,name,mike],[-230273521,dob,1999-01-01],[9371539127,gender,male]]插入操作每次像字典或集合插入一个元素时python会先计算键的哈希值hash(key),再和mask PyDicMinSize -1做与操作计算这个元素应该插入哈希表的位置index hash(key)/mask。如果哈希表中此位置是空的那么该元素就会被插入其中。而如果此位置已经被占用python会判断比较两个元素的哈希值和键是否相等。若两者都相等则表明这个元素已存在如果值不同则更新值。若两者中有一个不相等这种情况我们通常称之为哈希冲突hash collision意思是两个元素的键不相等但哈希值相等。这种情况下python便会继续寻找表中空余的位置直到找到位置为止。查找操作python会先根据其哈希值找到其应该处于的位置;然后比较哈希表这个位置中元素的哈希值和键与需要查找的元素是否相等。如果相等则直接返回如果不等则继续查找直到找出空位或抛出异常。删除操作对于删除操作python会暂时对这个位置的元素赋予一个特殊的值等到重新调整哈希表的大小时再将其删除。为了保证其高效性字典或集合内的哈希表通常会保证其至少留有1/3的剩余空间。随着元素的不停插入当剩余空间小于1/3时python会重新获取更大的内存空间扩充哈希表。不过这个情况下表内所有的元素位置都会被重新排放。