Yinjun Zhu's Blog
首页 归档 标签 分类
Yinjun Zhu's Blog

目录

深入浅出地理解 Python 中可散列类型的原理和实现（三）

 收录于 编程语言
 Created on   约 2571 字   预计阅读 6 分钟 

前言

在 Python内置的序列类型 一文中，本人简略地介绍了对象的不可变性（immutable）和可散列性（hashable），以及它们之间的关系，但没有详细展开介绍它们背后的原理。其实，散列（hash）在编程语言中是个比较重要的概念，它的原理适用于所有语言而不仅仅是 Python。本系列将以 Python 语言作为案例，用三篇文章来深入浅出地介绍 Python 中可散列类型的相关知识。

本文是第三篇，将介绍设计可散列类型的其它注意事项，以及介绍了一些替代方法，来更方便地实现可散列类型。

第一篇，在 这里；

第二篇，在 这里。

注意

本文中的命令行示范，都是基于以下环境：

  • 操作系统： CentOS 7
  • Python：3.7.9

 

设计可散列类型的其它注意事项

不能基于对象的可变属性计算散列值

如果一个对象的属性在该对象的生命周期内是可能发生变化的，那么就不能基于这个可变属性来计算对象的散列值。

如果你想设计一个可散列类型，那么这个类型的属性全部采用不可变类型（immutable type）是最安全的。

但通常，这往往又是过于理想化的。一般来说，一个类的属性，或多或少有一些是需要在它的生命周期内被修改的。所以我们必须确定哪些属性是不会改变的，并基于它们来计算散列值。

散列值可能比相等性检查更挑剔

上一篇文章本人介绍过字典的工作原理，由于字典在查询键的时候，散列值的检查在对象相等性检查之前进行。这意味着散列值的检查是更重要的，散列值不相等的两个对象，一定是不相等的。

另一方面，这也意味散列值不一定要独一无二的，我们可以让散列值相等，从而让字典的查询完全基于对象相等性。

换句话说，就是你可以实现一个类，让散列函数返回的是一个常量，即该类所有对象的散列值相同，这样字典在查询键的时候，最终就会基于对象的相等性来判断键是否存在于字典。这样做的好处是把查询工作简化为基于对象相等性，坏处是是字典的工作模式本质上变成一个列表，字典的查询效率和列表的查询效率相同，而不再是高效的 O(1) 查询。

 

实现可散列类型的替代方法

通过覆盖__hash__方法和__eq__方法可以来实现可散列类型，但正如本系列文章中介绍的，还需遵守一些其它设计原则和需要注意的事项，所以实现一个健壮的、没有潜在 bugs 的可散列类型并不是一件简单的事。

那么，有没有其它替代方法可以让我们更聚焦于类的功能设计，而不是过多关注设计原则和注意事项这些细枝末节呢？

答案是，有的。如果我们真的想实现可散列类型，我们可以通过实现它们的不可变性来完成。

有一些内置的工具我们可以使用，比如 tuple 和 frozenset，可以使用它们把列表或集合转成可散列类型，还有 Python 3.7 引入的dataclass，我们可以用它修饰自定义的类，使它可散列。也有一些第三方的库可以使用，比如 immutables ，我们可以用immutables把字典转成可散列的Map对象（immutables可能会被纳入 python 3.9 因为它已经被 asyncio contextvar 使用）。

列表和集合

如果有一个列表，我们想让它可散列，我们可以把它转换成 tuple 来保证它不可改变：

1
2
3
4
5
6
7

x = [1, 2, 3]
try:
    hash(x)
except TypeError as e:
    print(f'Exception when trying to hash a list! {e}')
x_tuple = tuple(x)
print(f'hash(tuple(x)): {hash(x_tuple}')

执行结果：

1
2

Exception when trying to hash a list! unhashable type: 'list'
hash(tuple(x)): 2528502973977326415

如果有一个集合，我们想让它可散列，我们可以把它转换成 frozenset，来保证它不可改变，并同时维持 O(1) 复杂度的查询：

1
2
3
4
5
6
7

x = {1, 2, 3}
try:
    hash(x)
except TypeError as e:
    print(f'Exception when trying to hash a set! {e}')
x_frozenset = frozenset(x)
print(f'hash(frozenset(x)): {hash(x_frozenset)}')

执行结果：

1
2

Exception when trying to hash a set! unhashable type: 'set'
hash(frozenset(x)): -272375401224217160

字典

