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

前言

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

本文是第一篇，着重介绍对象的相等性、散列值、可散列性等基础概念，以及如何自定义可散列类型和不可散列类型。

第二篇，在 这里

第三篇，在 这里

对象的相等性

在 Python中“is”、“==”以及“__eq__”的区别 一文中，介绍了==运算符的工作方式，它的背后其实是调用了类的__eq__方法，从而判断对象的相等性。相等性（equality）在 Python 中似乎不太受人待见，其实，它比大部分人想象的要更复杂、更重要。

为了让一个对象，能够和另一个对象以某种方式来比较，从而判断它们是否相等，你需要在它的类里实现一个__eq__方法。该方法返回一个布尔类型的值，或者返回一个NotImplemented特殊值，如果你根本不想、或者不知道如何去实现这个方法。如果要判断不相等，即!=运算符，有另一个对应的__ne__方法。工作方式和__eq__一样。

默认情况下，自定义的类中，__eq__方法是继承自object类的，它比较两个实例对象的标识符（identity），即对象的id，id 不相等的两个对象 a 和 b，它们也不具有相等性（ a == b 返回 False）。同样，对象肯定和自己相等（a == a 返回 True）。

以前 Python2 中，用户自定义的类，如果只覆盖（override）默认的__eq__方法，而没有覆盖__ne__方法，Python 会报错。但 Python3 中，已经被优化过了，如果用户只定义了自己的__eq__方法和没有定义__ne__方法，Python 会自动为用户实现一个__ne__方法（其实就是对__eq__方法求反）。

示例1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

  def __eq__(self, other):
    return NotImplemented

a = MyTest('Jack')
b = MyTest('Jack')
print(a == b)

执行结果：

1

False

返回NotImplemented的__eq__方法，等同于没有定义该方法而继承object类的默认方法，默认方法比较的是对象的 id。a 和 b 虽然看上去内容似乎相同，但指向两个不同的对象，所以 a == b 返回 False。

示例2：

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

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

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

a = MyTest('Jack')
b = MyTest('Jack')
print(a == b)

执行结果：

1

True

和上一个例子的区别在于，自定义了__eq__的实现：只要两个对象类型都是 MyTest 并且 name 相等，对象就相等。a 和 b 指向对象的 name 都是 ‘Jack’，所以 a == b 返回 True。

对象的散列值

散列值（hash value 或 hashes）是一个整形数值，代表的含义是 ”对象的值“。一个对象是可散列的（hashable），我们就可以通过hash()函数来得到它的散列值。hash()函数会调用对象自己的__hash__方法来获取散列值。关于可散列性将在下一节讲。

和对象的相等性一样，自定义的类如果没有实现__hash__方法，则继承object类的__hash__作为默认的方法。默认的方法也是基于对象的 identity 来产生一个散列值。Python 3.7 中，实现方式是 identity 右移四位：

示例3：

1
2
3
4

x = object()
print(f'Hash of x: {hash(x)}')
print(f'id of x: {id(x)}')
print(f'id of x >> 4: {id(x) >> 4}')

执行结果：

1
2
3

Hash of x: 8794977984775
id of x: 140719647756400
id of x >> 4: 8794977984775

可以看到，对象的 id 右移四位，和默认的__hash__方法产生的散列值相等。由于不同对象的 id 一定是不同的，所以在默认情况下，不同对象的散列值也一定不同，无论他们的内容是否相同。这主要是为了防止小概率的散列冲突发生。

对象的可散列性

上一节提到，只有可散列的对象才具有散列值。那么什么是可散列的对象呢？大部分程序员可能不会主动意识到对象是否可散列，直到他们遇到如下错误：

1
2
3
4

>>> {{1}: 'a'}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'

这里我们想把一个集合对象作为 key，插入到字典中，但遇到了 ”不可散列的类型“ 的错误。所以，可散列性是一个很重要的概念，因为字典、集合等容器都要求元素是可散列的，并用它们的散列值来实现复杂度为 O(1) 的快速查询。

那么到底什么是可散列性？这里再摘取 Python词汇表 中关于可散列性的完整定义，翻译成中文：

可散列的

一个对象具有在其生命周期内不会改变的散列值（它需要一个__hash__()方法），并可以同其他对象进行比较（它需要具有 __eq__() 方法），那么这个对象就是可散列的。两个比较起来相同的可散列对象，必须要有相同的散列值。

可散列性使得对象能够作为字典键或集合成员使用，因为这些数据结构要在内部使用散列值。

大多数 Python 中的不可变的内置对象都是可散列的；可变容器（例如列表或字典）都不可散列；不可变容器（例如元组和 frozenset）仅当它们的元素均为可散列时才是可散列的。 用户自定义类的实例对象默认是可散列的。 它们在比较时一定不相同（除非是与自己比较），它们的散列值的生成是基于它们的 id()。

