Python字典的核心底層原理講解

字典對(duì)象的核心是散列表。散列表是一個(gè)稀疏數(shù)組（總是有空白元素的數(shù)組），數(shù)組的每個(gè)單元叫做 bucket。每個(gè) bucket 有兩部分：一個(gè)是鍵對(duì)象的引用，一個(gè)是值對(duì)象的引用。所有 bucket 結(jié)構(gòu)和大小一致，我們可以通過偏移量來讀取指定 bucket。下面通過存儲(chǔ)與獲取數(shù)據(jù)的過程介紹字典的底層原理。

存儲(chǔ)數(shù)據(jù)的過程

例如，我們將‘name' = ‘張三' 這個(gè)鍵值對(duì)存儲(chǔ)到字典map中，假設(shè)數(shù)組長(zhǎng)度為8，可以用3位二進(jìn)制表示。

>>> map = {}
>>> map
{}
>>> map['name'] = '張三'

1、計(jì)算name的散列值。

>>> bin(hash('name'))
'0b101011100000110111101000101010100010011010110010100101001000110'

2、用散列值的最右邊 3 位數(shù)字作為偏移量，即“110”，十進(jìn)制是數(shù)字 6。我們查看偏移量 6，對(duì)應(yīng)的 bucket 是否為空。如果為空，則將鍵值對(duì)放進(jìn)去。如果不為空，則依次取右移 3 位作為偏移量，即“000”，十進(jìn)制是數(shù)字0，循環(huán)此過程，直到找到為空的 bucket 將鍵值對(duì)放進(jìn)去。python 會(huì)根據(jù)散列表的擁擠程度擴(kuò)容?！皵U(kuò)容”指的是:創(chuàng)造更大的數(shù)組，將原有內(nèi)容拷貝到新數(shù)組中。接近 2/3 時(shí)，數(shù)組就會(huì)擴(kuò)容。擴(kuò)容后，偏移量的數(shù)字個(gè)數(shù)增加，如數(shù)組長(zhǎng)度擴(kuò)容到16時(shí)，可以用最右邊4位數(shù)字作為偏移量。

獲取數(shù)據(jù)的過程

>>> map.get('name')
'張三'

1、計(jì)算name的散列值

2、用最右邊 3 位數(shù)字作為偏移量，即“110”，十進(jìn)制是數(shù)字6。查看偏移量 6，對(duì)應(yīng)的 bucket 是否為空。如果為空，則返回 None。如果不為空，則將這個(gè) bucket 的鍵對(duì)象計(jì)算對(duì)應(yīng)散列值，和我們的散列值進(jìn)行比較，如果相等，則將對(duì)應(yīng)“值對(duì)象”返回；如果不相等，則再依次取其他幾位數(shù)字，重新計(jì)算偏移量。循環(huán)此過程。

小結(jié)：

1.鍵必須可散列，如數(shù)字、元組、字符串；自定義對(duì)象需要滿足支持hash、支持通過__eq__()方法檢測(cè)相等性、若 a==b 為真，則 hash(a)==hash(b)也為真。

>>> b = [1,2] //List不可散列
>>> bin(hash(b))
Traceback (most recent call last):
 File "<pyshell#90>", line 1, in <module>
  bin(hash(b))
TypeError: unhashable type: 'list'

2. 字典在內(nèi)存中開銷巨大，典型的空間換時(shí)間；

3. 鍵查詢速度很快；

4. 往字典里面添加新建可能導(dǎo)致擴(kuò)容，導(dǎo)致散列表中鍵的次序變化。因此，不要在遍歷字典的同時(shí)進(jìn)行字典的修改。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)億速云的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接