• Python里的dict和set的效率有多高?
• 為什么它們是無序的?
• 為什么并不是所有的Python對象都可以當(dāng)作dict的鍵或set里的元素?
• 為什么dict的鍵和set的元素的順序是根據(jù)它們被添加的次序而定的,以及為什么在映射對象的生命周期中,這個(gè)順序并不是一成不變的?
• 為什么不應(yīng)該在迭代循環(huán)dict或是set的同時(shí)往里添加元素?

Python里的dict和set的效率有多高?

由實(shí)驗(yàn)得知,不管查詢有多少個(gè)元素的字典或集合,所耗費(fèi)的時(shí)間都能忽略不計(jì)(前提是字典或者集合不超過內(nèi)存大小).

字典中的散列表

散列表其實(shí)是一個(gè)稀疏數(shù)組(總是有空白元素的數(shù)組被稱為稀疏數(shù)組).在一般的數(shù)據(jù)結(jié)構(gòu)教材中,散列表里的單元通常叫作表元(bucket).

在dict的散列表當(dāng)中,每個(gè)鍵值對都占用一個(gè)表元,每個(gè)表元都有兩個(gè)部分,一個(gè)是對鍵的引用,另一個(gè)是對值的引用.

因?yàn)樗械谋碓拇笮∫恢?所以可以通過偏移量來讀取某個(gè)表元.

Python會(huì)設(shè)法保證大概還有三分之一的表元是空的,所以在快要達(dá)到這個(gè)閾值的時(shí)候,原有散列表會(huì)被復(fù)制到一個(gè)更大的空間里面.

如果要把一個(gè)對象放入散列表,那么首先要計(jì)算這個(gè)元素鍵的散列值.Python中可以用hash()方法來做這件事情.

1.散列值和相等性

內(nèi)置的hash()方法可以用于所有的內(nèi)置類型對象.如果是自定義對象調(diào)用hash()的話,實(shí)際上運(yùn)行的是自定義的__hash__.

如果這兩個(gè)對象在比較的時(shí)候是相等的,那么它們的散列值必須相等,否則散列表就不能正常運(yùn)行了.

例如,如果11.0為真,那么hash(1)hash(1.0)也必須為真,但其實(shí)這兩個(gè)數(shù)字(整型和浮點(diǎn))的內(nèi)部結(jié)構(gòu)是完全不一樣的.

既然提到了整型,CPython的實(shí)現(xiàn)細(xì)節(jié)里有一條是:如果有一個(gè)整型對象,而且它能被存進(jìn)一個(gè)機(jī)器字中,那么它的散列值就是它本身的值.

為了讓散列值能夠勝任散列表索引這一角色,它們必須在索引空間中盡量分散開來.這意味著在最理想的狀況下,越是相似但不相等的對象,它們散列值的差別應(yīng)該越大.

