摘要：若對于關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為均勻散列函數，這就是使關鍵字經過散列函數得到一個隨機的地址，從而減少沖突。

導語：本文章記錄了本人在學習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:不要對字典同時進行修改和迭代。因為你的修改有可能導致鍵的次序發生變化，從而在迭代中遺漏某些數據

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

集合很消耗內存

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

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

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