字典和集合

Python的字典为键值存储的数据结构。

# 创建
d = dict([[1,2],[3,4]])
d1 = {'key1': 1, 'key2': 2}

# 查找
d1['key1']
d1.get('key1')

# 插入/修改
d1['key3'] = 3

# 删除
del d1['key3']

字典的查找插入删除操作都是O(1)复杂度，速度极快，并且不会随着key的增加而变慢。

但是需要占用大量的内存。所以字典是用空间换时间的数据结构。

集合和字典类似，是一组不重复的key，但是没有value。

# 创建
s = set([1, 2, 3])
s1 = {1, 2, 3}

# 插入
s.add(4)

# 删除
s.remove(4)

set可以看成数学意义上的集合，set可以进行交集/并集等操作。

• 性能差别

字典和集合是性能高度优化过的数据结构，对于列表的查找操作，需要遍历列表，时间复杂度是O(n)。

但是如果用字典来存储这些数据，则只需O(1)复杂度。因为字典内部组成是一张哈希表，可以直接通过键的哈希值找到对应的值。

对于去重任务，如果使用列表的话，最坏情况会需要O(n^2)复杂度。但是集合的去重操作复杂度则是O(n)，因为集合是高度优化的哈希表，里面的元素不能重复，而且添加查找都是O(1)复杂度。

• 工作原理

字典和集合的内部结构都是一张哈希表。

对于字典，哈希表存储了哈希值，键和值3种元素。为了优化存储空间，字典维护一个索引表及一个元素表。而对于合集，哈希表只有单一的元素。

每次向字典或集合插入元素时，Python会先计算键的哈希值hash(key)，然后做mask操作，计算应该插入哈希表的位置，如果位置为空则进行插入操作。

如果位置已被占用，Python会比较两个元素的哈希值和键是否相等。如果相等则更新值，否则视为发生哈希冲突。Python会继续寻找其他空位，具体方法有开放寻址法和拉链法。

• 应用场景

  • 字典：查找
  • 集合：去重

• ref:

  • 廖雪峰dict和set
  • Python字典和集合的内部实现