【原】使用纯 Python 代码来模拟实现 Python 字典

RealPython 2021-03-30

展开全文

在前面几篇文章中，我们一起了解了 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)}}}"