使用纯 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()

#Test
pd = PyDict()
pd['Id'] = 2021
pd['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===
Web
WechatId
WechatName
Id

===Values in pydict===
realpython.cn
realpython_cn
python学与思
2021

===Items in pydict===
Web : realpython.cn
WechatId : realpython_cn
WechatName : 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__

当你需要实现一个自定义容器时,多数情况下,你也需要重载这些方法。

代码的整体逻辑还是比较简单的,就不详细解释了。

如你想获取源码,可关注本号,向我索取。


流畅的python

【相关文章】

  1. 快速查找,插入有序,从源码分析 Python 底层如何实现字典的这些特性
  2. 再次解释一下 Python 字典使用的哈希表
  3. RealPython 基础教程:Python 字典用法详解

 


欢迎转载,请注明出处。谢绝搬运,抄袭必究!

欢迎关注本站公众号【python学与思】

分享优质原创 Python 教程和技术文章,
整理 Python 常用库和开源框架的使用文档,
汇集 Python 常见疑难问题解决方法。
python学与思:学 Python,不浅尝辄止。

python 学与思