關(guān)于Python數(shù)據(jù)結(jié)構(gòu)中字典的心得
本篇主要介紹:常見的字典方法、如何處理查不到的鍵、標(biāo)準(zhǔn)庫中 dict 類型的變種、散列表的工作原理等。一下是全部內(nèi)容:
泛映射類型
collections.abc 模塊中有 Mapping 和 MutableMapping 這兩個(gè)抽象基類,它們的作用是為 dict 和其他類似的類型定義形式接口。
標(biāo)準(zhǔn)庫里所有映射類型都是利用 dict 來實(shí)現(xiàn)的,它們有個(gè)共同的限制,即只有可散列的數(shù)據(jù)類型才能用做這些映射里的鍵。
問題: 什么是可散列的數(shù)據(jù)類型?
在 python 詞匯表(https://docs.python.org/3/glossary.html#term-hashable)中,關(guān)于可散列類型的定義是這樣的:
如果一個(gè)對象是可散列的,那么在這個(gè)對象的生命周期中,它的散列值是不變的,而且這個(gè)對象需要實(shí)現(xiàn) __hash__()
方法。另外可散列對象還要有 __eq__()
方法,這樣才能跟其他鍵做比較。如果兩個(gè)可散列對象是相等的,那么它們的散列只一定是一樣的
根據(jù)這個(gè)定義,原子不可變類型(str,bytes和數(shù)值類型)都是可散列類型,frozenset 也是可散列的(因?yàn)楦鶕?jù)其定義,frozenset 里只能容納可散列類型),如果元組內(nèi)都是可散列類型的話,元組也是可散列的(元組雖然是不可變類型,但如果它里面的元素是可變類型,這種元組也不能被認(rèn)為是不可變的)。
一般來講,用戶自定義的類型的對象都是可散列的,散列值就是它們的 id() 函數(shù)的返回值,所以這些對象在比較的時(shí)候都是不相等的。(如果一個(gè)對象實(shí)現(xiàn)了 eq 方法,并且在方法中用到了這個(gè)對象的內(nèi)部狀態(tài)的話,那么只有當(dāng)所有這些內(nèi)部狀態(tài)都是不可變的情況下,這個(gè)對象才是可散列的。)
根據(jù)這些定義,字典提供了很多種構(gòu)造方法,https://docs.python.org/3/library/stdtypes.html#mapping-types-dict 這個(gè)頁面有個(gè)例子來說明創(chuàng)建字典的不同方式。
>>> a = dict(one=1, two=2, three=3) >>> b = {'one': 1, 'two': 2, 'three': 3} >>> c = dict(zip(['one', 'two', 'three'], [1, 2, 3])) >>> d = dict([('two', 2), ('one', 1), ('three', 3)]) >>> e = dict({'three': 3, 'one': 1, 'two': 2}) >>> a == b == c == d == e True
除了這些方法以外,還可以用字典推導(dǎo)的方式來建造新 dict。
字典推導(dǎo)
自 Python2.7 以來,列表推導(dǎo)和生成器表達(dá)式的概念就移植到了字典上,從而有了字典推導(dǎo)。字典推導(dǎo)(dictcomp)可以從任何以鍵值對作為元素的可迭代對象中構(gòu)建出字典。
比如:
>>> data = [(1, 'a'), (2, 'b'), (3, 'c')] >>> data_dict = {num: letter for num, letter in data} >>> data_dict {1: 'a', 2: 'b', 3: 'c'}
常見的映射方法
下表為我們展示了 dict、defaultdict 和 OrderedDict 的常見方法(后兩種是 dict 的變種,位于 collections模塊內(nèi))。
default_factory 并不是一個(gè)方法,而是一個(gè)可調(diào)用對象,它的值 defaultdict 初始化的時(shí)候由用戶設(shè)定。 OrderedDict.popitem() 會移除字典最先插入的元素(先進(jìn)先出);可選參數(shù) last 如果值為真,則會移除最后插入的元素(后進(jìn)先出)。用 setdefault 處理找不到的鍵
當(dāng)字典 d[k] 不能找到正確的鍵的時(shí)候,Python 會拋出異常,平時(shí)我們都使用d.get(k, default)
來代替 d[k],給找不到的鍵一個(gè)默認(rèn)值,還可以使用效率更高的 setdefault
my_dict.setdefault(key, []).append(new_value) # 等同于 if key not in my_dict: my_dict[key] = [] my_dict[key].append(new_value)
這兩段代碼的效果一樣,只不過,后者至少要進(jìn)行兩次鍵查詢,如果不存在,就是三次,而用 setdefault
只需一次就可以完成整個(gè)操作。
那么,我們?nèi)≈档臅r(shí)候,該如何處理找不到的鍵呢?
映射的彈性查詢
有時(shí)候,就算某個(gè)鍵在映射里不存在,我們也希望在通過這個(gè)鍵讀取值的時(shí)候能得到一個(gè)默認(rèn)值。有兩個(gè)途徑能幫我們達(dá)到這個(gè)目的,一個(gè)是通過 defaultdict 這個(gè)類型而不是普通的 dict,另一個(gè)是給自己定義一個(gè) dict 的子類,然后在子類中實(shí)現(xiàn) __missing__
方法。
defaultdict:處理找不到的鍵的一個(gè)選擇
首先我們看下如何使用 defaultdict :
import collections index = collections.defaultdict(list) index[new_key].append(new_value)
這里我們新建了一個(gè)字典 index,如果鍵 new_key
在 index 中不存在,表達(dá)式 index[new_key]
會按以下步驟來操作:
調(diào)用 list() 來建立一個(gè)新的列表把這個(gè)新列表作為值,'new_key' 作為它的鍵,放入 index 中返回這個(gè)列表的引用。
而這個(gè)用來生成默認(rèn)值的可調(diào)用對象存放在名為 default_factory
的實(shí)例屬性中。
defaultdict 中的 default_factory 只會在 getitem 里調(diào)用,在其他方法中不會發(fā)生作用。比如 index[k] 這個(gè)表達(dá)式會調(diào)用 default_factory 創(chuàng)造的某個(gè)默認(rèn)值,而 index.get(k) 則會返回 None。(這是因?yàn)樘厥夥椒?missing 會在 defaultdict 遇到找不到的鍵的時(shí)候調(diào)用 default_factory,實(shí)際上,這個(gè)特性所有映射方法都可以支持)。
特殊方法 missing
所有映射在處理找不到的鍵的時(shí)候,都會牽扯到 missing 方法。但基類 dict 并沒有提供 這個(gè)方法。不過,如果有一個(gè)類繼承了 dict ,然后這個(gè)繼承類提供了 missing 方法,那么在 getitem 碰到找不到鍵的時(shí)候,Python 會自動(dòng)調(diào)用它,而不是拋出一個(gè) KeyError 異常。
__missing__
方法只會被 __getitem__
調(diào)用。提供 missing 方法對 get 或者 __contains__(in 運(yùn)算符會用到這個(gè)方法)這些方法的是有沒有影響。
下面這段代碼實(shí)現(xiàn)了 StrKeyDict0 類,StrKeyDict0 類在查詢的時(shí)候把非字符串的鍵轉(zhuǎn)化為字符串。
class StrKeyDict0(dict): # 繼承 dict def __missing__(self, key): if isinstance(key, str): # 如果找不到的鍵本身就是字符串,拋出 KeyError raise KeyError(key) # 如果找不到的鍵不是字符串,轉(zhuǎn)化為字符串再找一次 return self[str(key)] def get(self, key, default=None): # get 方法把查找工作用 self[key] 的形式委托給 __getitem__,這樣在宣布查找失敗錢,還能通過 __missing__ 再給鍵一個(gè)機(jī)會 try: return self[key] except KeyError: # 如果拋出 KeyError 說明 __missing__ 也失敗了,于是返回 default return default def __contains__(self, key): # 先按傳入的鍵查找,如果沒有再把鍵轉(zhuǎn)為字符串再找一次 return key in self.keys() or str(key) in self.keys()
contains 方法存在是為了保持一致性,因?yàn)?k in d 這個(gè)操作會調(diào)用它,但我們從 dict 繼承到的 contains 方法不會在找不到鍵的時(shí)候用 missing 方法。
my_dict.keys() 在 Python3 中返回值是一個(gè) "視圖","視圖"就像是一個(gè)集合,而且和字典一樣速度很快。但在 Python2中,my_dict.keys() 返回的是一個(gè)列表。 所以 k in my_dict.keys() 操作在 python3中速度很快,但在 python2 中,處理效率并不高。
如果要自定義一個(gè)映射類型,合適的策略是繼承 collections.UserDict
類。這個(gè)類就是把標(biāo)準(zhǔn) dict 用 python 又實(shí)現(xiàn)了一遍,UserDict 是讓用戶繼承寫子類的,改進(jìn)后的代碼如下:
import collections class StrKeyDict(collections.UserDict): def __missing__(self, key): if isinstance(key, str): raise KeyError(key) return self[str(key)] def __contains__(self, key): # 這里可以放心假設(shè)所有已經(jīng)存儲的鍵都是字符串。因此只要在 self.data 上查詢就好了 return str(key) in self.data def __setitem__(self, key, item): # 這個(gè)方法會把所有的鍵都轉(zhuǎn)化成字符串。 self.data[str(key)] = item
因?yàn)?UserDict 繼承的是 MutableMapping,所以 StrKeyDict 里剩下的那些映射類型都是從 UserDict、MutableMapping 和 Mapping 這些超類繼承而來的。
Mapping 中提供了 get 方法,和我們在 StrKeyDict0 中定義的一樣,所以我們在這里不需要定義 get 方法。
字典的變種
在 collections 模塊中,除了 defaultdict 之外還有其他的映射類型。
collections.OrderedDict collections.ChainMap collections.Counter 不可變的映射類型
問題:標(biāo)準(zhǔn)庫中所有的映射類型都是可變的,如果我們想給用戶提供一個(gè)不可變的映射類型該如何處理呢?
從 Python3.3 開始 types 模塊中引入了一個(gè)封裝類名叫 MappingProxyType
。如果給這個(gè)類一個(gè)映射,它會返回一個(gè)只讀的映射視圖(如果原映射做了改動(dòng),這個(gè)視圖的結(jié)果頁會相應(yīng)的改變)。例如
>>> from types import MappingProxy Type >>> d = {1: 'A'} >>> d_proxy = MappingProxyType(d) >>> d_proxy mappingproxy({1: 'A'}) >>> d_proxy[1] 'A' >>> d_proxy[2] = 'x' Traceback(most recent call last): File "<stdin", line 1, in <module> TypeError: 'MappingProxy' object does not support item assignment >>> d[2] = 'B' >>> d_proxy[2] # d_proxy 是動(dòng)態(tài)的,d 的改動(dòng)會反饋到它上邊 'B'
字典中的散列表
散列表其實(shí)是一個(gè)稀疏數(shù)組(總有空白元素的數(shù)組叫稀疏數(shù)組),在 dict 的散列表中,每個(gè)鍵值都占用一個(gè)表元,每個(gè)表元都有兩個(gè)部分,一個(gè)是對鍵的引用,另一個(gè)是對值的引用。因?yàn)樗斜碓拇笮∫恢拢钥梢酝ㄟ^偏移量來讀取某個(gè)表元。
python 會設(shè)法保證大概有1/3 的表元是空的,所以在快要達(dá)到這個(gè)閾值的時(shí)候,原有的散列表會被復(fù)制到一個(gè)更大的空間。
如果要把一個(gè)對象放入散列表,那么首先要計(jì)算這個(gè)元素的散列值。
Python內(nèi)置的 hash() 方法可以用于計(jì)算所有的內(nèi)置類型對象。
如果兩個(gè)對象在比較的時(shí)候是相等的,那么它們的散列值也必須相等。例如 1==1.0 那么,hash(1) == hash(1.0)
散列表算法
為了獲取 my_dict[search_key] 的值,Python 會首先調(diào)用 hash(search_key) 來計(jì)算 search_key 的散列值,把這個(gè)值的最低幾位當(dāng)做偏移量在散列表中查找元。若表元為空,拋出 KeyError 異常。若不為空,則表元會有一對 found_key:found_value。
這時(shí)需要校驗(yàn) search_key == found_key,如果相等,返回 found_value。
如果不匹配(散列沖突),再在散列表中再取幾位,然后處理一下,用處理后的結(jié)果當(dāng)做索引再找表元。 然后重復(fù)上面的步驟。
取值流程圖如下:
添加新值和上述的流程基本一致,只不過對于前者,在發(fā)現(xiàn)空表元的時(shí)候會放入一個(gè)新元素,而對于后者,在找到相應(yīng)表元后,原表里的值對象會被替換成新值。
另外,在插入新值是,Python 可能會按照散列表的擁擠程度來決定是否重新分配內(nèi)存為它擴(kuò)容,如果增加了散列表的大小,那散列值所占的位數(shù)和用作索引的位數(shù)都會隨之增加字典的優(yōu)勢和限制
1、鍵必須是可散列的
可散列對象要求如下:
支持 hash 函數(shù),并且通過__hash__() 方法所得的散列值不變支持通過 __eq__() 方法檢測相等性若 a == b 為真, 則 hash(a) == hash(b) 也為真
2、字典開銷巨大
因?yàn)樽值涫褂昧松⒘斜?,而散列表又必須是稀疏的,這導(dǎo)致它在空間上效率低下。
3、鍵查詢很快
dict 的實(shí)現(xiàn)是典型的空間換時(shí)間:字典類型由著巨大的內(nèi)存開銷,但提供了無視數(shù)據(jù)量大小的快速訪問。
4、鍵的次序決定于添加順序
當(dāng)往 dict 里添加新鍵而又發(fā)生散列沖突時(shí),新建可能會被安排存放在另一個(gè)位置。
5、往字典里添加新鍵可能會改變已有鍵的順序
無論何時(shí)向字典中添加新的鍵,Python 解釋器都可能做出為字典擴(kuò)容的決定。擴(kuò)容導(dǎo)致的結(jié)果就是要新建一個(gè)更大的散列表,并把原有的鍵添加到新的散列表中,這個(gè)過程中可能會發(fā)生新的散列沖突,導(dǎo)致新散列表中次序發(fā)生變化。
因此,不要對字典同時(shí)進(jìn)行迭代和修改。
- Python基礎(chǔ)學(xué)習(xí)之基本數(shù)據(jù)結(jié)構(gòu)詳解【數(shù)字、字符串、列表、元組、集合、字典】
- Python基本數(shù)據(jù)結(jié)構(gòu)之字典類型dict用法分析
- Python基本數(shù)據(jù)結(jié)構(gòu)與用法詳解【列表、元組、集合、字典】
- Python cookbook(數(shù)據(jù)結(jié)構(gòu)與算法)通過公共鍵對字典列表排序算法示例
- Python實(shí)現(xiàn)列表轉(zhuǎn)換成字典數(shù)據(jù)結(jié)構(gòu)的方法
- Python中3種內(nèi)建數(shù)據(jù)結(jié)構(gòu):列表、元組和字典
- Python中列表、字典、元組、集合數(shù)據(jù)結(jié)構(gòu)整理
- python常用數(shù)據(jù)結(jié)構(gòu)字典梳理
相關(guān)文章
Python configparser模塊應(yīng)用過程解析
這篇文章主要介紹了Python configparser模塊應(yīng)用過程解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08tensorflow2.10使用BERT實(shí)現(xiàn)Semantic Similarity過程解析
這篇文章主要為大家介紹了tensorflow2.10使用BERT實(shí)現(xiàn)Semantic Similarity過程解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-04-04Python編寫一個(gè)多線程的12306搶票程序的示例
對于很多人來說,搶購火車票人們成了一個(gè)令人頭疼的問題,本文主要介紹了Python編寫一個(gè)多線程的12306搶票程序的示例,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09Python+OpenCV繪制多instance的Mask圖像
Mask圖像中,不同值表示不同的實(shí)例(instance)。本文將詳細(xì)為大家講講如何利用OpenCV繪制多instance的Mask圖像,感興趣的可以學(xué)習(xí)一下2022-06-06Python使用tkinter實(shí)現(xiàn)小時(shí)鐘效果
這篇文章主要為大家詳細(xì)介紹了Python使用tkinter實(shí)現(xiàn)小時(shí)鐘效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-02-02