Python中的字典和集合

摘要：若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就是使关键字经过散列函数得到一个随机的地址，从而减少冲突。

导语：本文章记录了本人在学习Python基础之数据结构篇的重点知识及个人心得，打算入门Python的朋友们可以来一起学习并交流。

本文重点：

1、掌握常见的字典创建，查询，判别方法；
2、了解字典中的defaultdict、子类化Userdict和常见映射类型；
3、了解支撑字典和集合背后的散列表的工作原理。

分为字面量句法和构造方法两种，下面以{"one":1,"two":2,"three":3}为例

d1={"one":1,"two":2,"three":3}#字面量句法
d2=dict(one=1,two=2,three=3)
d3=dict([("one",1),("two",2),("three",3)])
d4=dict({"one":1,"two":2,"three":3})
d5=dict(zip(["one","two","three"],[1,2,3]))#zip并行解包
print(d1==d2==d3==d4==d5)#True

以上五种方法创建的字典是相等的。

映射类型（Mapping Types）是一种关联式的容器类型，它存储了对象与对象之间的映射关系。
字典是Python中唯一的映射类型，它是存储了若干键值对（由键映射到值）的关联容器。

collections.abc模块中有两个抽象基类，分别是Mapping和MutableMapping，它们为dict和其他类似的类型定义形式接口。

isinstance：判定object的类型
语法：isinstance(object, classinfo)

其中，object 是变量，classinfo 是类型即 (tuple,dict,int,float,list,bool等) 和 class类

若参数object是classinfo类的实例，或者object是classinfo类的子类的一个实例， 返回 True；若 object 不是一个给定类型的的对象，则返回结果总是False。

若classinfo不是一种数据类型或者由数据类型构成的元组，将引发一个TypeError 异常。

eg:

from _collections_abc import Mapping
my_dict={}
print(isinstance(my_dict,Mapping))#判断数据是否为广义映射类型。输出True.

isinstance和type的区别：
若对象是classinfo中一个类的子类，isinstance可以判断出来返回True，而type是不能的。

字典推导:在{}中使用命令语句加for甚至if实现迭代推导出新列表的操作。

Country_Codes=[(86,"China"),(91,"India"),(1,"United States"),(62,"Indonesia"),(55,"Brazil"),(92,"Pakistan"),(81,"Japan")]

dict1={country:code for code,country in Country_Codes}#推导过程
print(dict1)

dict2={code:country.upper() for code,country in Country_Codes if code>80}#由限制要求创建字典
print(dict2)
#输出：
{"China": 86, "India": 91, "United States": 1, "Indonesia": 62, "Brazil": 55, "Pakistan": 92, "Japan": 81}
{86: "CHINA", 91: "INDIA", 92: "PAKISTAN", 81: "JAPAN"}

d.setdefault VS d.get
d.setdefault(k,[default])和d.get(k,[default])两种方法都可以处理找不到的键的情况，区别在于setdefault在返回默认值的同时能够在原字典创建新的k-default键值对。
所以更新某个键值对但键不一定存在时，用d.setdefault更好一些.

eg1:处理找不到的键

names=["Ailee","Bob","Cindy"]
ages=["19","17","15"]
dict3={x:y for x,y in zip(names,ages)}#用zip可以并行拆包.
print(dict3)
print(dict3.get("David","20"))
print(dict3)#get处理查不到的键时返回默认值，但不会在原字典创建这个键.
dict3.setdefault("David","20")
print(dict3)#setdefault处理查不到的键时返回默认值，并且会在原字典创建这个键.

格式：class collections.defaultdict([default_factory[, ...]])
defaultdict是內建dict的子类，它能够在查询找不到的键时为其创造默认值，由此避免抛出keyerror。其他功能与dict相同。

eg:defaultdict推导

from _collections import defaultdict
dict3=defaultdict(list,[(x,y) for x,y in zip([1,2,3,4,5],list("apple"))])
print(dict3)
#输出：
defaultdict(, {1: "a", 2: "p", 3: "p", 4: "l", 5: "e"})

eg:查询点名册同学的出席次数

from _collections import defaultdict

namelist=["Ailee", "Bob", "Cindy", "Ailee", "Bob", "Cindy", "Cindy", "Cindy", "Bob", "Cindy", "Ailee", "Bob", "Bob"]
count=defaultdict(int)#使用记录值数据结构整型作为默认的工厂函数

for x in namelist:
    count[x]+=1
    
print(count)#defaultdict(, {"Ailee": 3, "Bob": 5, "Cindy": 5})

