摘要:如果要把一個對象放入散列表,那么首先要計算這個元素的散列值。總結這一篇主要介紹了常見的字典方法如何處理查不到的鍵標準庫中類型的變種散列表的工作原理散列表帶來的潛在影響參考鏈接最后,感謝女朋友支持。
泛映射類型這一篇是《流暢的 python》讀書筆記。主要介紹:
常見的字典方法
如何處理查不到的鍵
標準庫中 dict 類型的變種
散列表的工作原理
collections.abc 模塊中有 Mapping 和 MutableMapping 這兩個抽象基類,它們的作用是為 dict 和其他類似的類型定義形式接口。
標準庫里所有映射類型都是利用 dict 來實現的,它們有個共同的限制,即只有可散列的數據類型才能用做這些映射里的鍵。
問題: 什么是可散列的數據類型?
在 python 詞匯表(https://docs.python.org/3/glossary.html#term-hashable)中,關于可散列類型的定義是這樣的:
如果一個對象是可散列的,那么在這個對象的生命周期中,它的散列值是不變的,而且這個對象需要實現 __hash__() 方法。另外可散列對象還要有 __eq__() 方法,這樣才能跟其他鍵做比較。如果兩個可散列對象是相等的,那么它們的散列只一定是一樣的
根據這個定義,原子不可變類型(str,bytes和數值類型)都是可散列類型,frozenset 也是可散列的(因為根據其定義,frozenset 里只能容納可散列類型),如果元組內都是可散列類型的話,元組也是可散列的(元組雖然是不可變類型,但如果它里面的元素是可變類型,這種元組也不能被認為是不可變的)。
一般來講,用戶自定義的類型的對象都是可散列的,散列值就是它們的 id() 函數的返回值,所以這些對象在比較的時候都是不相等的。(如果一個對象實現了 eq 方法,并且在方法中用到了這個對象的內部狀態的話,那么只有當所有這些內部狀態都是不可變的情況下,這個對象才是可散列的。)
根據這些定義,字典提供了很多種構造方法,https://docs.python.org/3/library/stdtypes.html#mapping-types-dict 這個頁面有個例子來說明創建字典的不同方式。
>>> 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
除了這些方法以外,還可以用字典推導的方式來建造新 dict。
字典推導自 Python2.7 以來,列表推導和生成器表達式的概念就移植到了字典上,從而有了字典推導。字典推導(dictcomp)可以從任何以鍵值對作為元素的可迭代對象中構建出字典。
比如:
>>> 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模塊內)。
default_factory 并不是一個方法,而是一個可調用對象,它的值 defaultdict 初始化的時候由用戶設定。
OrderedDict.popitem() 會移除字典最先插入的元素(先進先出);可選參數 last 如果值為真,則會移除最后插入的元素(后進先出)。
用 setdefault 處理找不到的鍵
當字典 d[k] 不能找到正確的鍵的時候,Python 會拋出異常,平時我們都使用d.get(k, default) 來代替 d[k],給找不到的鍵一個默認值,還可以使用效率更高的 setdefault
my_dict.setdefault(key, []).append(new_value) # 等同于 if key not in my_dict: my_dict[key] = [] my_dict[key].append(new_value)
這兩段代碼的效果一樣,只不過,后者至少要進行兩次鍵查詢,如果不存在,就是三次,而用 setdefault 只需一次就可以完成整個操作。
那么,我們取值的時候,該如何處理找不到的鍵呢?
映射的彈性查詢defaultdict:處理找不到的鍵的一個選擇有時候,就算某個鍵在映射里不存在,我們也希望在通過這個鍵讀取值的時候能得到一個默認值。有兩個途徑能幫我們達到這個目的,一個是通過 defaultdict 這個類型而不是普通的 dict,另一個是給自己定義一個 dict 的子類,然后在子類中實現 __missing__ 方法。
首先我們看下如何使用 defaultdict :
import collections index = collections.defaultdict(list) index[new_key].append(new_value)
這里我們新建了一個字典 index,如果鍵 new_key 在 index 中不存在,表達式 index[new_key] 會按以下步驟來操作:
調用 list() 來建立一個新的列表
把這個新列表作為值,"new_key" 作為它的鍵,放入 index 中
返回這個列表的引用。
而這個用來生成默認值的可調用對象存放在名為 default_factory 的實例屬性中。
特殊方法 missingdefaultdict 中的 default_factory 只會在 getitem 里調用,在其他方法中不會發生作用。比如 index[k] 這個表達式會調用 default_factory 創造的某個默認值,而 index.get(k) 則會返回 None。(這是因為特殊方法 missing 會在 defaultdict 遇到找不到的鍵的時候調用 default_factory,實際上,這個特性所有映射方法都可以支持)。
所有映射在處理找不到的鍵的時候,都會牽扯到 missing 方法。但基類 dict 并沒有提供 這個方法。不過,如果有一個類繼承了 dict ,然后這個繼承類提供了 missing 方法,那么在 getitem 碰到找不到鍵的時候,Python 會自動調用它,而不是拋出一個 KeyError 異常。
__missing__ 方法只會被 __getitem__ 調用。提供 missing 方法對 get 或者 __contains__(in 運算符會用到這個方法)這些方法的是有沒有影響。
下面這段代碼實現了 StrKeyDict0 類,StrKeyDict0 類在查詢的時候把非字符串的鍵轉化為字符串。
class StrKeyDict0(dict): # 繼承 dict def __missing__(self, key): if isinstance(key, str): # 如果找不到的鍵本身就是字符串,拋出 KeyError raise KeyError(key) # 如果找不到的鍵不是字符串,轉化為字符串再找一次 return self[str(key)] def get(self, key, default=None): # get 方法把查找工作用 self[key] 的形式委托給 __getitem__,這樣在宣布查找失敗錢,還能通過 __missing__ 再給鍵一個機會 try: return self[key] except KeyError: # 如果拋出 KeyError 說明 __missing__ 也失敗了,于是返回 default return default def __contains__(self, key): # 先按傳入的鍵查找,如果沒有再把鍵轉為字符串再找一次 return key in self.keys() or str(key) in self.keys()
contains 方法存在是為了保持一致性,因為 k in d 這個操作會調用它,但我們從 dict 繼承到的 contains 方法不會在找不到鍵的時候用 missing 方法。
my_dict.keys() 在 Python3 中返回值是一個 "視圖","視圖"就像是一個集合,而且和字典一樣速度很快。但在 Python2中,my_dict.keys() 返回的是一個列表。 所以 k in my_dict.keys() 操作在 python3中速度很快,但在 python2 中,處理效率并不高。
如果要自定義一個映射類型,合適的策略是繼承 collections.UserDict 類。這個類就是把標準 dict 用 python 又實現了一遍,UserDict 是讓用戶繼承寫子類的,改進后的代碼如下:
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): # 這里可以放心假設所有已經存儲的鍵都是字符串。因此只要在 self.data 上查詢就好了 return str(key) in self.data def __setitem__(self, key, item): # 這個方法會把所有的鍵都轉化成字符串。 self.data[str(key)] = item
因為 UserDict 繼承的是 MutableMapping,所以 StrKeyDict 里剩下的那些映射類型都是從 UserDict、MutableMapping 和 Mapping 這些超類繼承而來的。
Mapping 中提供了 get 方法,和我們在 StrKeyDict0 中定義的一樣,所以我們在這里不需要定義 get 方法。
字典的變種在 collections 模塊中,除了 defaultdict 之外還有其他的映射類型。
collections.OrderedDict
collections.ChainMap
collections.Counter
不可變的映射類型問題:標準庫中所有的映射類型都是可變的,如果我們想給用戶提供一個不可變的映射類型該如何處理呢?
從 Python3.3 開始 types 模塊中引入了一個封裝類名叫 MappingProxyType。如果給這個類一個映射,它會返回一個只讀的映射視圖(如果原映射做了改動,這個視圖的結果頁會相應的改變)。例如
>>> 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 "字典中的散列表TypeError: "MappingProxy" object does not support item assignment >>> d[2] = "B" >>> d_proxy[2] # d_proxy 是動態的,d 的改動會反饋到它上邊 "B"
散列表其實是一個稀疏數組(總有空白元素的數組叫稀疏數組),在 dict 的散列表中,每個鍵值都占用一個表元,每個表元都有兩個部分,一個是對鍵的引用,另一個是對值的引用。因為所有表元的大小一致,所以可以通過偏移量來讀取某個表元。
python 會設法保證大概有1/3 的表元是空的,所以在快要達到這個閾值的時候,原有的散列表會被復制到一個更大的空間。
如果要把一個對象放入散列表,那么首先要計算這個元素的散列值。
Python內置的 hash() 方法可以用于計算所有的內置類型對象。
散列表算法如果兩個對象在比較的時候是相等的,那么它們的散列值也必須相等。例如 1==1.0 那么,hash(1) == hash(1.0)
為了獲取 my_dict[search_key] 的值,Python 會首先調用 hash(search_key) 來計算 search_key 的散列值,把這個值的最低幾位當做偏移量在散列表中查找元。若表元為空,拋出 KeyError 異常。若不為空,則表元會有一對 found_key:found_value。
這時需要校驗 search_key == found_key,如果相等,返回 found_value。
如果不匹配(散列沖突),再在散列表中再取幾位,然后處理一下,用處理后的結果當做索引再找表元。 然后重復上面的步驟。
取值流程圖如下:
添加新值和上述的流程基本一致,只不過對于前者,在發現空表元的時候會放入一個新元素,而對于后者,在找到相應表元后,原表里的值對象會被替換成新值。
字典的優勢和限制 1、鍵必須是可散列的另外,在插入新值是,Python 可能會按照散列表的擁擠程度來決定是否重新分配內存為它擴容,如果增加了散列表的大小,那散列值所占的位數和用作索引的位數都會隨之增加
可散列對象要求如下:
支持 hash 函數,并且通過__hash__() 方法所得的散列值不變
支持通過 __eq__() 方法檢測相等性
若 a == b 為真, 則 hash(a) == hash(b) 也為真
2、字典開銷巨大因為字典使用了散列表,而散列表又必須是稀疏的,這導致它在空間上效率低下。
3、鍵查詢很快dict 的實現是典型的空間換時間:字典類型由著巨大的內存開銷,但提供了無視數據量大小的快速訪問。
4、鍵的次序決定于添加順序當往 dict 里添加新鍵而又發生散列沖突時,新建可能會被安排存放在另一個位置。
5、往字典里添加新鍵可能會改變已有鍵的順序無論何時向字典中添加新的鍵,Python 解釋器都可能做出為字典擴容的決定。擴容導致的結果就是要新建一個更大的散列表,并把原有的鍵添加到新的散列表中,這個過程中可能會發生新的散列沖突,導致新散列表中次序發生變化。
因此,不要對字典同時進行迭代和修改。
這一篇主要介紹了:
常見的字典方法
如何處理查不到的鍵
標準庫中 dict 類型的變種
散列表的工作原理
散列表帶來的潛在影響
參考鏈接https://docs.python.org/3/glossary.html#term-hashable
https://docs.python.org/3/library/stdtypes.html#mapping-types-dict
最后,感謝女朋友支持。
歡迎關注(April_Louisa) | 請我喝芬達 |
---|---|
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/44534.html
摘要:這種數據結構包含以下幾種常見的操作向關聯數組添加鍵值對從關聯數組內刪除鍵值對修改關聯數組內的鍵值對根據已知的鍵尋找值字典問題是設計一種能夠具備關聯數組特性的數據結構。 定義 Python中有一個叫作dictionary的對象類型,翻譯過來就是字典,用dict表示。 創建字典 創建空的字典 >>> mydict = {} >>> mydict {} >>> type(mydict) >...
摘要:字典的創建字典可以通過或一對花括號創建一個空字典。方法是字典對象名稱加方括號括起來的鍵名,比如。空字典的長度是和類似于對列表的操作,不過這兩個函數檢驗的是字典的鍵。修改了字典并沒有重新獲取,但是已經反應了變化,多了返回值的對象,。 字典(dict, dictionary的簡寫)是Python中另一個非常重要的內置數據類型,是Python中映射類型(Mapping Type),它把鍵(k...
摘要:本章主要介紹字典的概念,基本操作以及一些進階操作。使用字典在中,字典是一系列鍵值對。中用花括號來表示字典。代碼定義空字典的語法結果如果要修改字典中的值,只需通過鍵名訪問就行。 《Python編程:從入門到實踐》筆記。本章主要介紹字典的概念,基本操作以及一些進階操作。 1. 使用字典(Dict) 在Python中,字典是一系列鍵值對。每個鍵都與一個值相關聯,用鍵來訪問值。Python中用...
摘要:下面讓我們一塊來看下的中高級數據結構。到現在,我們學習了列表元組字典和集合種高級數據結構。 < 返回索引頁 高級數據結構 列表與元組 什么是列表 列表的操作 什么是元組 元組的操作 字典與集合 字典的定義 字典的操作 集合的定義 集合的操作 序列 序列的通用操作 可變類型和不可變類型 深copy和淺copy 總結 練習 參考 高級數據結構 我們知道P...
摘要:字典,這個東西你現在還用嗎隨著網絡的發展,用的人越來越少了。最早的名字叫伍記小字典,但未能編纂完成。新華字典由商務印書館出版。成為迄今為止世界出版史上最高發行量的字典。也被稱為關聯數組或哈希表。 字典,這個東西你現在還用嗎?隨著網絡的發展,用的人越來越少了。不少人習慣于在網上搜索,不僅有web版,乃至于已經有手機版的各種字典了。我曾經用過一本小小的《新華字典》。 《新華字典》是...
摘要:我們用函數,來簡單快捷地創建這個字典輸出結果與原先代碼一致。示例代碼如下版本為無序字典有序字典輸出的結果為無序字典有序字典默認字典是內建類的一個子類,第一個參數為屬性提供初始值,默認為。 ??字典(dict)結構是Python中常用的數據結構,筆者結合自己的實際使用經驗,對字典方面的相關知識做個小結,希望能對讀者一些啟發~ 創建字典 ??常見的字典創建方法就是先建立一個空字典,然后逐一...
閱讀 3689·2021-10-13 09:40
閱讀 3149·2021-10-09 09:53
閱讀 3551·2021-09-26 09:46
閱讀 1848·2021-09-08 09:36
閱讀 4248·2021-09-02 09:46
閱讀 1314·2019-08-30 15:54
閱讀 3179·2019-08-30 15:44
閱讀 1023·2019-08-30 11:06