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

前言

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

本文是第二篇，介绍字典的工作原理，以及由此延伸出的设计可散列对象的几个原则。

第一篇，在 这里；

第三篇，在 这里。

字典的工作原理

我们先以字典为例，看看它的工作原理。Python 字典的实现基于散列表，在这基础上做了比较好的优化。要理解散列性对于字典为何非常重要，我们先从一个更高的层次看一下字典是如何工作的。

• 当我们执行语句 “d[key] = value" 要在字典中存放一个键和对应的值时，Python 会依次执行：

  1. 针对 key 调用__hash__函数，来计算它的散列值 hash_value，如果 key 对象不可散列，抛出 TypeError，结束；
  2. 把（hash_value，key，value）作为一个元素存在一个数组结构中，存放的偏移位置是 hash_value % len(array)；
  3. 如果数组需要重新调整大小，不会重新计算先前数组中存放的散列值，而是重用它们。

• 当我们执行语句 “value = d[key]” 从字典中获取一个键对应的值时，Python 会执行：

  1. 针对 key 调用__hash__函数来计算它的 hash_value，如果 key 对象不可散列，抛出 TypeError；

  2. 计算偏移位置 hash_value % len(array)，尝试从数组中得到偏移位置对应的元素，如果不存在，抛出 KeyError，如果存在，我们暂且称它为 （target hash_value, target key, target value），然后依次做以下检查：

     1）如果 target hash_value 和前面计算出来的 hash_value 不相同，抛出 KeyError，结束；

     2）如果 target key 对象的 identity 和源 key 对象的 identity 相等，不再做后续检查，直接返回 target value，结束；

     3）如果 target key 对象的 identity 和源 key 对象的 identity 不相等，则接着调用__eq__比较两对象是否相等，如果相等，返回 target value，否则，抛出 KeyError。

  可以看到，字典基于散列值的工作方式，非常高效。通过对象的散列值，得到它在数组中的偏移量，并直接以随机存取的方式获取它的键和对应的值，整个查询的复杂度为 O(1)。

• 当我们执行语句 “key in d" 来判断一个键是否存在于字典中时，Python 的执行方式和上面获取键值的方法类似，区别在于它返回的是 True/False，而不是返回 target value 或抛出异常。

来看一些例子：

示例1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class HashableType(object):
  def __init__(self, name):
    self.name = name

  def __eq__(self, other):
    print('in HashableType class\'s compare function')
    if isinstance(other, HashableType) and other.name == self.name:
      return True
    return False

  def __hash__(self):
    print('in HashableType class\'s hash function')
    return hash(self.name)


class UnhashableType(object):
  def __init__(self, name):
    self.name = name

  def __eq__(self, other):
    print('in UnhashableType class\'s compare function')
    if isinstance(other, HashableType) and other.name == self.name:
      return True
    return False


d = dict()
test1 = HashableType('jack')
d[test1] = 1
test2 = UnhashableType('tom')
try:
  d[test2] = 2
except TypeError as e:
  print(f"can not add test2 into dict: {e}")

for i in range(1000):
  d[i] = i

执行结果：

1
2

in HashableType class's hash function
can not add test2 into dict: unhashable type: 'UnhashableType'

定义了两个类，第一个类是可散列的，第二个类是不可散列的，本人在上一篇文章中介绍过，要定义一个不可散列的类型，只要实现__eq__方法而不实现__hash__方法即可。test1 是可散列对象，当执行 “d[test1] = 1” 时，成功调用 test1 的__hash__方法获得它的散列值，从而将 test1 对象存储在字典中。test2 是不可散列对象，执行 “d[test2] = 2” 时，抛出 TypeError。接下来，在 for 循环中，往字典中添加了 1000 个元素，在这过程中，字典会 resize，而已经存放在字典中的 test1 的散列值并不会被重新计算，而是直接被重用，所以__hash__函数没有再调用过。

示例2：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class NeverEqual:
  def __init__(self, name):
    self.name = name

  def __eq__(self, other):
    print('in NeverEqual class\'s compare function')
    return False

  def __hash__(self):
    print('in NeverEqual class\'s hash function')
    return hash(self.name)


never_equal = NeverEqual('jack')
print(f'Is never_equal equal to itself? {never_equal == never_equal}')
d = dict()
d[never_equal] = 1
print(f'Is never_equal in a dict including itself? {never_equal in d}')

执行结果：

1
2
3
4
5

in NeverEqual class's compare function
Is never_equal equal to itself? False
in NeverEqual class's hash function
in NeverEqual class's hash function
Is never_equal in a dict including itself? True

never_equal 是一个永远不会和同类对象相等的对象，甚至和它自己也不相等，因为__eq__方法直接返回 False。所以 “never_equal == never_equal” 的结果为 False。

接下来，执行 “d[never_equal] = 1” 的时候，计算散列值，调用了一次__hash__方法，执行 “never_equal in d” 的时候，又调用了一次__hash__方法。

最后，检查 “never_equal in d”，虽然 never_equal 不和自己相等，但 “never_equal in d” 却返回 True，这是因为前面介绍字典的工作原理的时候讲过，在获取/查询键值的时候：如果 target key 对象的 identity 和源 key 对象的 identity 相等，不再做后续检查。never_equal 和存放在字典中的 never_equal 是同一个对象，id 相同，所以不会再检查相等性，直接返回 True。这是一个重要的优化，因为实现__eq__函数的代价可能比较高昂。

示例3：

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