这段话不难理解，如果一个类实现了__hash__方法和__eq__方法，这个类就是可散列类型。换句话说，要让自定义的类是可散列类型，需要同时定义__hash__方法和__eq__方法。 可散列对象__hash__方法返回散列值，散列值将在字典、集合查询时用到。

前两节提到，自定义的类默认继承object类的__hash__方法和__eq__方法，所以自定义的类默认是可散列的，散列值基于对象的 id 生成，不同版本的 Python 实现不同；默认的__eq__比较方式也是基于对象 id，对象只有和自己比较才相等。

如果要让自定义的类按自己的方式计算散列值从而支持散列，只要在类中实现__hash__方法和__eq__方法从而覆盖掉基类中的这两个方法即可。

需要注意的是，上面引用的话，还蕴含了两个可散列类型需要具备的重要原则：

• 可散列对象，它的散列值在它的生命周期内永远不可改变。
• 两个可散列对象相等，那么它们的散列值一定相等，即如果对象 a == b，那么 hash(a) == hash(b)。

所以自己实现__hash__方法和__eq__方法，必须遵从这两个特性，才能构建健壮的可散列类型。在本系列的第二篇文章中，会详细介绍这两点。

自定义不可散列类型

如何让自定义的类不可散列呢？只需满足自定义的类实现了__eq__方法而没有实现__hash__方法：

示例4：

1
2
3
4
5
6
7

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

test = MyTest('t1')
d = {test: 'a'}
print(d)

执行结果：

1

{<__main__.MyTest object at 0x00000258D01968C8>: 'a'}

自定义的类 MyTest，没有定义__hash__和__eq__方法，所以默认继承object类的方法，因此该类是可散列类型，对象可以作为字典的键。

示例5：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

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

test = MyTest('t1')
d = {test: 'a'}

执行结果：

1
2
3

Traceback (most recent call last):
...
TypeError: unhashable type: 'MyTest'

此处，自定义的类 MyTest 里定义了__eq__方法，Python 在解释代码的时候，看到了自定义的类中有这个方法，就会尝试找该类有没有实现__hash__方法，如果没有，就把__hash__方法设为 None，表示该类不可散列。

需要注意的是，不仅仅是继承自object, 任何继承自其它父类的子类，只要定义了自己的__eq__方法，都不会去继承父类的__hash__方法。 Python 文档原文：

A class that overrides __eq__() and does not define __hash__() will have its __hash__()implicitly set to None. When the __hash__()method of a class is None, instances of the class will raise an appropriate TypeError when a program attempts to retrieve their hash value, and will also be correctly identified as unhashable when checking isinstance(obj, collections.abc.Hashable).

If a class that overrides __eq__() needs to retain the implementation of __hash__() from a parent class, the interpreter must be told this explicitly by setting __hash__ = <ParentClass>.__hash__.

翻译成白话文，就是如果一个类定义了自己的__eq__方法，而没有定义__hash__方法，那么它的__hash__方法设为 None，而不会继承父类的__hash__方法；如果要让它继承父类的__hash__方法，则需要显示的设置__hash__ = <ParentClass>.__hash__ 。看一个例子：

示例6：

 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

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

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

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


class MyTest2(MyTest):
  def __init__(self, name, age):
    MyTest.__init__(self, name)
    self.age = age

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

d = dict()
t1 = MyTest('Jack')
d[t1] = 90
print(t1 in d)
t2 = MyTest2('Tom', 13)
d[t2] = 85
print(d)

执行结果：

1
2
3
4
5
6

in parent class's hash function
in parent class's hash function
True
Traceback (most recent call last):
...
TypeError: unhashable type: 'MyTest2

MyTest 类中定义了__hash__方法和__eq__方法，所以是可散列的，在存储语句 “d[t1] = 90” 和 查询语句 “t1 in d” 执行的时候，会调用__hash__方法获取散列值，所以打印了两次 “in parent class’s hash function”，并且查询结果为 True。子类 MyTest2 中，实现了__eq__方法而没有实现__hash__方法，按照前面的介绍，这种情况下该类不会继承父类的__hash__方法，所以它是不可散列类型。执行存储语句 “d[t2] = 85” 的时候，Python 抛出 TypeError，告诉用户 MyTest2 是不可散列类型。

所以，想让自定义的类是不可散列的，最简单的方式就是定义__eq__而不定义__hash__。

关于设计和自定义可散列类型的一些重要原则，以及字典、集合等类型的工作原理，将在下一篇文章中详细介绍。

参考文档

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

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

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

Buy Me a Coffee

PayPal

微信

支付宝