dict哈希表高级知识精讲

上一小节,我们通过源码学习,研究了 dict 对象的内部结构,并找到隐藏其中的秘密 —— 哈希表 。 关联式容器 一般由 平衡搜索树 或 哈希表 来实现,dict 选用 哈希表 ,主要考虑 搜索效率 。 但哈希表 稀疏 的特性,意味着巨大的内存开销。 为优化内存使用,Python 别出心裁地将哈希表分成两部分来实现:哈希索引 以及 键值对存储 数组。

尽管如此,由于篇幅关系,很多细节我们还没来得及讨论。 本节,我们再接再厉,继续研究 哈希函数 、哈希冲突哈希攻击 以及 删除操作 等高级知识点,彻底掌握哈希表设计精髓。

哈希值

Python 内置函数 hash 返回对象 哈希值 ,哈希表 依赖 哈希值 索引元素:

../../_images/d46a8e1afac96f98db84a545046db177.svg

根据哈希表性质, 键对象 必须满足以下两个条件,否则哈希表便不能正常工作:

  • 哈希值在对象整个生命周期内不能改变;

  • 可比较,且比较相等的对象哈希值必须相同;

满足这两个条件的对象便是 可哈希 ( hashable )对象,只有可哈希对象才可作为哈希表的键。 因此,诸如 dictset 等底层由哈希表实现的容器对象,其键对象必须是可哈希对象。

Python 内建对象中的 不可变对象 ( immutable )都是可哈希对象;而诸如 list 、dict可变对象 则不是:

>>> hash([])
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    TypeError: unhashable type: 'list'

不可哈希对象不能作为 dict 对象的键,显然 listdict 等均不是合法的键对象:

>>> {
...     []: 'list is not hashable'
... }
    Traceback (most recent call last):
    File "<stdin>", line 2, in <module>
    TypeError: unhashable type: 'list'
>>>
>>> {
...     {}: 'dict is not hashable either'
... }
    Traceback (most recent call last):
    File "<stdin>", line 2, in <module>
    TypeError: unhashable type: 'dict'

而用户自定义的对象默认便是可哈希对象,对象哈希值由对象地址计算而来,且任意两个不同对象均不相等:

>>> class A:
...     pass
...
>>>
>>> a = A()
>>> b = A()
>>>
>>> hash(a), hash(b)
(-9223372036573452351, -9223372036573452365)
>>>
>>> a == b
False

那么,哈希值如何计算呢?答案是—— 哈希函数 。 在对象模型部分,我们知道对象行为由类型对象决定。 哈希值 计算作为对象行为中的一种,秘密也隐藏在类型对象中—— tp_hash 函数指针。 而内置函数 hash 则依赖类型对象中的 tp_hash 函数,完成哈希值计算并返回。

str 对象为例,其哈希函数位于 Objects/unicodeobject.c 源文件,unicode_hash 是也:

PyTypeObject PyUnicode_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "str",              /* tp_name */
    sizeof(PyUnicodeObject),        /* tp_size */
    // ...

    (hashfunc) unicode_hash,        /* tp_hash*/

    // ...
    unicode_new,            /* tp_new */
    PyObject_Del,           /* tp_free */
};

对于用户自定义的对象,可以实现 __hash__ 魔术方法,重写默认哈希值计算方法。 举个例子,假设标签类 Tag 的实例对象由 value 字段唯一标识,便可以根据 value 字段实现 哈希函数 以及 相等性 判断:

class Tag:

    def __init__(self, value, title):
        self.value = value
        self.title = title

    def __hash__(self):
        return hash(self.value)

    def __eq__(self, other):
        return self.value == other.value

哈希值 使用频率 较高,而且在对象生命周期内均不变。 因此,可以在对象内部对哈希值进行缓存,避免重复计算。 以 str 对象为例,内部结构中的 hash 字段便是用于保存哈希值的。

理想的哈希函数必须保证哈希值尽量均匀地分布于整个哈希空间,越是相近的值,其哈希值差别应该越大。

哈希冲突

一方面,不同的对象,哈希值有可能相同,另一方面,与哈希值空间相比,哈希表的槽位是非常有限的。 因此,存在多个键被映射到哈希索引的同一槽位的可能性,这便是 哈希冲突 !

../../_images/82eb378b5d46a6cf86cea3b4baa9b567.svg

那么有哪些方法可以避免哈希冲突呢?点击 更多章节,获取更多细节!

更多章节

洞悉 Python 虚拟机运行机制,探索高效程序设计之道!

到底如何才能提升我的 Python 开发水平,向更高一级的岗位迈进? 如果你有这些问题或者疑惑,请订阅我们的专栏,阅读更多章节:

https://cdn.fasionchan.com/python-source-course-qrcode.png

附录

订阅更新,获取更多学习资料,请关注我们的 微信公众号

微信搜索:小菜学编程

创作不易,如果觉得我们写得还行,就请我们喝杯咖啡吧😋

微信搜索:小菜学编程