Python內部很地方都使用著dict這種結構，在對象屬性__dict__就是一個字典，所以對其效率要求很高。

dict采用了哈希表，最低能在 O(1)時間內完成搜索。同樣的java的HashMap也是采用了哈希表實現，不同是dict在發生哈希沖突的時候采用了開放尋址法，而HashMap采用了鏈接法。

開放尋址法

優點

記錄更容易進行序列化（serialize）操作

如果記錄總數可以預知，可以創建完美哈希函數，此時處理數據的效率是非常高的

缺點

存儲記錄的數目不能超過桶數組的長度，如果超過就需要擴容，而擴容會導致某次操作的時間成本飆升，這在實時或者交互式應用中可能會是一個嚴重的缺陷

使用探測序列，有可能其計算的時間成本過高，導致哈希表的處理性能降低

由于記錄是存放在桶數組中的，而桶數組必然存在空槽，所以當記錄本身尺寸（size）很大并且記錄總數規模很大時，空槽占用的空間會導致明顯的內存浪費

刪除記錄時，比較麻煩。比如需要刪除記錄a，記錄b是在a之后插入桶數組的，但是和記錄a有沖突，是通過探測序列再次跳轉找到的地址，所以如果直接刪除a，a的位置變為空槽，而空槽是查詢記錄失敗的終止條件，這樣會導致記錄b在a的位置重新插入數據前不可見，所以不能直接刪除a，而是設置刪除標記。這就需要額外的空間和操作。

想要自己實現一個dict可以繼承 collection 的 UserDict，里面已經封裝了常用的方法。
下面是我根據自己的理解去用python實現的字典，簡化了很的功能，比如對象緩沖池、String哈希的優化等等，如果有錯誤的或者更好的實現方式請指出。因為python沒有純粹的數組結構，所以數組也是借用list實現的. #python3.6 from collections import namedtupleclass SimpleArray(object):#簡單的數組類實現def __init__(self, mix):self.container = [None for i in range(mix)]def __len__(self):return len(self.container)def __setitem__(self, key, value):return self.container.__setitem__(key,value)def __getitem__(self, item):return self.container.__getitem__(item)def __delitem__(self, key):return self.container.__setitem__(key, None)def __str__(self):return str(self.container)class SimpleDict(object):#簡單的字典類實現Init_length = 8 # 初始化的大小Load_factor = 2/3 # 擴容因子def __init__(self):self._array_len = SimpleDict.Init_lengthself._array = SimpleArray(self._array_len)self._used = 0self.dictObj = namedtuple("dictObj","key value") # 這里其實可以用數組也可以的，namedtuple是為了讓代碼更可讀def __getitem__(self, item):key = self._hash(item)dictObj = self._array[key]if dictObj is not None and dictObj.key == item:return dictObj.valueelse:for new_key in self._second_hash(key):if self._array[new_key] is not None and item == self._array[new_key].key:return self._array[new_key].valuedef __setitem__(self, key, value):# 計算是否需要擴容if (self._used / self._array_len) > SimpleDict.Load_factor:self._new_array()#根據鍵的hash值來計算得出位置索引hash_key = self._hash(key)new_key = self._second_hash(hash_key)while True:if self._array[hash_key] is None or key == self._array[hash_key].key:break# 發生哈希碰撞根據二次探查函數得出下一個索引的位置hash_key = next(new_key)if abs(hash_key) >= self._array_len:self._new_array()hash_key = self._hash(key)# 找到空位將鍵值對象放入self._array[hash_key] = self.dictObj(key, value)self._used += 1def __delitem__(self, key):hash_key = self._hash(key)if key != self._array[hash_key].key:for new_key in self._second_hash(hash_key):if key == self._array[new_key].key:hash_key = new_keyself._array[hash_key] = Noneself._used -= 1def _hash(self, key):# 計算哈希值return hash(key) & (self._array_len-1)def _second_hash(self, hash_key):# 簡單的二次探查函數實現count = 1for i in range(self._array_len):new_key = hash_key + count**2if abs(new_key) < self._array_len:yield new_keynew_key = hash_key - count**2if abs(new_key) < self._array_len:yield new_keycount += 1def _new_array(self):# 擴容old_array = self._arrayself._array_len = self._array_len * 2 # 擴容2倍大小self._array = SimpleArray(self._array_len)for i in range(len(old_array)):dictObj = old_array[i]if dictObj is not None:self[dictObj.key] = dictObj.valuedef __str__(self):result = ", ".join("%s:%s"%(obj.key, obj.value)for obj in self._arrayif obj is not None)return "{" + result + "}"if __name__ == '__main__':d = SimpleDict()for i in range(20):d[str(i)] = iprint(d)print(d["10"])del d["11"]print(d)

---

鏈接法

優點

對于記錄總數頻繁可變的情況，處理的比較好（也就是避免了動態調整的開銷）

由于記錄存儲在結點中，而結點是動態分配，不會造成內存的浪費，所以尤其適合那種記錄本身尺寸（size）很大的情況，因為此時指針的開銷可以忽略不計了

刪除記錄時，比較方便，直接通過指針操作即可

缺點

存儲的記錄是隨機分布在內存中的，這樣在查詢記錄時，相比結構緊湊的數據類型（比如數組），哈希表的跳轉訪問會帶來額外的時間開銷

如果所有的 key-value 對是可以提前預知，并之后不會發生變化時（即不允許插入和刪除），可以人為創建一個不會產生沖突的完美哈希函數（perfect hash function），此時封閉散列的性能將遠高于開放散列

由于使用指針，記錄不容易進行序列化（serialize）操作

其中有很重要的兩個參數影響其性能: 初始容量和加載因子

dict：默認初始容量為8，加載因子為2/3

HashMap： 默認初始容量為16， 加載因子為0.75

兩者相同的是擴容的長度必需是2的N次方

總結

以上是生活随笔為你收集整理的加载dict_Python的dict实现原理和Java的HashMap之间的区别的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。