摘要：若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)，這就是使關(guān)鍵字經(jīng)過(guò)散列函數(shù)得到一個(gè)隨機(jī)的地址，從而減少?zèng)_突。

導(dǎo)語(yǔ)：本文章記錄了本人在學(xué)習(xí)Python基礎(chǔ)之?dāng)?shù)據(jù)結(jié)構(gòu)篇的重點(diǎn)知識(shí)及個(gè)人心得，打算入門Python的朋友們可以來(lái)一起學(xué)習(xí)并交流。

本文重點(diǎn)：

1、掌握常見的字典創(chuàng)建，查詢，判別方法；
2、了解字典中的defaultdict、子類化Userdict和常見映射類型；
3、了解支撐字典和集合背后的散列表的工作原理。

分為字面量句法和構(gòu)造方法兩種，下面以{"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

以上五種方法創(chuàng)建的字典是相等的。

映射類型（Mapping Types）是一種關(guān)聯(lián)式的容器類型，它存儲(chǔ)了對(duì)象與對(duì)象之間的映射關(guān)系。
字典是Python中唯一的映射類型，它是存儲(chǔ)了若干鍵值對(duì)（由鍵映射到值）的關(guān)聯(lián)容器。

collections.abc模塊中有兩個(gè)抽象基類，分別是Mapping和MutableMapping，它們?yōu)閐ict和其他類似的類型定義形式接口。

isinstance：判定object的類型
語(yǔ)法：isinstance(object, classinfo)

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

若參數(shù)object是classinfo類的實(shí)例，或者object是classinfo類的子類的一個(gè)實(shí)例， 返回 True；若 object 不是一個(gè)給定類型的的對(duì)象，則返回結(jié)果總是False。

若classinfo不是一種數(shù)據(jù)類型或者由數(shù)據(jù)類型構(gòu)成的元組，將引發(fā)一個(gè)TypeError 異常。

eg:

from _collections_abc import Mapping
my_dict={}
print(isinstance(my_dict,Mapping))#判斷數(shù)據(jù)是否為廣義映射類型。輸出True.

isinstance和type的區(qū)別：
若對(duì)象是classinfo中一個(gè)類的子類，isinstance可以判斷出來(lái)返回True，而type是不能的。

字典推導(dǎo):在{}中使用命令語(yǔ)句加for甚至if實(shí)現(xiàn)迭代推導(dǎo)出新列表的操作。

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}#推導(dǎo)過(guò)程
print(dict1)

dict2={code:country.upper() for code,country in Country_Codes if code>80}#由限制要求創(chuàng)建字典
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])兩種方法都可以處理找不到的鍵的情況，區(qū)別在于setdefault在返回默認(rèn)值的同時(shí)能夠在原字典創(chuàng)建新的k-default鍵值對(duì)。
所以更新某個(gè)鍵值對(duì)但鍵不一定存在時(shí)，用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處理查不到的鍵時(shí)返回默認(rèn)值，但不會(huì)在原字典創(chuàng)建這個(gè)鍵.
dict3.setdefault("David","20")
print(dict3)#setdefault處理查不到的鍵時(shí)返回默認(rèn)值，并且會(huì)在原字典創(chuàng)建這個(gè)鍵.

格式：class collections.defaultdict([default_factory[, ...]])
defaultdict是內(nèi)建dict的子類，它能夠在查詢找不到的鍵時(shí)為其創(chuàng)造默認(rèn)值，由此避免拋出keyerror。其他功能與dict相同。

eg:defaultdict推導(dǎo)

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:查詢點(diǎn)名冊(cè)同學(xué)的出席次數(shù)

from _collections import defaultdict

namelist=["Ailee", "Bob", "Cindy", "Ailee", "Bob", "Cindy", "Cindy", "Cindy", "Bob", "Cindy", "Ailee", "Bob", "Bob"]
count=defaultdict(int)#使用記錄值數(shù)據(jù)結(jié)構(gòu)整型作為默認(rèn)的工廠函數(shù)

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

