Python字典及特性

字典是一種可變、無序容器數(shù)據(jù)結(jié)構(gòu)。元素以鍵值對存在，鍵值唯一。它的特點(diǎn)搜索速度很快：數(shù)據(jù)量增加10000倍，搜索時間增加不到2倍；當(dāng)數(shù)據(jù)量很大的時候，字典的搜索速度要比列表快成百上千倍。

Python字典的實(shí)現(xiàn)原理

在Python中，字典是通過散列表（哈希表）實(shí)現(xiàn)的。字典也叫哈希數(shù)組或關(guān)聯(lián)數(shù)組，所以其本質(zhì)是數(shù)組（如下圖），每個 bucket 有兩部分：一個是鍵對象的引用，一個是值對象的引用。所有 bucket 結(jié)構(gòu)和大小一致，我們可以通過偏移量來讀取指定 bucket。

哈希數(shù)組

存儲

定義一個字典 dic = {}，假設(shè)其哈希數(shù)組長度為8。

>>> dic = {}
>>> dic
{}

實(shí)現(xiàn)dic的哈希數(shù)組

Python會根據(jù)哈希數(shù)組的擁擠程度對其擴(kuò)容?！皵U(kuò)容”指的是:創(chuàng)造更大的數(shù)組，這時候會對已經(jīng)存在的鍵值對重新進(jìn)行哈希取余運(yùn)算保存到其它位置；一般接近 2/3 時，數(shù)組就會擴(kuò)容。擴(kuò)容后，偏移量的數(shù)字個數(shù)增加，如數(shù)組長度擴(kuò)容到16時，可以用最右邊4位數(shù)字作為偏移量。

>>>dic['name'] = '張三'
>>>bin(hash('name'))
'0b101011100000110111101000101010100010011010110010100101001000110' 

讀取

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

計算鍵對象name的哈希值，然后比較哈希數(shù)組對應(yīng)索引內(nèi)的bucket是否為空，為空返回None，否則計算這個bucket的鍵對象的哈希值，然后與name哈希值比較，相等則返回值對象，否則繼續(xù)左移計算哈希值。

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

Python中所有不可變的內(nèi)置類型都是可哈希的。
可變類型（如列表，字典和集合）就是不可哈希的，因此不能作為字典的鍵。

2.字典的內(nèi)存開銷很大，以空間換時間。
3.鍵查詢速度很快，列表查詢是按順序一個個遍歷，字典則是一步到位。
4.往字典里面添加新鍵可能導(dǎo)致擴(kuò)容，導(dǎo)致哈希數(shù)組中鍵的次序變化。因此，不要在遍歷字典的同時進(jìn)行字典的修改。