|
在前面幾篇文章中，我們一起了解了 Python 字典的概念、用法和實(shí)現(xiàn)原理。 今天，我們?cè)囍?Python 代碼來(lái)實(shí)現(xiàn)一個(gè)具有全功能的字典類(lèi)，從而加強(qiáng)理解。 【基本思路】 首先，我們要確認(rèn)字典應(yīng)具備的基本功能：
然后，考慮具體實(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ī)訪(fǎng)問(wèn)。 然而，鍵沖突是不可避免的。有兩種基本的方法用來(lái)解決沖突：沖突鏈表和開(kāi)放尋址。開(kāi)放尋址需要設(shè)計(jì)巧妙的算法來(lái)計(jì)算下一個(gè)可用的位置，出于簡(jiǎn)單考慮，我們采用鏈表的方式來(lái)解決鍵沖突。 每條沖突鏈也使用 list 來(lái)表示，發(fā)生哈希沖突的鍵值對(duì)依次追加到同一 list 的尾部。 最后，如何表示鍵值對(duì)元素呢？ 在我們之前學(xué)過(guò)的數(shù)據(jù)類(lèi)型中，tuple 看起來(lái)是一個(gè)表示鍵值對(duì)的理想類(lèi)型。但遺憾的是，它不可修改。我們的字典需要支持修改 key 對(duì)應(yīng)的 value。那么，可用的數(shù)據(jù)類(lèi)型只有 list 了。 這樣，我們同樣使用 list 來(lái)表示每個(gè)鍵值對(duì)：[key, value]。 最終，我們的數(shù)據(jù)結(jié)構(gòu)包含三重 list：
對(duì)于哈希算法，我們直接使用 Python 內(nèi)置的 hash() 函數(shù)。 現(xiàn)在，哈希表結(jié)構(gòu)、哈希算法和沖突策略都明確了。 下邊，有請(qǐng)翠花上代碼！ 【實(shí)現(xiàn)代碼】 代碼如下，其中的關(guān)鍵地方加了注釋?zhuān)膊扛接袦y(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 : 2021WechatName: python學(xué)與思{Id: 2021, WechatId: realpython_cn, Web: realpython.cn}PyDict._slots 是實(shí)現(xiàn)哈希表的嵌套 list。 PyDict.__items() 通過(guò)生成器的方式返回字典中所有的元素，它為其他的幾個(gè)訪(fǎng)問(wèn)方法提供了基礎(chǔ)功能。 為了和 dict 使用方式保持一致，我們重載了很多魔法方法。
當(dāng)你需要實(shí)現(xiàn)一個(gè)自定義容器時(shí)，多數(shù)情況下，你也需要重載這些方法。 代碼的整體邏輯還是比較簡(jiǎn)單的，就不詳細(xì)解釋了。 如你想獲取源碼，可關(guān)注本號(hào)，向我索取。 【相關(guān)文章】 我埋頭寫(xiě)作，就像在努力爬坡 你在看和分享，無(wú)形中推了我一把 多希望你可以一直關(guān)注著我 那是我不懈前行的力量 |
|
|
來(lái)自： RealPython > 《python 技術(shù)》