原理解釋：defaultdict在查詢找不到的鍵時(shí)會(huì)通過(guò)__getitem__調(diào)用__missing__，然后__missing__根據(jù)default_factory選擇返回默認(rèn)值。當(dāng)不輸入default_factory時(shí)，會(huì)拋出keyerror。
我們可以通過(guò)print (defaultdict.__missing__.__doc__)來(lái)看__missing__的內(nèi)部實(shí)現(xiàn)：

__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()#為找不到的鍵創(chuàng)建默認(rèn)值
  return value

注意：__missing__只能被__getitem__調(diào)用，調(diào)用__getitem__可用d[k]，d.get(k)無(wú)效。

default_factory的選擇

類型名稱作為初始化函數(shù)參數(shù)
此類設(shè)置根據(jù)創(chuàng)建字典的值的需求而定；
若值以整型記錄可用int；若用列表記錄多個(gè)數(shù)據(jù)可用list。

可調(diào)用函數(shù)作為初始化函數(shù)參數(shù)
使用任何不帶參數(shù)的可調(diào)用函數(shù)，并以該函數(shù)返回值作為默認(rèn)值。
仍以點(diǎn)名code為例，有兩種方法：
1）自定義函數(shù)：

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

2）使用lambda創(chuàng)建匿名函數(shù)

count=defaultdict(lambda :0)

UserDict繼承自抽象基類（abstract based class）中的MutableMapping。

UserDict是讓用戶繼承寫子類的。之所以傾向于從UserDict而不是dict繼承的原因是，這是因?yàn)樵诟采w重寫dict類的 get(k, default)、__setitem__( )、__contain__( )、__missing__( ) 等方法時(shí)，常常又會(huì)使用到 mapObj[k]、 k in mapObj、mapObj[k] 等語(yǔ)法形式，這樣一不小心就會(huì)造成這些內(nèi)部方法的無(wú)窮遞歸調(diào)用。但是UserDict就不會(huì)有此類問(wèn)題。

UserDict有一個(gè)data的屬性，是dict的實(shí)例。用戶定義UserDict的子類時(shí)如果重寫方法，并不會(huì)遞歸調(diào)用UserDict的其他方法，而是對(duì)UserDict.data進(jìn)行操作，這樣就減少了用戶自定義dict時(shí)防范死循環(huán)遞歸的難度。

eg:

import collections
class Modified_Dict(collections.UserDict):#繼承自UserDict
    def __missing__(self,key):
        if isinstance(key, str):#防止遞歸循環(huán)，及時(shí)拋出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類構(gòu)造字典
print(dict4["Ailee"])#輸出：3
dict4.update({"one":1,"two":2})
print(dict4)#輸出：{"Ailee": 3, "Bob": 5, "Cindy": 5, "one": 1, "two": 2}

錯(cuò)誤示范：這里應(yīng)該加圓括號(hào)建立自定義dict的空字典，否則之后的數(shù)據(jù)無(wú)法被更新

dict5=Modified_Dict
dict5.update({"one":1,"two":2})
print(dict5)#發(fā)現(xiàn)update失敗 -_-!

UserDict繼承自Mapping基類，諸如MutableMapping.update和Mapping.get也很實(shí)用。（截止2017.12.15 未掌握Mapping.get）

從Python3.3開始，type模塊引入了一個(gè)封裝類名叫做MappingProxyType。MappingProxyType提供一個(gè)可讀的動(dòng)態(tài)映射視圖，即用戶無(wú)法從這個(gè)視圖對(duì)原映射進(jìn)行改動(dòng)，但是原映射有改動(dòng)時(shí)可以通過(guò)這個(gè)視圖觀察到。
此類型特點(diǎn)在于防止用戶錯(cuò)誤的修改映射。

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

