Python的集合和字典

1.可散列的数据类型

在对象的生命周期中，散列值不变，需要实现hash()方法，另外可散列对象还要满足eq()方法。如果这两个散列值对象是相等的，那么他们的散列值一定是一样的。

hash()：找到进行两个对象比较的依据，返回唯一的可散列的哈希值，int类型

eq():比较这两个对象，参照一定的依据比较（一般比较其hash值）

因此若果这两个对象相等，那么他们的hash值也会相等！

---

2。原子不可变类型

例如str,bytes和数值类型是可散列的。frozenset也是可散列的，元祖的话必须满足包含的元素都是可散列的，该元祖才是可散列的。

set本身不是可散列的,因为set的参数可以为可变序列，也可以为不可变序列,所以set并不满足原子不可变类型。

---

3.字典推导：字典推导类似列表推到，形如{key：value for key,value in dict_.items()}

Python 3.x 里面，iteritems() 和 viewitems() 这两个方法都已经废除了，而 items() 得到的结果是和 2.x 里面 viewitems() 一致的。在3.x 里 用 items()替换iteritems() ，可以用于 for 来循环遍历。

python2.x 中 iteritems()返回字典推导后的迭代，不生成列表，不会占用额外内存。

---

4.字典的构造方式

dict_ = {'test':1,'name':syz}
dict_2 = dict(name='syz',age=20)
dict_3 = dict(**dict_)
dict_4 = dict([('name','syz'),('age',20)])

---

dict和list比较

和list比较，dict有以下几个特点：

（1）查找和插入的速度极快，不会随着key的增加而变慢；

（2）需要占用大量的内存，内存浪费多。

而list相反：

（1）查找和插入的时间随着元素的增加而增加；

（2）占用空间小，浪费内存很少。

---

#### **6.常见的映射方法**

（1）dict：最普通的dict方法。setdefault(key,default)方法来处理找不到键的问题，popitem随机返回一个键值，并删除它。

（2）defaultdict:通过构造defaultdict字典，能够有效的处理找不到的键，具有核心方法miss()，调用default_factory。

（3）orderedDict():将具名元祖转为orderedDict字典时用到。具有move_to_last(k,[last])将键为k的元素移动到开头会结尾，last为布尔类型，为True则移到末尾，反之移到开头。

具名元祖的_asdict()方法,转为orderedDict（）方法！

分析：
defaudict方法：当调用__getitem__的时候，如果查找不到字典，则会调用__missing__方法，然后调用defaudict创建dict实例,并传入的default_factory参数，将它作为键的默认值，如果没有default_factory则返回keyerror异常。__missing__方法只对__getitem__调用，对.get，in无影响。

---

**6.字典的变种（多种形式）:

（1）collections.OrderedDict 在添加键的时候总是会保持顺序，有特殊的popitem（last=True/last=False）方法,返回字典的最后一个元素/第一个元素。

会按照顺序排列键值对！使用跟普通字典类似

（2）collections.Counter
这个映射类型会给键准备一个整数计数器，每次更新一个键就会增加这个计数器，每次修改数值，Counter总会自动排序。

运行结果：

运行结果：

分析:

①Counter的参数为迭代类型，主要用于计数，返回的类型为Counter类型

②dict的update和Counter的update方法效果不同，前者为覆盖，后者为追加

（3）collections.UserDict
把标准的dict用纯Python实现一遍。相比于dict，UserDict的子类方法更加简洁。多用于继承。

注：字典的update方法与__getitem__方法有关系,继承dict会忽略掉__getitem__方法，因此继承多采用UserDict，UserString，UserList

结论：查找键值得时候，最好用字符格式查找！！！

---

7.不可变类型：

标准库中的所有映射类型都是可变的，通过from types import MappingProxyType
来实例化一个不可变的对象。实际上 MappingProxyType创建了dict的一个只读的视图，用户不能修改，而对原数据修改后，视图也会做相应的修改








#####分析：
由上述代码可见经过MappingProxyType实例化的映射类型，只能读，不能修改。

后面会讲到@property只读特性和@属性.setter设置装饰器

---

8.集合论

（1）set本身是不可散列的，而frozenset可以散列(不可变序列)，set中可以使用&，|等逻辑运算来实现求并集和交集。set添加和删除元素的

（2）set的方法中，存在反向操作，例如a&b&c&d反向方法是b.intersection(a,c,d)，来求多个集合的交集其中a，c，d为迭代类型对象，而b必须为集合类型。同理b.union(a,c),b.difference(a,c)(差集)等等。s.isdisjoint(z)判断s和z是否不相交。集合多采用运算符来计算。