要让字典对象变得可散列，从而实现字典嵌套，我们可以使用immutable.Map类。immutables.Map是一个不可改变的 Map，因此是可散列的。任何对它的改变，会创建一个新的 map，而原 map 保持不变。它的性能比deepcopy 高很多。

Python 3.7 还没有把immutables加入标准库，所以先要安装一下：

1

pip install immutables

成功安装到 Python 3.7 的site-packages后，就可以在代码中直接使用：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from immutables import Map
d = {'a': 1, 'b': 2}
try:
    hash(d)
except TypeError as e:
    print(f'Exception when trying to hash a dict! {e}')
    
m = Map(d)
print(f'm is {m}')
print(f"Is 'a' in m? {'a' in m}")
print(f'hash(m): {hash(m)}')
try:
    m['a'] = 42
except TypeError as e:
    print(f'Fail to change Map object: {e}')
    
# Assignment creates a _new_ map!
m_prime = m.set('a', 42)
print(f'm after assignment: {m}')
print(f'm_prime after assignment: {m_prime}')

# m can be the key of dict because it is immutable
d2 = {m: 'test'}
print(f'The dictionary key can be another immutable dictionary: {d2}')

执行结果：

1
2
3
4
5
6
7
8

Exception when trying to hash a dict! unhashable type: 'dict'
m is immutables.Map({'b': 2, 'a': 1})
Is 'a' in m? True
hash(m): -8572025453086703039
Fail to change Map object: 'immutables._map.Map' object does not support item assignment
m after assignment: immutables.Map({'b': 2, 'a': 1})
m_prime after assignment: immutables.Map({'b': 2, 'a': 42})
The dictionary key can be another immutable dictionary: {immutables.Map({'b': 2, 'a': 1}): 'test'}

可以看到，如果要对字典 d 直接计算散列值，会抛出异常，因为字典是不可散列的。但我们可以用 d 构造一个 Map 对象 m。这个 Map 对象除了修改操作外，支持字典其它所有操作，比如查询操作 “‘a’ in m”。如果要修改 m 的内容，会抛出 TypeError。如果调用 set 方法，它会返回一个新的 Map 对象，而原对象保持不变。由于 m 对象现在是不可变的，也是可散列的，所以我们可以把它作为 key 加入到另一个字典中，实现字典嵌套。

自定义类

Python 3.7 引入了dataclass模块，该模块抽取了第三方库的attrs库的一部分功能，相当于 mini 版 attrs 库。我们可以用dataclass修饰自定义的类，把参数 frozen 设为 True，它会冻结该类的对象，使它们无法改变，从而让自定义的类变成可散列的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from dataclasses import dataclass

@dataclass(frozen=True)
class HashableType(object):
  name: str
  age: int

d = dict()
test1 = HashableType('jack', 20)
try:
  test1.name = 'tom'
except Exception as e:
  print(f'Catch an error trying to change HashableType object! {e}')

print(f'test1 has hash value {hash(test1)}')
test2 = HashableType('jack', 20)
print(f'Is test1 equal to test2: {test1 == test2}')
test3 = HashableType('tom', 20)
print(f'Is test1 equal to test3: {test1 == test3}')
d[test1] = 1
print(d)
print(test1 in d)
print(test2 in d)

执行结果：

1
2
3
4
5
6
7

Catch an error trying to change HashableType object! cannot assign to field 'name'
test1 has hash value -3497626926969420008
Is test1 equal to test2: True
Is test1 equal to test3: False
{HashableType(name='jack', age=20): 1}
True
True

用dataclass实现可散列类型非常简单，只要在类的定义前加上 “@dataclass(frozen=True)” 即可，类的属性必须用类型注解的方式来定义，因为如果在__init__方法中初始化属性，就打破了类的属性的不可变性。__hash__方法和__eq__方法无需定义，dataclass会自动定义好，默认情况下，类的所有属性都是不可变的，并且散列值基于所有属性计算出来。如果尝试修改该类对象，会抛出异常。相等性比较的是所有属性，两个对象的所有属性相等，比较结果就相等。

可以看到，用dataclass来实现可散列类型，代码要简单许多，而且属性自动设为只读，保证了散列的安全性。所以要自定义可散列类型，首推这种方式，而不是原始的通过覆盖__hash__方法和__eq__方法来实现。

 

参考

https://docs.python.org/3.7/reference/datamodel.html#object.__hash__

https://docs.python.org/3/glossary.html

https://hynek.me/articles/hashes-and-equality/

- 全文完 -

相关文章

「 您的赞赏是激励我创作和分享的最大动力! 」

 Python
返回 | 主页