Prize_number["Ailee"]=6
print(dict6)#{"Ailee": 6, "Bob": 5, "Cindy": 5}原映射改動(dòng)可視。

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中也提到過(guò)。namedtuple的實(shí)例方法_asdict()把具名元組以collections.OrderedDict的形式返回。

collections.ChainMap
ChainMap可以容納數(shù)個(gè)不同的映射對(duì)象，然后在進(jìn)行鍵查找操作的時(shí)候，這些對(duì)象會(huì)被當(dāng)成一個(gè)整體被逐個(gè)查找，直到鍵被找到為止。
查詢規(guī)則片段：

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

想了解更多：
https://docs.python.org/3/lib...
collections.Counter
counter用來(lái)統(tǒng)計(jì)目標(biāo)集合中不同的元素及其頻數(shù)，利用most_common([n])返回前n個(gè)頻數(shù)最高的值以及相應(yīng)的計(jì)數(shù)。

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標(biāo)準(zhǔn)文庫(kù)給出的定義：A set object is an unordered collection of distinct hashable objects.
翻譯過(guò)來(lái)就是：set是一個(gè)包含不同可散列對(duì)象的無(wú)序集合
種類：集合這種數(shù)據(jù)結(jié)構(gòu)包含set和frozenset，兩者的區(qū)別在于后者不可變而前者可變，類似于元組之于列表。因此frozenset相比set不具備修改一類的方法。
本質(zhì)：集合是許多唯一對(duì)象的聚集，所以可以用來(lái)去重。
新建set：

在大括號(hào)中直接填寫元素，類似字典
set1={"apple","banana","pear"}

利用構(gòu)造方法set()，類似list()
set4=set("apple")

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

新建frozenset：

只能使用構(gòu)造方法frozenset()
frozenset1=frozenset(range(5))
print(frozenset1)#frozenset({0, 1, 2, 3, 4})
只能使用此方法的原因是Python中沒(méi)有針對(duì)frozenset的特殊字面量句法（對(duì)于列表的字面量句法就是[]這樣子 ）。

集合推導(dǎo)：
集合推導(dǎo)在大括號(hào)中進(jìn)行，思路與列表推導(dǎo)，字典推導(dǎo)類似。
eg:

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

set的操作方法包含frozenset的操作方法，區(qū)別在于frozenset不支持就地改變集合的方法，這一點(diǎn)與元組很類似。
下面展示set的操作方法，其中涉及修改本身的不適用于frozenset

集合的數(shù)學(xué)操作

集合的比較操作

集合的實(shí)用操作

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

散列（hashing）是電腦科學(xué)中一種對(duì)資料的處理方法，通過(guò)某種特定的函數(shù)/算法（稱為散列函數(shù)/算法）將要檢索的項(xiàng)與用來(lái)檢索的索引（稱為散列，或者散列值）關(guān)聯(lián)起來(lái)，生成一種便于搜索的數(shù)據(jù)結(jié)構(gòu)（稱為散列表）。也譯為散列。舊譯哈希（誤以為是人名而采用了音譯）。它也常用作一種資訊安全的實(shí)作方法，由一串資料中經(jīng)過(guò)散列算法（Hashing algorithms）計(jì)算出來(lái)的資料指紋（data fingerprint），經(jīng)常用來(lái)識(shí)別檔案與資料是否有被竄改，以保證檔案與資料確實(shí)是由原創(chuàng)者所提供。

若關(guān)鍵字為k，則其值存放在f(k)的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。稱這個(gè)對(duì)應(yīng)關(guān)系f為散列函數(shù)，按這個(gè)思想建立的表為散列表。

對(duì)不同的關(guān)鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現(xiàn)象稱為沖突。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來(lái)說(shuō)稱做同義詞。綜上所述，根據(jù)散列函數(shù)f(k)和處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲(chǔ)位置，這種表便稱為散列表，這一映射過(guò)程稱為散列造表或散列，所得的存儲(chǔ)位置稱散列地址。

