Python的可散列对象

老齐

发布于 2021-03-11 15:08:20

5K00

代码可运行

文章被收录于专栏：老齐教室老齐教室

运行总次数：0

代码可运行

注：本文是对《跟老齐学Python：轻松入门》和《Python大学实用教程》有关字典对象的学习补充和提升。更多有关这两本书的资料，请阅读如下链接：

《跟老齐学Python：轻松入门》：http://www.itdiffer.com/learn_python.html
《Python大学实用教程》：http://www.itdiffer.com/python_course.html

是否想过，为什么Python中的字典对象会那么快，而且可靠？先说答案，就是因为它依赖于一个重要的算法：散列表（hash table，也有译为“哈希表”）。

理解散列表，有助于深入理解Python中字典的运行原理，这对理解Python编程语言是一个巨大的进步，因为字典在Python中几乎随处可见。

对于这个问题，计划用两篇文章解释。这里先介绍Python语言中的可散列对象。

散列函数

在介绍散列表以及它在Python中的实现之前，先简要说明散列函数及其工作原理。

散列函数是一种可以将任何长度的数据映射到固定长度的值的函数，这个映射过程称为散列（hash）。

散列函数具有以下三个特点：

计算速度快：计算一条数据的散列值，必须要快。
确定性：相同的字符串的散列值总相同。
散列值长度固定：无论输入的是1个字节、10个字节还是1万个字节，生成的散列值始终是固定的预定长度。
不可逆性：散列函数是一个“单向函数”，将字符串输入到散列函数，得到了散列值，但是不能反过来，不能从散列值得到原来的字符串。由于这个特性，它可以用于加密。

常用的散列函数有：MD5, SHA-1, SHA-2, NTLM.

能够找到一些网站，能够自动生成字符串的散列值，如下图所示，是使用https://www.md5online.org提供的功能得到的。

散列的应用

散列的应用范围比较广，散列表只是其一，其他方面诸如加密、安全等。

比如用散列函数生成文件的摘要（digest），并应用于数字签名（digital signature）

^{[2]}

。

再比如存储用户密码，这是散列的另一种常见应用。如果你在某个网站注册了用户，但是忘记密码了，在登录页面中常常会有“找回密码”或者“重置密码”的链接。如果点击“找回密码”，网站真的向你提供的邮箱中发送了你的密码，说明这个网站在存储密码的时候，根本没有加密，极有可能是“明码”保存了。这是非常危险的，一旦网站的用户个人数据出问题——时长会暴出网站的用户数据出问题的新闻——密码就赫然呈现在世人面前了。负责任的网站，都会用散列函数，将用户的密码加密，用户只能“重置密码”，而不能“找回”。所以，通常是给你预留的邮箱中发送重置密码的链接。

Python的内置散列函数

Python的内置函数hash()是一个散列函数，它能够返回输入对象的十进制整数形式的散列值。

以数字为例，例如：

>>> hash(1)
1
>>> hash(10)
10
>>> hash(10.0)
10
>>> hash(3.1415926)
326490306866391043

返回值即为输入数字的散列值。

特别注意，Python的hash()函数返回的是整数对象，这些对象在标准的64位Python 3解释器中始终以24个字节表示。

如上述代码，默认情况下，整数的散列值是其本身。请注意，hash(10)和hash(10.0)的结果一样。显然，10和10.0是两个不同的对象（一个是整数，另外一个是浮点数），而它们的散列值相同。反过来，根据相同的散列值，无法唯一判定输入对象是哪一个。这就是可以用散列加密的原因。

看一下hash()的文档——看文档，是一项重要的能力和习惯

^{[3]}

。

hash(obj, /)
    Return the hash value for the given object.

    Two objects that compare equal must also have the same hash value, but the  reverse is not necessarily true.

