在前面幾篇文章中，我們一起了解了 Python 字典的概念、用法和實(shí)現(xiàn)原理。
今天，我們?cè)囍?Python 代碼來(lái)實(shí)現(xiàn)一個(gè)具有全功能的字典類，從而加強(qiáng)理解。
【基本思路】
首先，我們要確認(rèn)字典應(yīng)具備的基本功能：
存儲(chǔ) key 唯一的鍵值對(duì)
可通過(guò) key 來(lái)訪問(wèn)鍵值對(duì)，且時(shí)間效率較高
可迭代
支持 keys()、value() 和 item() 等 dict 支持的基本方法
可獲取元素個(gè)數(shù)，可以字符串方式輸出所有元素
然后，考慮具體實(shí)現(xiàn)方式。
我們已經(jīng)知道，dict 是基于哈希表實(shí)現(xiàn)的。一個(gè)不存在鍵沖突的哈希表其實(shí)就是一個(gè)數(shù)組，只要根據(jù) hash(key) % size，將鍵值對(duì)保存起來(lái)就行了。
因此，我們可以使用 list 作為基本的存儲(chǔ)結(jié)構(gòu)。list 底層就是變長(zhǎng)數(shù)組，支持通過(guò)索引隨機(jī)訪問(wèn)。
然而，鍵沖突是不可避免的。有兩種基本的方法用來(lái)解決沖突：沖突鏈表和開放尋址。開放尋址需要設(shè)計(jì)巧妙的算法來(lái)計(jì)算下一個(gè)可用的位置，出于簡(jiǎn)單考慮，我們采用鏈表的方式來(lái)解決鍵沖突。
每條沖突鏈也使用 list 來(lái)表示，發(fā)生哈希沖突的鍵值對(duì)依次追加到同一 list 的尾部。
最后，如何表示鍵值對(duì)元素呢？
在我們之前學(xué)過(guò)的數(shù)據(jù)類型中，tuple 看起來(lái)是一個(gè)表示鍵值對(duì)的理想類型。但遺憾的是，它不可修改。我們的字典需要支持修改 key 對(duì)應(yīng)的 value。那么，可用的數(shù)據(jù)類型只有 list 了。
這樣，我們同樣使用 list 來(lái)表示每個(gè)鍵值對(duì)：[key, value]。
最終，我們的數(shù)據(jù)結(jié)構(gòu)包含三重 list：
哈希表槽位 Slots
沖突鍵值對(duì)鏈表
單個(gè)鍵值對(duì)
對(duì)于哈希算法，我們直接使用 Python 內(nèi)置的 hash() 函數(shù)。
現(xiàn)在，哈希表結(jié)構(gòu)、哈希算法和沖突策略都明確了。
下邊，有請(qǐng)翠花上代碼！
【實(shí)現(xiàn)代碼】
代碼如下，其中的關(guān)鍵地方加了注釋，尾部附有測(cè)試代碼。
class PyDict: def __init__(self, init_size=64): self._size = init_size self._length = 0
#哈希表。其中每個(gè)元素都是一個(gè) list 對(duì)象，存儲(chǔ)具有相同哈希值的元素 self._slots = [[] for i in range(self._size)]
#實(shí)現(xiàn) __setitem__ 魔法方法，以支持 dict[key]=value 操作 def __setitem__(self, key, value): slot = hash(key) % self._size for kv in self._slots[slot]: #更新已存在的 [key, value] if kv[0] == key: kv[1] = value break else: #元素以 [key, value] 的形式追加到哈希表 slot 對(duì)應(yīng)的 list 中，這樣可修改其 value self._slots[slot].append([key, value]) self._length += 1
#實(shí)現(xiàn) __getitem__ 魔法方法，以支持 value=dict[key] 操作 def __getitem__(self, key): slot = hash(key) % self._size for kv in self._slots[slot]: if kv[0] == key: return kv[1]
raise KeyError(f'Key {key} not exist')
#實(shí)現(xiàn) __delitem__ 魔法方法，以支持 del dict[key] 操作 def __delitem__(self, key): slot = hash(key) % self._size for kv in self._slots[slot]: if kv[0] == key: self._slots[slot].remove(kv) self._length -= 1 return
raise KeyError(f'Key {key} not exist')
#實(shí)現(xiàn) __len__ 魔法方法，以支持 len(dict) 操作 def __len__(self): return self._length
#以生成器的方式返回所有的元素，供內(nèi)部調(diào)用 def __items(self): for kv_list in self._slots: if kv_list: for kv in kv_list: yield kv
#實(shí)現(xiàn) __iter__ 魔法方法，以支持迭代操作 def __iter__(self): return (item[0] for item in self.__items())
#實(shí)現(xiàn) __contains__ 魔法方法，以支持 key in / not in dict 操作 def __contains__(self, key): slot = hash(key) % self._size for kv in self._slots[slot]: if kv[0] == key: return True
return False
#實(shí)現(xiàn) __repr__ 魔法方法，以字符串方式輸出字典中的所有元素 def __repr__(self): kv_str_list = []
kvs = self.__items() for kv in kvs: kv_str_list.append(': '.join([str(kv[0]), str(kv[1])]))
return f"{{{', '.join(kv_str_list)}}}"
#dict.get(key) def get(self, key): try: return self.__getitem__(key) except KeyError: return None
#dict.keys() def keys(self): return self.__iter__()
#dict.values() def values(self): return (item[1] for item in self.__items())
#dict.items() def items(self): return self.__items()
#Testpd = PyDict()
pd['Id'] = 2021pd['Web'] = 'realpython.cn'pd['WechatId'] = 'realpython_cn'pd['WechatName'] = 'python學(xué)與思'
print(pd)print('\r\n')
print(pd['WechatName'])print('\r\n')
print('===Keys in pydict===')for k in pd.keys(): print(k)print('\r\n')
print('===Values in pydict===')for v in pd.values(): print(v)print('\r\n')
print('===Items in pydict===')for kv in pd.items(): print(f'{kv[0]} : {kv[1]}')print('\r\n')
if 'WechatName' in pd: print(f'WechatName: {pd.get("WechatName")}') del pd['WechatName'] print(pd)運(yùn)行結(jié)果：
{Web: realpython.cn, WechatId: realpython_cn, WechatName: python學(xué)與思, Id: 2021}
python學(xué)與思
===Keys in pydict===WebWechatIdWechatNameId
===Values in pydict===realpython.cnrealpython_cnpython學(xué)與思2021
===Items in pydict===Web : realpython.cnWechatId : realpython_cnWechatName : python學(xué)與思Id : 2021
WechatName: python學(xué)與思{Id: 2021, WechatId: realpython_cn, Web: realpython.cn}PyDict._slots 是實(shí)現(xiàn)哈希表的嵌套 list。
PyDict.__items() 通過(guò)生成器的方式返回字典中所有的元素，它為其他的幾個(gè)訪問(wèn)方法提供了基礎(chǔ)功能。
為了和 dict 使用方式保持一致，我們重載了很多魔法方法。
__setitem__
__getitem__
__delitem__
__len__
__contains__
__repr__
當(dāng)你需要實(shí)現(xiàn)一個(gè)自定義容器時(shí)，多數(shù)情況下，你也需要重載這些方法。
代碼的整體邏輯還是比較簡(jiǎn)單的，就不詳細(xì)解釋了。
如你想獲取源碼，可關(guān)注本號(hào)，向我索取。
【相關(guān)文章】
我埋頭寫作，就像在努力爬坡
你在看和分享，無(wú)形中推了我一把
多希望你可以一直關(guān)注著我
那是我不懈前行的力量
聯(lián)系客服