"""
import sys
# 通過sys.maxsize獲取操作系統(tǒng)的整數(shù)最大值,轉(zhuǎn)換成二進(jìn)制,計(jì)算位數(shù),加上一個(gè)符號(hào)位
MAX_BITS = len(format(sys.maxsize, 'b'))
print('%s-bit Python build' % (MAX_BITS + 1))
def hash_diff(o1, o2):
 h1 = '{:>0{}b}'.format(hash(o1), MAX_BITS)  # 計(jì)算o1的散列值,并用0補(bǔ)滿空位
 h2 = '{:>0{}b}'.format(hash(o2), MAX_BITS)  # 計(jì)算o2的散列值,并用0補(bǔ)滿空位
 # 比較h1和h2的每一位,用!標(biāo)識(shí)出來,否則用' '表示
 diff = ''.join('!' if b1 != b2 else ' ' for b1, b2 in zip(h1, h2))
 count = '!={}'.format(diff.count('!'))  # 顯示不同的總數(shù)
 width = max(len(repr(o1)), len(repr(o2)), 8)  # 行頭的寬度
 sep = '_' * (width * 2 + MAX_BITS)  # 分割線
 return '{!r:{width}} {}\n{:{width}} {} {}\n{!r:{width}} {}\n{}'.format(
  o1, h1, ' ' * width, diff, count, o2, h2, sep, width=width
 )
print(hash_diff(1, 1.0))
print(hash_diff(1.0, 1.0001))
print(hash_diff(1.0001, 1.0002))
print(hash_diff(1.0002, 1.0003))

從Python3.3開始,str,bytes和datetime對象的散列值計(jì)算過程中多了隨機(jī)的'加鹽'這一步.

所加鹽值是Python進(jìn)程內(nèi)的一個(gè)常量,但是每次啟動(dòng)Python解釋器都會(huì)生成一個(gè)不同的鹽值.

隨機(jī)鹽值的加入是為了防止DOS攻擊而采取的一種安全措施.

散列表算法

為了獲取my_dict[search_key]背后的值,Python首先會(huì)調(diào)用hash(search_key)來計(jì)算search_key的散列值,把這個(gè)值最低的幾位數(shù)字當(dāng)作偏移量,在散列表里查找表元(具體取幾位,得看當(dāng)前散列表的大小).若找到的表元是空的,則拋出KeyError異常.

若不是空的,則表元里會(huì)有一對found_key:found_value.這時(shí)候Python會(huì)檢驗(yàn)search_key == found_key是否為真,如果是,就會(huì)返回found_value.

如果search_key和found_key不匹配的話,這種情況稱為[散列沖突].發(fā)生這種情況是因?yàn)?散列表所做的其實(shí)是把隨機(jī)的元素映射到只有幾位的數(shù)字上,而散列表本身的索引又只能依賴于這個(gè)數(shù)字的一部分.為了解決散列沖突,算法會(huì)在散列值中另外再取幾位,然后用特殊的方法處理一下,把新得到的數(shù)字再當(dāng)作索引來尋找表元.

若這次找到的表元是空的,則同樣拋出KeyError;若非空,或者鍵匹配,則返回這個(gè)值;或者又發(fā)現(xiàn)了散列沖突,則重復(fù)以上的步驟.

從字典中取值的算法流程如下:給定一個(gè)鍵,這個(gè)算法要么返回一個(gè)值,要么拋出KeyError異常

|-------------------------------------------------------------------------|
|計(jì)算鍵的散列值________使用散列值的另一部分來定位散列表中的零一行 |
|  |  |↑|
|  |  || 否 (散列沖突)  |
|  |  ↓||
|使用散列值的一部分表元  ||
|來定位散列表中的一 ------→ 為空? ---------否-------→ 鍵相等?  |
|個(gè)表元|||
|  |是  |是 |
|  ↓ ↓|
|  拋出KeyError 返回表元里的值  |
|--------------------------------------------------------------------------|

添加新元素和更新現(xiàn)有鍵值的操作幾乎跟上面一樣.只不過對于前者,在發(fā)現(xiàn)空表元的時(shí)候會(huì)放入一個(gè)新元素;

對于后者,在找到對應(yīng)的表元后,原表里值對象會(huì)被替換成新值.

另外在插入新值時(shí),Python可能會(huì)按照散列表的擁擠程度來決定是否要重新分配內(nèi)存來為它擴(kuò)容.如果增加了散列表的大小,那散列值所占的位數(shù)和用作索引的位數(shù)就會(huì)隨之增加,這樣做的目的是為了減少發(fā)生散列沖突的概率.

表面上看,這個(gè)算法似乎很費(fèi)事,而實(shí)際上就是dict里有數(shù)百萬個(gè)元素,多數(shù)的搜索過程中并不會(huì)有沖突發(fā)生,平均下來每次搜索可能會(huì)有一到兩次沖突.

在正常情況下,就算是最不走運(yùn)的鍵所遇到的沖突的次數(shù)用一只手也能數(shù)過來.

dict的實(shí)現(xiàn)及其導(dǎo)致的結(jié)果

1.鍵必須死可散列的

一個(gè)可散列的對象必須滿足以下要求:

1)支持hash()函數(shù),并且通過__hash__()方法所得到的散列值是不變的.

2)支持通過__eq__()方法來檢測相等性.

3)若a == b為真,則hash(a) == hash(b)也為真

所有由用戶定義的對象默認(rèn)都是可散列的,因?yàn)樗鼈兩⒘兄涤蒳d()來獲取,而且它們都是不相等的.

如果你實(shí)現(xiàn)了一個(gè)類的__eq__()方法,并且希望它是可散列的,那么它一點(diǎn)要有個(gè)恰當(dāng)?shù)腳_hash__方法,保證a==b為真的情況下hash(a)==hash(b)也必定為真.

否則就會(huì)破壞恒定的散列表算法,導(dǎo)致由這些對象所組成的字典和集合完全失去可靠性,這個(gè)后果是非?？膳碌?

另一方面,如果一個(gè)含有自定義__eq__依賴的類處于可變的狀態(tài),那就不要在這個(gè)類中實(shí)現(xiàn)__hash__方法,因?yàn)樗膶?shí)例時(shí)不可散列的.

'''
學(xué)習(xí)中遇到問題沒人解答？小編創(chuàng)建了一個(gè)Python學(xué)習(xí)交流群：725638078
尋找有志同道合的小伙伴，互幫互助,群里還有不錯(cuò)的視頻學(xué)習(xí)教程和PDF電子書！
'''
class A:
 def __init__(self, a):
  self.a = a
 def __hash__(self):
  return 1
 def __eq__(self, other):
  return hash_diff(self, other)
 def __repr__(self):
  return str(self.a)
a = A(1)
b = A(2)
d1 = {a: 1, b: 2, 1: 3}
print(d1)  # {1: 3}  會(huì)發(fā)現(xiàn)里面只有一個(gè)鍵值對

2.字典在內(nèi)存上的開銷巨大

由于字典使用了散列表,而散列表又必須時(shí)稀疏的,這導(dǎo)致它在空間上的效率低下.舉例而言.如果你需要存放數(shù)量巨大的記錄,那么放在由元組或是具名元組構(gòu)成的列表中會(huì)是比較好的選擇;

最好不要根據(jù)JSON的風(fēng)格,用由字典組成的列表來存放這些記錄,用元組取代字典能節(jié)省空間的原因有兩個(gè):

其一是避免了散列表所消耗的空間. 其二是無需把記錄中字段的名字在每個(gè)元素里都存一遍.

在用戶自定義的類型中,__slots__屬性可以改變實(shí)例屬性的存儲(chǔ)方式,由dict變成tuple.

3.鍵查詢很快

dict的實(shí)現(xiàn)是典型的空間換時(shí)間:字典類型有著巨大的內(nèi)存開銷,但它們提供了無視數(shù)據(jù)量的快速訪問--只要字典能被裝在內(nèi)存里.

4.鍵的次序取決于添加順序

當(dāng)往dict里添加新鍵而又發(fā)生散列沖突的時(shí)候,新鍵可能會(huì)被安排存放到另一個(gè)位置.于是下面的這種情況就會(huì)發(fā)生:

由dict([(key1, value1), (key2, value2)])和dict([(key2, value2), (key1, value1)])得到的兩個(gè)字典,在進(jìn)行比較的時(shí)候,它們是相等的.

但是如果在key1和key2被添加到字典里的過程中有沖突發(fā)生的話,這兩個(gè)鍵出現(xiàn)在字典里的順序是不一樣的.

下面的示例展示了這個(gè)現(xiàn)橡.這個(gè)示例用同樣的數(shù)據(jù)創(chuàng)建了3個(gè)字典,唯一的區(qū)別就是數(shù)據(jù)出現(xiàn)的順序不一樣.可以看到,雖然鍵的次序是亂的,這3個(gè)字典仍然被視作相等的.

STUDENTS = [
 (89, '孫悟空'),
 (79, '豬八戒'),
 (69, '沙和尚'),
 (59, '小白龍'),
 (49, '唐僧')
]
d1 = dict(STUDENTS)
print('d1:', d1.keys())
d2 = dict(sorted(STUDENTS))
print('d2:', d2.keys())
d3 = dict(sorted(STUDENTS, key=lambda x: x[1]))
print('d3', d3.keys())
assert d1 == d2 and d2 == d3

5.往字典里添加新鍵可能會(huì)改變已有鍵的順序

無論何時(shí)往字典里添加新的鍵,Python解釋器都可能做出為字典擴(kuò)容的決定.擴(kuò)容導(dǎo)致的結(jié)果就是要新建一個(gè)更大的散列表,并把字典里已有的元素添加到新表里.

這個(gè)過程可能會(huì)發(fā)生新的散列沖突,導(dǎo)致新散列表中鍵的次序變化.

要注意的是,上面提到的這些變化是否會(huì)發(fā)生以及如何發(fā)生,都依賴于字典背后的實(shí)現(xiàn),因此你不能很自信的說自己知道背后發(fā)生了什么.

如果你在迭代一個(gè)字典的所有鍵的過程中同時(shí)對字典進(jìn)行修改,那么這個(gè)循環(huán)很可能會(huì)跳過一些鍵----甚至是跳過那些字典中已經(jīng)有的鍵.

由此可知,不要對字典同時(shí)進(jìn)行迭代和修改.如果想掃描并修改一個(gè)字典,最好分成兩步來進(jìn)行:

首先對字典迭代,以得出需要添加的內(nèi)容,把這些內(nèi)容放在一個(gè)新字典里;迭代結(jié)束之后再對原字典進(jìn)行更新.

在Python3中,.keys() .items() .values()方法返回的都是字典視圖.也就是說,這些方法返回的值更像集合.

set的實(shí)現(xiàn)及其導(dǎo)致的結(jié)果

set和frozenset的實(shí)現(xiàn)也依賴散列表,但在它們的散列表里存放的只有元素的引用.在set加入到Python之前,我們都是把字典加上無意義的值當(dāng)作集合來用.

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

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

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

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

5.往集合里添加元素,可能會(huì)改變集合里已有元素的次序.

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注本站的更多內(nèi)容！

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。