字典和集合

参考《Fluent Python》字典和集合

集合的本质是唯一元素的聚集，所以集合可以用来去重

>>> l = ['open', 'spam', 'aaaa', 'aaaa']
>>> set(l)
{'aaaa', 'spam', 'open'}

集合也支持一些基础的中缀运算符，给定两个集合a， b， a | b返回合集, a & b返回交集， a - b是差集。

创建set的两种方法：{}和set()

>>> from dis import dis
>>> dis('{1}')
  1           0 LOAD_CONST               0 (1)
              2 BUILD_SET                1
              4 RETURN_VALUE
>>> dis('set([1])')
  1           0 LOAD_NAME                0 (set)
              2 LOAD_CONST               0 (1)
              4 BUILD_LIST               1
              6 CALL_FUNCTION            1
              8 RETURN_VALUE

使用第一种方法更快一点，第二种会先从set这个名字查询构造方法，然后创建一个列表，把这个列表传入构造方法中，而第一种会利用专门的BUILD_SET来创建集合。

集合推导

>>> from unicodedata import name
>>> {chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), '')}
{'#', '÷', '§', '%', '¬', '©', '>', '¢', '±', 'µ', '<', '®', '¥', '$', '¶', '¤', '=', '×', '£', '°', '+'}

从unicodedata中导入name函数，用来获取字符的名字。

将32-256之间的字符的名字中带有SIGN的提取出来，放在一个集合中。

散列表（Hash表）

Hash基础

Python用Hash表实现了dict类。

Hash表的时间复杂度为O(1)。

散列函数

散列函数给出一个数据，返回一个数字。即散列函数：

将输入映射到数字

散列函数的条件：

必须一致，可重复，假设输入apple得到4。那么必须每次输入apple都要输出4
不同输入映射到不同数字

散列表的作用就是用来快速查找，更新数据。

将数据的键输入散列函数，得到的数字作为数组下标，将值储存在相应位置，在查询数字时，只需要输入键即可得到索引，从而得到数字。

当有大量数据的时候效率尤其明显。

字典中的散列表

Hash表其实是一个稀疏数组（总有空白元素的数组成为稀疏数组），散列表中的每一个单元叫做表元，在dict中，每个键值对占用一个表元，表元中包括两部分：对键的引用和对值的引用。

如果想把一个对象放进散列表中，需要计算这个元素键的散列值， Python中用Hash()来计算。

散列表算法

为了获取my_dict[search_key]的值，python会首先调用hash(search_key)来计算散列值，取这个散列值的最低的几位数字作为偏移量，在散列表中查询表元。若表元为空，则抛出错误，若不为空，检测search_key == found_key若为真，则返回值。

当search_key == found_key不匹配时，称为散列冲突，这是算法会取散列值的另外几位数字，来寻找表元。

散列表算法

根据散列表的大小，散列表所占的位数和用作索引的位数都不一样，这样是为了避免散列冲突的发生的概率，实际情况下，发生散列冲突的概率是很小的。

An object is hashable if it has a hash value which never changes during its lifetime (it needs a hash() method), and can be compared to other objects (it needs an eq() method). Hashable objects which compare equal must have the same hash value.

即如果一个对象是可散列的：

需要支持hash()函数，并且得到的散列值是不变的
支持通过eq()来检测相等性
若a == b为真，那么hash(a) == hash(b)也为真

原子不可变数据类型（str，bytes和数值类型）都是hashable类型，frozenset也是hashable的，因为根据其定义，frozenset里只可容纳可散列类型。元组也是hashable的，但只有当元组包含的所有元素都是hashable类型的情况下它才是可散列的。list等可变对象是不可散列的，因为随着数据的改变他们的哈希值会变化导致进入错误的哈希表。

>>> test = (1, 2, (3, 4))
>>> hash(test)
3794340727080330424
>>> test1 = (1, 2, [3, 4])
>>> hash(test1)
Traceback (most recent call last):
  File "<pyshell#71>", line 1, in <module>
    hash(test1)
TypeError: unhashable type: 'list'

所有由用户自定义的对象默认都是可散列的，他们的散列值通过id()来获取，而且不相等。

字典在内存上消耗大

因为字典采用散列表。如果要保存巨大的数据，放在元组中是比较好的选择

字典的键查询很快

字典是典型的空间换时间，虽然有很大的内存开销，但是他也有无视数据量大小的访问速度。

向字典中添加新键可能会改变已有键的顺序

当向字典中添加新的键时， Python都可能做出字典扩容的决定。对字典的迭代和修改最好分成两步。

首先对字典进行迭代，得到需要修改的内容；在把这些内容放在一个新的字典中，迭代结束后对原有字典更新。

Python3中，字典的.keys(), .items()和.values()返回的不是集合而是字典视图。