（3）对于set集合满足增删等方法，但对于frozenset不可变集合来说，没有add，clear，discard，pop（出栈顶元素，后进先出），remove等增减方法。

m = frozenset((1,2,3,4,5,1,2,3))
m.remove(2)

>>>AttributeError: 'frozenset' object has no attribute 'remove'  # 因为frozenset是不可变集合

---

9.对set和dict探讨其背后的效率问题

（1）set和dict的性能远远大于list的性能。dict在面对超大的数据集时，性能略高于set。

（2）散列表其实是一个稀疏数组，总存在空白元素，在数据结构中，散列表里的单元成为表元，表元由两部分组成，一是对键的引用，二是对值的引用。

（3）如果两个对象在比较时相等，那么它们的散列值必须相等。越是相似但不相等的对象，它们散列值的差别应该更大。以降低散列冲突的可能性。

（4）散列表算法：

1.首先计算散列值，使用散列值得一部分去定位散列表中的一个表元。

2.判断表元是否为空

3.如果表元为空，则抛出KeyError异常，否则判断两个键是否相等。

4.如果相等，则返回对应的键值，否则重新从散列值中选取另一段数字与散列表中另一行表元比较，从第二步再次开始。

增大散列表的大小，能够减小发生散列冲突的概率。

---

10.一个散列的对象必须同时满足以下条件

（1）支持hash()函数，得到的散列值是不变的

（2）通过__eq__（）方法检测其相等性。

（3）若a==b，则hash(a)==hash(b)

注：所有用户自定义的对象都是可散列的，散列值有id()获取，它们都不相等。

hash() 函数的用途:

hash() 函数的对象字符不管有多长，返回的 hash 值都是固定长度的，也用于校验程序在传输过程中是否被第三方（木马）修改，如果程序（字符）在传输过程中被修改hash值即发生变化，如果没有被修改，则 hash 值和原始的 hash 值吻合，只要验证 hash 值是否匹配即可验证程序是否带木马（病毒）。

注:

①键的顺序取决于它的添加顺序

②往字典里添加新键可能会改变已有键的顺序。

③不要对字典同时进行迭代和修改。尽量在迭代完，再修改。否则会导致字典的键值错位

id与hash的区别：

（1）hash函数返回一个整数，两个对象的值相同，则哈希值相同，可以用来判断传输过程中文件是否被破坏。

（2）id函数同样返回一个整数，他代表一个对象在程序中的唯一身份，其实是这个对象的地址。两个不同的对象即使拥有相同的值，他的id也不相同。python中判断两个对象是否相等，就是看这两个对象的id是否相同。

散列查找其实通过的是索引查找，效率很高，但是避免不了散列冲突的问题，会导致被保存的元素的位置替换。

字典中的函数大全

D为字典实例

D.clear()                         #移除D中的所有项
D.copy()                          #返回D的副本
D.fromkeys(seq[,val])             #返回从seq中获得的键和被设置为val的值的字典。可做类方法调用
D.get(key[,default])              #如果D[key]存在，将其返回；否则返回给定的默认值None
D.has_key(key)                    #检查D是否有给定键key
D.items()                         #返回表示D项的(键，值)对列表
D.iteritems()                     #从D.items()返回的(键，值)对中返回一个可迭代的对象
D.iterkeys()                      #从D的键中返回一个可迭代对象
D.itervalues()                    #从D的值中返回一个可迭代对象
D.keys()                          #返回D键的列表
D.pop(key[,d])                    #移除并且返回对应给定键key或给定的默认值D的值
D.popitem()                       #从D中移除任意一项，并将其作为(键，值)对返回
D.setdefault(key[,default])       #如果D[key]存在则将其返回；否则返回默认值None
D.update(other)                   #将other中的每一项加入到D中。
D.values()                        #返回D中值的列表

# 举个栗子
k = dict.fromkeys(['n','b'],'me')
k
>>>{'n': 'me', 'b': 'me'}

分析：

fromkeys作为类方法，生成一个新的字典，第一个参数为迭代类型变量，作为键值，去掉重复的；第二个参数为每个键值的初始值

---

11.异常处理KeyError

在不同地方寻找一个（而不是遍历）键值对，通过try except，如果再一个字典中找不到该键，则抛出keyerror，进去其他键中取寻找。

try:
           # Check if present in user settings
           val = self.user_settings[attr]
except KeyError:
           # Fall back to defaults
           val = self.defaults[attr]