原理解释：defaultdict在查询找不到的键时会通过__getitem__调用__missing__，然后__missing__根据default_factory选择返回默认值。当不输入default_factory时，会抛出keyerror。
我们可以通过print (defaultdict.__missing__.__doc__)来看__missing__的内部实现：

__missing__(key) # Called by __getitem__ for missing key; pseudo-code:
  if self.default_factory is None: raise KeyError((key,))
  self[key] = value = self.default_factory()#为找不到的键创建默认值
  return value

注意：__missing__只能被__getitem__调用，调用__getitem__可用d[k]，d.get(k)无效。

default_factory的选择

类型名称作为初始化函数参数
此类设置根据创建字典的值的需求而定；
若值以整型记录可用int；若用列表记录多个数据可用list。

可调用函数作为初始化函数参数
使用任何不带参数的可调用函数，并以该函数返回值作为默认值。
仍以点名code为例，有两种方法：
1）自定义函数：

def zero():
    return 0
count=defaultdict(zero)

2）使用lambda创建匿名函数

count=defaultdict(lambda :0)

UserDict继承自抽象基类（abstract based class）中的MutableMapping。

UserDict是让用户继承写子类的。之所以倾向于从UserDict而不是dict继承的原因是，这是因为在覆盖重写dict类的 get(k, default)、__setitem__( )、__contain__( )、__missing__( ) 等方法时，常常又会使用到 mapObj[k]、 k in mapObj、mapObj[k] 等语法形式，这样一不小心就会造成这些内部方法的无穷递归调用。但是UserDict就不会有此类问题。

UserDict有一个data的属性，是dict的实例。用户定义UserDict的子类时如果重写方法，并不会递归调用UserDict的其他方法，而是对UserDict.data进行操作，这样就减少了用户自定义dict时防范死循环递归的难度。

eg:

import collections
class Modified_Dict(collections.UserDict):#继承自UserDict
    def __missing__(self,key):
        if isinstance(key, str):#防止递归循环，及时抛出keyerror
            raise KeyError(key)
        return self[str(key)]
    def __contains__(self,key):
        return str(key) in self.data
    def __setitem__(self, key, item):
        self.data[str(key)]=item
dict4=Modified_Dict({"Ailee": 3, "Bob": 5, "Cindy": 5})#使用新dict类构造字典
print(dict4["Ailee"])#输出：3
dict4.update({"one":1,"two":2})
print(dict4)#输出：{"Ailee": 3, "Bob": 5, "Cindy": 5, "one": 1, "two": 2}

错误示范：这里应该加圆括号建立自定义dict的空字典，否则之后的数据无法被更新

dict5=Modified_Dict
dict5.update({"one":1,"two":2})
print(dict5)#发现update失败 -_-!

UserDict继承自Mapping基类，诸如MutableMapping.update和Mapping.get也很实用。（截止2017.12.15 未掌握Mapping.get）

从Python3.3开始，type模块引入了一个封装类名叫做MappingProxyType。MappingProxyType提供一个可读的动态映射视图，即用户无法从这个视图对原映射进行改动，但是原映射有改动时可以通过这个视图观察到。
此类型特点在于防止用户错误的修改映射。

from types import MappingProxyType
Prize_number={"Ailee": 3, "Bob": 5, "Cindy": 5}
dict6=MappingProxyType(Prize_number)
dict6["Ailee"]=6#不支持改动。TypeError: "mappingproxy" object does not support item assignment
print(dict6)

Prize_number["Ailee"]=6
print(dict6)#{"Ailee": 6, "Bob": 5, "Cindy": 5}原映射改动可视。

collections.OrderedDict
OrderedDict能够记住key的插入先后顺序。
eg:

from _collections import OrderedDict
d = {"banana": 3, "apple": 4, "pear": 1, "orange": 2}
print(OrderedDict(sorted(d.items())))
print(OrderedDict(sorted(d.items(),key=lambda t :t[1])))

输出：

OrderedDict([("apple", 4), ("banana", 3), ("orange", 2), ("pear", 1)])
OrderedDict([("pear", 1), ("orange", 2), ("banana", 3), ("apple", 4)])

在之前第二章namedtuple中也提到过。namedtuple的实例方法_asdict()把具名元组以collections.OrderedDict的形式返回。

collections.ChainMap
ChainMap可以容纳数个不同的映射对象，然后在进行键查找操作的时候，这些对象会被当成一个整体被逐个查找，直到键被找到为止。
查询规则片段：

import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))

想了解更多：
https://docs.python.org/3/lib...
collections.Counter
counter用来统计目标集合中不同的元素及其频数，利用most_common([n])返回前n个频数最高的值以及相应的计数。

eg:

