参考《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()返回的不是集合而是字典视图。
网友评论