|
在前面幾篇文章中，我們一起了解了 Python 字典的概念、用法和實(shí)現(xiàn)原理。 今天，我們試著用 Python 代碼來實(shí)現(xiàn)一個(gè)具有全功能的字典類，從而加強(qiáng)理解。 【基本思路】 首先，我們要確認(rèn)字典應(yīng)具備的基本功能：
然后，考慮具體實(shí)現(xiàn)方式。 我們已經(jīng)知道，dict 是基于哈希表實(shí)現(xiàn)的。一個(gè)不存在鍵沖突的哈希表其實(shí)就是一個(gè)數(shù)組，只要根據(jù) hash(key) % size，將鍵值對保存起來就行了。 因此，我們可以使用 list 作為基本的存儲結(jié)構(gòu)。list 底層就是變長數(shù)組，支持通過索引隨機(jī)訪問。 然而，鍵沖突是不可避免的。有兩種基本的方法用來解決沖突：沖突鏈表和開放尋址。開放尋址需要設(shè)計(jì)巧妙的算法來計(jì)算下一個(gè)可用的位置，出于簡單考慮，我們采用鏈表的方式來解決鍵沖突。 每條沖突鏈也使用 list 來表示，發(fā)生哈希沖突的鍵值對依次追加到同一 list 的尾部。 最后，如何表示鍵值對元素呢？ 在我們之前學(xué)過的數(shù)據(jù)類型中，tuple 看起來是一個(gè)表示鍵值對的理想類型。但遺憾的是，它不可修改。我們的字典需要支持修改 key 對應(yīng)的 value。那么，可用的數(shù)據(jù)類型只有 list 了。 這樣，我們同樣使用 list 來表示每個(gè)鍵值對：[key, value]。 最終，我們的數(shù)據(jù)結(jié)構(gòu)包含三重 list：
對于哈希算法，我們直接使用 Python 內(nèi)置的 hash() 函數(shù)。 現(xiàn)在，哈希表結(jié)構(gòu)、哈希算法和沖突策略都明確了。 下邊，有請翠花上代碼！ 【實(shí)現(xiàn)代碼】 代碼如下，其中的關(guān)鍵地方加了注釋，尾部附有測試代碼。 class PyDict: def __init__(self, init_size=64): self._size = init_size self._length = 0 #哈希表。其中每個(gè)元素都是一個(gè) list 對象，存儲具有相同哈希值的元素 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 對應(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() 通過生成器的方式返回字典中所有的元素，它為其他的幾個(gè)訪問方法提供了基礎(chǔ)功能。 為了和 dict 使用方式保持一致，我們重載了很多魔法方法。
當(dāng)你需要實(shí)現(xiàn)一個(gè)自定義容器時(shí)，多數(shù)情況下，你也需要重載這些方法。 代碼的整體邏輯還是比較簡單的，就不詳細(xì)解釋了。 如你想獲取源碼，可關(guān)注本號，向我索取。 【相關(guān)文章】 我埋頭寫作，就像在努力爬坡 你在看和分享，無形中推了我一把 多希望你可以一直關(guān)注著我 那是我不懈前行的力量 |
|
|
