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

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

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

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

1、計算name的散列值。

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

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

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

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

1、計算name的散列值

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

小結(jié)：

1.鍵必須可散列，如數(shù)字、元組、字符串；自定義對象需要滿足支持hash、支持通過__eq__()方法檢測相等性、若 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)存中開銷巨大，典型的空間換時間；

3. 鍵查詢速度很快；

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

總結(jié)

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

最新評論