dict 哈希表高级知识精讲

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

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

哈希值

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

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

哈希值在对象整个生命周期内不能改变；
可比较，且比较相等的对象哈希值必须相同；

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

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

1
2
3
4


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

不可哈希对象不能作为 dict 对象的键，显然 list 、 dict 等均不是合法的键对象：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


>>> {
...     []: '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'

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


>>> 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 是也：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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 字段实现 哈希函数 以及 相等性 判断：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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 字段便是用于保存哈希值的。

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

哈希冲突

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

那么我们有什么办法可以解决哈希冲突呢？点击 阅读原文 ，获取更多细节！

【Python源码剖析】系列文章首发于公众号【小菜学编程】，敬请关注：