若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就是使關(guān)鍵字經(jīng)過(guò)散列函數(shù)得到一個(gè)“隨機(jī)的地址”，從而減少?zèng)_突。

減少?zèng)_突的方法：

開放定址法
開放定址法就是產(chǎn)生沖突之后去尋找下一個(gè)空閑的空間。函數(shù)定義為：

其中，hash(key)是哈希函數(shù)，di是增量序列，i為已沖突的次數(shù)。

鏈表法
散列到同一位置的元素，不是繼續(xù)往下探測(cè)，而是在這個(gè)位置是一個(gè)鏈表，這些元素則都放到這一個(gè)鏈表上。java的HashMap就采用的是這個(gè)。

再散列
如果一次不夠，就再來(lái)一次，直到?jīng)_突不再發(fā)生。

建立公共溢出區(qū)
將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表(注意：在這個(gè)方法里面是把元素分開兩個(gè)表來(lái)存儲(chǔ))。

散列表的存儲(chǔ)特點(diǎn)：
衡量散列表的利用率有一個(gè)概念叫做載荷因子：

`α= 已有的元素個(gè)數(shù)/表的長(zhǎng)度`

載荷因子越大，插入到散列表中的元素越多，產(chǎn)生沖突的概率隨之增大。因此通常載荷因子被設(shè)計(jì)成0.75，保證一定的表元是空的。
散列表的存儲(chǔ)特點(diǎn)決定了它耗費(fèi)存儲(chǔ)空間的特點(diǎn)。

散列表本質(zhì)要解決的是查找時(shí)間的問(wèn)題。如果順序查找的話，時(shí)間復(fù)雜度為O(n)；而散列表，時(shí)間復(fù)雜度則為O(1)！直接甩了一個(gè)次元，這也就是為什么在大量數(shù)據(jù)存儲(chǔ)查找的時(shí)候，散列表得到大量應(yīng)用的原因。

注：散列表知識(shí)引自
作者：SakuraWood
鏈接：https://juejin.im/post/5a1bd0...
來(lái)源：掘金

給定一個(gè)鍵，要么返回查詢值，要么拋出keyerror。

鍵必須是可散列的
可散列對(duì)象滿足的要求
(1)支持hash()函數(shù)，并且通過(guò)hash()得到的散列值是不變的；
(2)支持通過(guò)__eq__()方法來(lái)檢測(cè)相等性；
(3)若a==b為真，則hash(a)=hash(b)也為真。
原子不可變數(shù)據(jù)類型都是可散列類型。例如：字符串，字節(jié)，數(shù)值類型

字典很消耗內(nèi)存
原因在于減少?zèng)_突的發(fā)生

鍵查詢很快
時(shí)間復(fù)雜度為o(1)，列表的遍歷查找對(duì)應(yīng)的時(shí)間復(fù)雜度為o(n)。當(dāng)數(shù)據(jù)規(guī)模較大時(shí)可以明顯發(fā)現(xiàn)散列表查詢快人一大步。

鍵的次序取決于添加順序

向字典里添加新鍵可能會(huì)改變已有鍵的順序
當(dāng)載荷因子增大到一定程度時(shí)（0.75），Python解釋器會(huì)為字典擴(kuò)容，把原字典的元素存儲(chǔ)到新的散列表中。新的存儲(chǔ)過(guò)程中有可能發(fā)生散列沖突，導(dǎo)致新散列表中鍵的次序發(fā)生變化。

Tips:不要對(duì)字典同時(shí)進(jìn)行修改和迭代。因?yàn)槟愕男薷挠锌赡軐?dǎo)致鍵的次序發(fā)生變化，從而在迭代中遺漏某些數(shù)據(jù)

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

集合很消耗內(nèi)存

可以很高效地判斷元素是否存在于某個(gè)集合

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

向集合里添加新元素可能會(huì)改變已有元素的順序