class HashableType(object):
  def __init__(self, name):
    self.name = name

  def __eq__(self, other):
    print('in HashableType class\'s compare function')
    if isinstance(other, HashableType) and other.name == self.name:
      return True
    return False

  def __hash__(self):
    print('in HashableType class\'s hash function')
    return hash(self.name)


d = dict()
test1 = HashableType('jack')
d[test1] = 1
print(test1 in d)
test1.name = 'tom'
print(test1 in d)

执行结果：

1
2
3
4
5

in HashableType class's hash function
in HashableType class's hash function
True
in HashableType class's hash function
False

把 test1 对象存入字典时，调用一次散列函数计算它的散列值，然后判断 test1 是否在字典中，又调用一次散列函数，test1 对象在字典中，所以打印 True。接下来，强制改变了 test1 对象的 name 属性，再判断 test1 是否在字典时，计算出的散列值已经发生了改变，得到的偏移位置处为空，所以返回 False。这个例子，告诉我们，为什么一个对象的散列值在它的生命期内永远不能改变是非常重要的。 如果散列值改变了，就会遇到字典或集合不再正常工作，以及一些很难发现的 bugs。

定义可散列类型的原则

上一篇文章中，我们知道了要定义一个可散列的类型，首先需要定义它的__hash__方法和__eq__方法。而本文的上一节中，我们又了解了定义这两个方法是基础，除此之外，我们在设计__hash__方法和__eq__方法时还需要遵守一些其它的重要原则。这一节我们详细介绍这些原则。

原则一：可散列对象，它的散列值在它的生命周期内永远不可改变。

示例3中，我们已经看到，为什么对象的散列值在它的生命周期内不能改变。虽然我们 test1 对象，始终在字典中，但 Python 却声称找不到它。原因在于，test1 对象改变之后，当要获取它或者查询它是否在字典中时，计算出来的散列值不同于之前存放时的散列值，从而计算的偏移位置也不同了，自然无法找到原来的对象。

这个原则，很好地解释了为什么不可变的数据结构比如元祖或者字符串是可散列的，而可变的数据结构如列表或字典是不可散列的。

接下来的例子，可能会更让人迷惑不解，我们基于示例3的代码再创建一个相同散列值的对象，来看看能在字典中找到吗：

1

print(HashableType('jack') in d)

执行结果：

1

False

这里 HashableType(‘jack’) 新建的对象和之前的 test1 对象有相同的 name 属性，不是应该和字典中的 test1 有相同的散列值吗？为什么查询结果是 False 呢？本人在上一节的字典工作原理的第二部分介绍过，在字典背后的数组存储空间，根据散列值计算出的偏移位置找到 key 对象后，还要做一些检查，其中第三个检查就是调用__eq__比较两对象是否相等。这里原对象的 name 属性已经改为 “tom“ 了，所以新对象 HashableType(‘jack’) 和存在字典里的原对象的相等比较结果是 False，最终字典的查询结果也是 False。

那为什么在字典的查询过程中，除了检查散列值，还要检查对象的相等性呢？因为我们知道，散列值是一个整数，即使我们在一个现代的 64 位的架构上跑程序，还是有一定的概率导致两个不相等的对象有相同的散列值。

考虑到这种情况，我们可以引申出可散列类型的第二个原则：

原则二：两个可散列对象相等，那么它们的散列值一定相等，即如果对象 a == b，那么 hash(a) == hash(b)。

如果不满足这个原则，会有什么结果，我们看一个例子。

示例4：

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

class HashableType(object):
  def __init__(self, name, age):
    self.name = name
    self.age = age

  def __eq__(self, other):
    if isinstance(other, HashableType) and other.age == self.age:
      return True
    return False

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


d = dict()
test1 = HashableType('jack', 20)
d[test1] = 1
test2 = HashableType('tom', 20)
print(f"is test1 equal to test2? {test1 == test2}")
print(f"is test1 in dict? {test1 in d}")
print(f"is test2 in dict? {test2 in d}")

执行结果：

1
2
3

is test1 equal to test2? True
is test1 in dict? True
is test2 in dict? False

test2 虽然和 test1 对象相等，但却无法在字典中找到它，原因在于两者的散列值不同。这样的结果显然违背了字典的定义。

那么，原则二命题的逆命题是否成立？即 ”如果 hash(a) == hash(b)，那么 a == b“ 是否成立？在解释原则一中举的例子时，已经介绍过，在任何环境下运行字典，都有一定的概率导致两个不相等的对象有相同的散列值，这叫散列冲突。通过优化散列函数可以减少散列冲突的发生的概率，但是无法完全避免。 所以原则二的逆命题并不成立。换句话说，我们可以得到一个更严谨的原则三：

原则三：如果 hash(a) == hash(b)，那么 a 和 b 很可能相等；

注意，是很可能，而不是一定，所以原则三对于编写可散列类型没有什么指示作用。

字典、集合，或者其它基于对象散列值进行查询的类型，无论用什么语言实现，都使用这些原则来实现快速的 O(1) 查询功能。

总结

本文介绍了字典的工作原理，以及延伸出可散列类型的三个原则，其中两个原则是设计可散列类型的关键。概括地说，你如果想实现一个可散列类型，使它的对象可以存放在字典、集合等容器中支持这些容器的一切操作，那么你必须满足以下要求：

1. 为类自定义__hash__方法和__eq__方法；
2. 对象的散列值，在对象的生命周期中，不可改变；
3. __hash__方法和__eq__方法需要满足：如果对象 a == b，那么必须 hash(a) == hash(b)。

参考

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/

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

Buy Me a Coffee

PayPal

微信

支付宝