从文档中可知，如果两个对象相等，它们的散列值必须相等，或者说，如果两个对象已经通过==返回了True，就说明它们的散列值相等。反之，如果两个对象的散列值相等，这两个对象不一定相等，例如：

>>> hash(-1)
-2
>>> hash(-2)
-2
>>> -1 == -2
False

这更进一步说明，散列函数是“单向函数”。像上述示例这样，-1和-2的散列值相同，称为散列碰撞（collision），即两个对象的散列值产生了冲突。

以上示例中，都是以数字作为hash()的参数，如果改用字符串，返回的也是整数形式的散列值。

>>> hash("跟老齐学Python")
-8625257969505844567

但是，如果你在自己的计算机上重复上面的操作，注意字符串别输入错了，所得到的结果应该跟我这里演示的结果不同——前面参数为数字时，一定相同。

这是因为，自从Python3.3之后，对于字符串和字节对象，在进行散列处理之前，先增加了一个随机值，形象地说就是“加了一小撮盐”。“加盐”之后的字符串就变成了随机值。如果想出现这种情况，可以更改PYTHONHASHSEED的值

^{[4]}

，将它设置为大于零的整数。

可散列类型

在Python内置的对象类型中，并非都是可散列的，只有那些不可变对象，比如整数、浮点数、字符串、元组等，才是可散列的。

如果要将hash()用于不可散列的对象，结果会出现TypeError异常，例如：

>>> hash(["R","e","a","l","P","y","t","h","o","n"])
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

然而，自定义的对象，默认是可散列的，并且默认情况下，是以对象的id值作为hash()的参数。这就意味着，用同一个类，创建了两个不同的实例对象，它们会有不同的散列值，例如：

>>> class Laoqi:
...     pass
...
>>> x = Laoqi()
>>> y = Laoqi()
>>> hash(x)
8777241446265
>>> hash(y)
8777241446967
>>> hash(id(x)/16)==hash(x)  # 说明x的散列值是依据其id值得到的
True
>>> hash(id(y)/16)==hash(y)
True

如果你所见，用同一个类创建了两个实例对象，它们的散列值不同，当然，如果执行x==y，返回的是False。

>>> x == y
False

这符合Python的习惯，毕竟x和y是两个实例，在通常情况下，都是给类提供不同的参数，只不过这里演示得太简单了。

如果，由于某种需要，必须让两个实例具有相同的散列值，怎么办？可以在类里面重写__hash__()方法。

>>> class Laoqi:
...     def __hash__(self):
...         return 728
...
>>> a = Laoqi()
>>> b = Laoqi()
>>> a == b
False
>>> hash(a)
728
>>> hash(b)
728

这个示例进一步展示了前面提到的一种现象：散列值相同的对象不相等。并且，还说明，hash()函数其实是调用了对象中的__hash__()方法。如果检查一下，Python的内置对象类型中都有这个特殊方法。

>>> '__hash__' in dir(int)
True
>>> '__hash__' in dir(list)
True
>>> '__hash__' in dir(dict)
True
>>> '__hash__' in dir(str)
True
......

前面提到，Python中的对象分为可散列和不可散列两种类型，而这里检测之后，所有内置对象类型都具有__hash__方法，是不是意味着都能用于hash()函数呢？前面说过可变对象是不可散列类型。这又怎么理解？做如下操作：

>>> print(list.__hash__)
None
>>> print(str.__hash__)
<slot wrapper '__hash__' of 'str' objects>

以列表（可变对象，不可散列）和字符串（不可变对象，可散列）为例，发现它们的__hash__返回值不同，列表返回的是None，而字符串返回的是一个对象。这就给我们启发了。如果这样定义：

>>> class Laoqi:
...     __hash__ = None
...
>>> c = Laoqi()
>>> hash(c)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'Laoqi'

现在用所定义的类Laoqi创建了一个实例c，它就变成了不可散列的对象。综上可知，对象是否可散列，主要看它的__hash__是什么，如果是None，则不可散列。