字典和集合

字典（dicts， dictionaries dictionaries (opens new window)）是一系列由键（key）和值（value）配对组成的元素的集合，底层是哈希表。字典存储任意数量的对象，每个对象都由唯一的字典key标识。

字典通常也称为maps, hashmaps, lookup tables，或 associative arrays。它们允许高效查找、插入和删除与给定键关联的任何对象。相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。

在 Python3.7+，字典被确定为有序（注意：在 3.6 中，字典有序是一个 implementation detail，在 3.7 才正式成为语言特性，因此 3.6 中无法 100% 确保其有序性），而 3.6 之前是无序的，其长度大小可变，元素可以任意地删减和改变。

>>> book = {
...     "a": 1,
...     "b": 2,
...     "c": 3,
... }
>>> squares = {x: x * x for x in range(6)}
>>> book["a"]
1
>>> "a" in book
True
>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

而集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合。

>>> book = {1,2,3,4,5,5}
>>> book
{1, 2, 3, 4, 5}

底层结构

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

• 对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。
• 而对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。

性能

dict

为dict对象列出的平均事例时间假设对象的哈希函数足够健壮，从而使碰撞不常见。一般情况下，假设参数中使用的关键点是从所有关键点集中均匀随机选择的。

注意，dict有一条快速路径（实际上）只处理str键；这不会影响算法的复杂性，但会显著影响常量因素：典型程序完成的速度。

Operation	Average Case	Amortized Worst Case
k in d	O(1)	O(n)
Copy[3]	O(n)	O(n)
Get Item	O(1)	O(n)
Set Item[1]	O(1)	O(n)
Delete Item	O(1)	O(n)
Iteration[3]	O(n)	O(n)

set

跟字典dict类似。

Operation	Average case	Worst Case	notes
x in s	O(1)	O(n)
Union s|t	O(len(s)+len(t)) (opens new window)
Intersection s&t	O(min(len(s), len(t)))	O(len(s) * len(t))	replace "min" with "max" if t is not a set
Multiple intersection s1&s2&..&sn		(n-1)*O(l) where l is max(len(s1),..,len(sn))
Difference s-t	O(len(s))
s.difference_update(t)	O(len(t))
Symmetric Difference s^t	O(len(s))	O(len(s) * len(t))
s.symmetric_difference_update(t)	O(len(t))	O(len(t) * len(s))

• 从源代码 (opens new window)中可以看出，集差异 st 或 s.difference(t) ( set_difference() ) 和就地集差异 s.difference_update(t) ( set_difference_update_internal() ) 的复杂性是不同的！第一个是 O(len(s))（对于 s 中的每个元素，如果不在 t 中，则将其添加到新集合中）。第二个是 O(len(t)) （对于 t 中的每个元素都将其从 s 中删除）。所以必须注意哪个是首选的，这取决于哪个是最长的集合以及是否需要新的集合。
• 要执行像 st 这样的集合操作，s 和 t 都需要是集合。但是，即使 t 是任何可迭代的，您也可以执行等效方法，例如 s.difference(l)，其中 l 是一个列表。

其他

高效创建字典

• 字典生成式
• {}
• dict()

跟列表一样，字典也有它的语法糖，且比dict()定义字典更高效。

# 使用{}
d = {'name': 'go', 'age': 10, 'python': '20'}

# 使用dict函数
d = dict({'name': 'go', 'age': 10, 'python': '20'})

使用dis分析：

>>> def create_dict1():
...     return {'name': 'go', 'age': 10, 'python': '20'}
...
>>> def create_dict2():
...     return dict({'name': 'go', 'age': 10, 'python': '20'})
...
>>> dis.dis(create_dict1)
  2           0 LOAD_CONST               1 ('go')
              2 LOAD_CONST               2 (10)
              4 LOAD_CONST               3 ('20')
              6 LOAD_CONST               4 (('name', 'age', 'python'))
              8 BUILD_CONST_KEY_MAP      3
             10 RETURN_VALUE
>>> dis.dis(create_dict2)
  2           0 LOAD_GLOBAL              0 (dict)
              2 LOAD_CONST               1 ('go')
              4 LOAD_CONST               2 (10)
              6 LOAD_CONST               3 ('20')
              8 LOAD_CONST               4 (('name', 'age', 'python'))
             10 BUILD_CONST_KEY_MAP      3
             12 CALL_FUNCTION            1
             14 RETURN_VALUE

比较创建时间：

python -m timeit "d = {'name': 'go', 'age': 10, 'python': '20'}"
# 5000000 loops, best of 5: 98.7 nsec per loop
python -m timeit "d = dict({'name': 'go', 'age': 10, 'python': '20'})"
# 1000000 loops, best of 5: 219 nsec per loop

字典的键需要是可哈希的值

字符串和数字等不可变类型是可哈希的，并且可以很好地用作字典键。也可以将tuple对象用作字典键，只要它们本身只包含可散列类型。

但对于列表这种可变化类型，是不可以作为字典的键的。