from collections import Counter
ct=Counter("wasffffdsasd")
print(ct)#Counter({"d": 4, "s": 3, "a": 2, "w": 1})
ct.update("dassffffd")
print(ct.most_common(2))#[("d", 8), ("s", 5)]

定义：Python标准文库给出的定义：A set object is an unordered collection of distinct hashable objects.
翻译过来就是：set是一个包含不同可散列对象的无序集合
种类：集合这种数据结构包含set和frozenset，两者的区别在于后者不可变而前者可变，类似于元组之于列表。因此frozenset相比set不具备修改一类的方法。
本质：集合是许多唯一对象的聚集，所以可以用来去重。
新建set：

在大括号中直接填写元素，类似字典
set1={"apple","banana","pear"}

利用构造方法set()，类似list()
set4=set("apple")

空集的构造
注意空集的构造只能用set()而不能用{}，{}是空字典而非空集
set3=set()

新建frozenset：

只能使用构造方法frozenset()
frozenset1=frozenset(range(5))
print(frozenset1)#frozenset({0, 1, 2, 3, 4})
只能使用此方法的原因是Python中没有针对frozenset的特殊字面量句法（对于列表的字面量句法就是[]这样子 ）。

集合推导：
集合推导在大括号中进行，思路与列表推导，字典推导类似。
eg:

set3={chr(i)for i in range(100,110)}
print(set3)#{"k", "f", "i", "e", "d", "m", "l", "g", "j", "h"}

set的操作方法包含frozenset的操作方法，区别在于frozenset不支持就地改变集合的方法，这一点与元组很类似。
下面展示set的操作方法，其中涉及修改本身的不适用于frozenset

集合的数学操作

集合的比较操作

集合的实用操作

若想深入理解dict和set，首先需要了解它们背后的散列表。

散列（hashing）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。也译为散列。旧译哈希（误以为是人名而采用了音译）。它也常用作一种资讯安全的实作方法，由一串资料中经过散列算法（Hashing algorithms）计算出来的资料指纹（data fingerprint），经常用来识别档案与资料是否有被窜改，以保证档案与资料确实是由原创者所提供。

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

减少冲突的方法：

开放定址法
开放定址法就是产生冲突之后去寻找下一个空闲的空间。函数定义为：

其中，hash(key)是哈希函数，di是增量序列，i为已冲突的次数。

链表法
散列到同一位置的元素，不是继续往下探测，而是在这个位置是一个链表，这些元素则都放到这一个链表上。java的HashMap就采用的是这个。

再散列
如果一次不够，就再来一次，直到冲突不再发生。

建立公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(注意：在这个方法里面是把元素分开两个表来存储)。

散列表的存储特点：
衡量散列表的利用率有一个概念叫做载荷因子：

`α= 已有的元素个数/表的长度`

载荷因子越大，插入到散列表中的元素越多，产生冲突的概率随之增大。因此通常载荷因子被设计成0.75，保证一定的表元是空的。
散列表的存储特点决定了它耗费存储空间的特点。

散列表本质要解决的是查找时间的问题。如果顺序查找的话，时间复杂度为O(n)；而散列表，时间复杂度则为O(1)！直接甩了一个次元，这也就是为什么在大量数据存储查找的时候，散列表得到大量应用的原因。

注：散列表知识引自
作者：SakuraWood
链接：https://juejin.im/post/5a1bd0...
来源：掘金

给定一个键，要么返回查询值，要么抛出keyerror。

键必须是可散列的
可散列对象满足的要求
(1)支持hash()函数，并且通过hash()得到的散列值是不变的；
(2)支持通过__eq__()方法来检测相等性；
(3)若a==b为真，则hash(a)=hash(b)也为真。
原子不可变数据类型都是可散列类型。例如：字符串，字节，数值类型

字典很消耗内存
原因在于减少冲突的发生

键查询很快
时间复杂度为o(1)，列表的遍历查找对应的时间复杂度为o(n)。当数据规模较大时可以明显发现散列表查询快人一大步。

键的次序取决于添加顺序

向字典里添加新键可能会改变已有键的顺序
当载荷因子增大到一定程度时（0.75），Python解释器会为字典扩容，把原字典的元素存储到新的散列表中。新的存储过程中有可能发生散列冲突，导致新散列表中键的次序发生变化。

Tips:不要对字典同时进行修改和迭代。因为你的修改有可能导致键的次序发生变化，从而在迭代中遗漏某些数据

集合里的元素必须是可散列的

集合很消耗内存

可以很高效地判断元素是否存在于某个集合

元素的次序取决于被添加到集合里的次序

向集合里添加新元素可能会改变已有元素的顺序