使用纯 Python 代码来模拟实现 Python 字典
在前面几篇文章中，我们一起了解了 Python 字典的概念、用法和实现原理。
今天，我们试着用 Python 代码来实现一个具有全功能的字典类，从而加强理解。
【基本思路】
首先，我们要确认字典应具备的基本功能：
存储 key 唯一的键值对
可通过 key 来访问键值对，且时间效率较高
可迭代
支持 keys()、value() 和 item() 等 dict 支持的基本方法
可获取元素个数，可以字符串方式输出所有元素
然后，考虑具体实现方式。
我们已经知道，dict 是基于哈希表实现的。一个不存在键冲突的哈希表其实就是一个数组，只要根据 hash(key) % size，将键值对保存起来就行了。
因此，我们可以使用 list 作为基本的存储结构。list 底层就是变长数组，支持通过索引随机访问。
然而，键冲突是不可避免的。有两种基本的方法用来解决冲突：冲突链表和开放寻址。开放寻址需要设计巧妙的算法来计算下一个可用的位置，出于简单考虑，我们采用链表的方式来解决键冲突。
每条冲突链也使用 list 来表示，发生哈希冲突的键值对依次追加到同一 list 的尾部。
最后，如何表示键值对元素呢？
在我们之前学过的数据类型中，tuple 看起来是一个表示键值对的理想类型。但遗憾的是，它不可修改。我们的字典需要支持修改 key 对应的 value。那么，可用的数据类型只有 list 了。
这样，我们同样使用 list 来表示每个键值对：[key, value]。
最终，我们的数据结构包含三重 list：
哈希表槽位 Slots
冲突键值对链表
单个键值对
对于哈希算法，我们直接使用 Python 内置的 hash() 函数。
现在，哈希表结构、哈希算法和冲突策略都明确了。
下边，有请翠花上代码！
【实现代码】
代码如下，其中的关键地方加了注释，尾部附有测试代码。
class PyDict: def __init__(self, init_size=64): self._size = init_size self._length = 0
#哈希表。其中每个元素都是一个 list 对象，存储具有相同哈希值的元素 self._slots = [[] for i in range(self._size)]
#实现 __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 对应的 list 中，这样可修改其 value self._slots[slot].append([key, value]) self._length += 1
#实现 __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')
#实现 __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')
#实现 __len__ 魔法方法，以支持 len(dict) 操作 def __len__(self): return self._length
#以生成器的方式返回所有的元素，供内部调用 def __items(self): for kv_list in self._slots: if kv_list: for kv in kv_list: yield kv
#实现 __iter__ 魔法方法，以支持迭代操作 def __iter__(self): return (item[0] for item in self.__items())
#实现 __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
#实现 __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学与思'
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)运行结果：
{Web: realpython.cn, WechatId: realpython_cn, WechatName: python学与思, Id: 2021}
python学与思
===Keys in pydict===WebWechatIdWechatNameId
===Values in pydict===realpython.cnrealpython_cnpython学与思2021
===Items in pydict===Web : realpython.cnWechatId : realpython_cnWechatName : python学与思Id : 2021
WechatName: python学与思{Id: 2021, WechatId: realpython_cn, Web: realpython.cn}PyDict._slots 是实现哈希表的嵌套 list。
PyDict.__items() 通过生成器的方式返回字典中所有的元素，它为其他的几个访问方法提供了基础功能。
为了和 dict 使用方式保持一致，我们重载了很多魔法方法。
__setitem__
__getitem__
__delitem__
__len__
__contains__
__repr__
当你需要实现一个自定义容器时，多数情况下，你也需要重载这些方法。
代码的整体逻辑还是比较简单的，就不详细解释了。
如你想获取源码，可关注本号，向我索取。
【相关文章】
我埋头写作，就像在努力爬坡
你在看和分享，无形中推了我一把
多希望你可以一直关注着我
那是我不懈前行的力量