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

存儲數據的過程

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

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

1、計算name的散列值。

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

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

獲取數據的過程

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

1、計算name的散列值

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

小結：

1.鍵必須可散列，如數字、元組、字符串；自定義對象需要滿足支持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. 字典在內存中開銷巨大，典型的空間換時間；

3. 鍵查詢速度很快；

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

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對武林站長站的支持。如果你想了解更多相關內容請查看下面相關鏈接