通过散列表深入理解字典

2021-02-18

注：本文是对《跟老齐学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中的实现之前，先简要说明散列函数及其工作原理。

散列函数是一种可以将任何长度的数据映射到固定长度的值的函数，这个映射过程称为散列（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()的参数，如果改用字符串，返回的也是整数形式的散列值。

1 2	>>> 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。

1 2	>>> 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，则不可散列。

散列表

了解了散列函数之后，就可以看看散列表是什么了。散列表是一种数据结构，它存储的是键值对（key-value）。

在散列表中，每个键值对的键必须是可散列的，这是因为存储的键值对通过使用其键的散列值进行索引。如果查询散列表中的某个元素，其查询速度与表中所存储的键值对数量无关，不论表的长度增加10倍还是10万倍，查询某个特定元素的速度都不会受到影响。

散列表是怎么实现的呢？一种经典的做法是通过一个可变容器存储数据和索引，并通过键的散列值建立索引，借此可以查询到特定的数据。形象地说，是创建一个大桶（bucket），里面放很多小桶。每个小桶都由键的散列值建立索引，小桶中装的就是数据。

在下面的示例中，演示用Python实现散列表，从中可以理解散列表的基本余力。当然，在真正的编程中，不需要自定义这种散列表对象，因为Python中的字典类型对象就能实现。

import pprint

class Hashtable:
    def __init__(self, elements):
        self.bucket_size = len(elements)
        self.buckets = [[] for i in range(self.bucket_size)]
        self._assign_buckets(elements)

    def _assign_buckets(self, elements):
        for key, value in elements:
            hashed_value = hash(key)
            index = hashed_value % self.bucket_size
            self.buckets[index].append((key, value))

    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        bucket = self.buckets[index]
        for key, value in bucket:
            if key == input_key:
                return(value)
        return None

    def __str__(self):
        return pprint.pformat(self.buckets) # 返回一个可打印的对象

if __name__ == "__main__":
     capitals = [
        ('France', 'Paris'),
        ('United States', 'Washington D.C.'),
        ('Italy', 'Rome'),
        ('Canada', 'Ottawa')
    ]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")

注意观察第10行开始的for循环语句，在第11行，计算每个可散列元素的键的散列值，用它计算一个索引值（第12行），将此索引值作为self.buckets容器（bucket，也有直接译为“桶”）的索引（第13行），并向该索引对应的数据结构（列表）中增加数据(key,value)。

如果将前面提到过的环境变量PYTHONHASHSEED的值设置为46$^{[5]}$，就会得到下面的输出结果。有两个空容器，另外两个容器中分别存储了两个键值对数据。

[[('United States', 'Washington D.C.'), ('Canada', 'Ottawa')],
 [],
 [],
 [('France', 'Paris'), ('Italy', 'Rome')]]
The capital of Italy is Rome

注意，如果不设置PYTHONHASHSEED 的值，会得到与上述显示不一样的值。

在这个示例中，用Python创建了一个散列表，以元组为元素的列表作为输入。在初始化的时候，以输入对象的长度创建一个列表容器，然后将输入的数据存储到此容器中。

然而，如你在输出中所见，在输出结果中，有两个空列表，有另外两个列表中分别存储了不同的两个数据，这是什么原因？是因为在这个Python散列表中出现了散列碰撞。

使用Python标准库中的hash()函数计算散列值，出现碰撞是在所难免的。为此可以用扩大容器的容量（即长度），从而降低出现碰撞的概率，但是不能根本杜绝。

另外，容器的数量扩大，也会浪费更多的空间。下面的示例做了一点修改，在第4行，将self.bucket_size变为原来的2倍了。

hl_lines=”3” 
class Hashtable: 
    def __init__(self, elements): 
        self.bucket_size = len(elements) * 2 
        self.buckets = [[] for i in range(self.bucket_size)] 
        self._assign_buckets(elements)

再次执行程序，得到了下面的结果，仍然没有解决碰撞问题，并且已经有五个空容器了。

[[],
 [],
 [],
 [('Canada', 'Ottawa')],
 [],
 [],
 [('United States', 'Washington D.C.'), ('Italy', 'Rome')],
 [('France', 'Paris')]]
The capital of Italy is Rome

如果有两个散列碰撞，它们会被放入同一个容易。既然碰撞在所难免，那么在实现哈希表的时候，就要解决这个问题。通常的解决方法有两种：

开放式寻址法（open addressing）
分离链接法（separate chaining）

分离链接法在上面的示例中已经实现过了，在示例中，其实使用的是一个嵌套列表，如果要查询指定的值，需要对整个列表全部扫描。由此可见，分离链接法是在一个容器中用另外一种数据结构创建一系列的数据对象。

使用开放式寻址方法，如果某个索引下的容易中已有数据，则只要找到一个新的容器即可，所以要判断容器中是否已经有数据，并且要能找到新的容易。在原有的Hashtable类中修改_assign_buckets()方法，代码如下。

def _assign_buckets(self, elements):
    self.buckets = [None] * self.bucket_size

    for key, value in elements:
        hashed_value = hash(key)
        index = hashed_value % self.bucket_size

        while self.buckets[index] is not None:
            print(f"The key {key} collided with {self.buckets[index]}")
            index = (index + 1) % self.bucket_size

        self.buckets[index] = ((key, value))

上面代码中，第2行，首先把大容器中设置了默认值None，然后在第8行用while循环，检查某索引的列表内是否已经存储了数据。

之后，还需要修改get_value方法，有必要检查索引对应的数据是否为None。

def get_value(self, input_key):
    hashed_value = hash(input_key)
    index = hashed_value % self.bucket_size
    while self.buckets[index] is not None:
        key,value = self.buckets[index]
        if key == input_key:
            return value
        index = (index + 1) % self.bucket_size

前面的示例中，“Italy”键与“France”键的散列值冲突，按照修改之后的方法，这两个键就不会存储到同一个容器（列表）中，而是将“Italy”为键的数据存储到下一个“桶”里面。

The key Italy collided with ('France', 'Paris')
[None,
 None,
 ('Canada', 'Ottawa'),
 None,
 ('France', 'Paris'),
 ('Italy', 'Rome'),
 None,
 ('United States', 'Washington D.C.')]
The capital of Italy is Rome

在开放式寻址法中，如果要删除散列表中的元素，只能执行逻辑删除，而不是物理删除。因为如果删除正好是发生了散列冲突的数据，那么与其对应的另外一个数据，就没办法找到了。

例如，前面在示例中，“Italy”与先前插入的元素（“France”）冲突，于是将它存储到索引值加一后的下一个“桶”里面，如果物理删除“France”元素，将无法找到“Italy”无法访问。

因此，在使用开放式寻址策略时，要删除元素，必须用一个哑值（dummy value，即虚拟数据）替换其存储区，这样解释器就可以根据冲突的这个位置检索到下一个位置。

字典：Python散列表的应用

现在，我们已经了解了哈希表的基本含义，下面来看一下它在Python语言中最重要的应用：字典。Python中的字典是使用散列表和“开放式寻址”冲突解决方法构建的。

在Python的基本知识中，我们知道字典是“键-值对”的集合$^{[3]}$ ，因此要定义字典，必须提供一个用逗号括起来的大括号内的键-值对列表，如以下示例所示：

>>> chess_players = {
...    "Carlsen": 2863,
...    "Caruana": 2835,
...    "Ding": 2791,
...    "Nepomniachtchi": 2784,
...    "Vachier-Lagrave": 2778,
... }

这里所创建的字典chess_players中包括五个键值对：世界排名前五的国际象棋棋手名称及其得分。

要检索特定值，只需要使用方括号指定键即可：

1 2	>>> chess_players["Nepomniachtchi"] 2784

If you try to access a non existing element, the Python interpreter throws a Key Error exception:

如果访问不存在的元素，Python解释器将抛出Key Error异常：

>>> chess_players["Mastromatteo"]
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
KeyError: 'Mastromatteo'

字典内的元素，可以用.items()方法生成可迭代对象：

>>> for (k, v) in chess_players.items():
...     print(k,v)
... 
Carlsen 2863
Caruana 2835
Ding 2791
Nepomniachtchi 2784
Vachier-Lagrave 2778

另外，如果使用字典的.keys()和.values()两个方法，可以分别得到字典的键和值所生成的对象（在参考文献[3]中，对这类对象有特别说明），也是可迭代的。

>>> chess_players.keys()
dict_keys(["Carlsen", "Caruana", "Ding", "Nepomniachtchi", "Vachier-Lagrave"])
>>> chess_players.values()
dict_values([2863, 2835, 2791, 2784, 2778])

字典是可变对象，可以增加键值对。

1
2
3

>>> chess_players["Grischuk"] = 2777
>>> chess_players
{'Carlsen': 2863, 'Caruana': 2835, 'Ding': 2791, 'Nepomniachtchi': 2784, 'Vachier-Lagrave': 2778, 'Grischuk': 2777}

注意，字典中键值对的键，必须是可散列对象，因为字典是基于散列表而创建的。如果键不是可散列的，Python会爆出TypeError异常。

>>> my_list = ["Giri", "Mamedyarov"]
chess_players[my_list] = 2764
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

如果要删除字典的键值对，可以使用del语句，注意，这不是函数。

1
2
3

>>> del chess_players["Grischuk"]
>>> chess_players
{'Carlsen': 2863, 'Caruana': 2835, 'Ding': 2791, 'Nepomniachtchi': 2784, 'Vachier-Lagrave': 2778}

删除元素的语句，并不不会执行物理删除，它只是将语句中的“键”替换为虚拟值，这就是前面提到的开放寻址法所起的作用。但是，在实际操作总，由于解释器会为处理所有这些复杂问题，我们不用去关心，给我们的感觉就是“删除”了那个指定的键值对。

探寻所以然

字典是散列表，那么它在后台是如何运行的？下面就在前面“知其然”基础上，了解一些“所以然”的内容。

特别提醒，此处我们的所有讨论，都是基于Python的最新版本，因为Python 3.6开始，字典已经发生了很大变化，并且变得更小，更快，甚至功能更强大，因为它现在已经能够实现“插入排序”了$^{[6]}$。

下面创建一个空字典，并检查它的大小，会发现这个空字典占据了240bytes的内存。

>>> import sys
>>> my_dict = {}
>>> sys.getsizeof(my_dict)
240

空字典占据240bytes的内存，但是，如果增加了数据，会发现，它所占内存并没有变化。

1
2
3

>>> my_dict["a"] = 100
>>> sys.getsizeof(my_dict)
240

这是为什么呢？因为从Python 3.6开始，字典中值存储在不同的数据结构中，而字典仅包含指向实际值存储位置的指针。此外，当创建一个空字典时，它同时创建一个Python散列表，其中包含8个存储容器，长度只有240个字节，因此字典中增加了第一个元素后，根本没有改变其大小。

下面尝试增加更多的元素，会发现字典所占内存空间（即字典大小）在增长。

>>> for i in range(20):
...     my_dict[i] = 100
...     print(f"elements = {i+1} size = {sys.getsizeof(my_dict)}")
... 
elements = 1 size = 240
elements = 2 size = 240
elements = 3 size = 240
elements = 4 size = 240
elements = 5 size = 240
elements = 6 size = 368
elements = 7 size = 368
elements = 8 size = 368
elements = 9 size = 368
elements = 10 size = 368
elements = 11 size = 648
elements = 12 size = 648
elements = 13 size = 648
elements = 14 size = 648
elements = 15 size = 648
elements = 16 size = 648
elements = 17 size = 648
elements = 18 size = 648
elements = 19 size = 648
elements = 20 size = 648

如上运行结果所示，在插入第六个元素（第10行）和第十一元素（第15行）之后，字典变大了，并非连续变大。这又是什么原因呢？这是为了使Python散列表更快并减少冲突，所以当字典充满三分之二时，解释器会调整字典的大小$^{[7]}$ 。

现在，将上面所创建字典中的元素都删除了，再看一看该字典的大小。

>>> keys = list(my_dict.keys())
>>> for key in keys:
...     del my_dict[key]
...
>>> my_dict
{}
>>> sys.getsizeof(my_dict)
648

与没有删除前比较，发现居然大小没变。之所以如此，就是由于字典的内存占用非常小，并且在使用字典时删除操作并不频繁，因此与每次删除后动态调整字典大小，解释器更愿意浪费一点空间。但是，如果通过调用.clear()方法清空字典，由于它是批量删除，因此释放了空间，并且最小达到72个字节。

1
2
3

>>> my_dict.clear()
>>> sys.getsizeof(my_dict)
72

结论

本文主要介绍了Python散列表及其在字典对象类型中的具体应用，从而更深入了解了字典的特点。

这篇文章的内容重点参考了Raymond Hettinger在2017年Pycon大会上的演讲$^{[8]}$，Raymond Hettinger 是Python的核心开发者，为Python的发展做出了重大贡献。

参考文献

[1]. http://thepythoncorner.com/dev/hash-tables-understanding-dictionaries/

[2]. https://www.ruanyifeng.com/blog/2011/08/what_is_a_digital_signature.html

[3]. Python大学实用教程. 齐伟. 北京：电子工业出版社

[4]. https://docs.python.org/3.3/using/cmdline.html#envvar-PYTHONHASHSEED

[5]. https://stackoverflow.com/questions/30585108/disable-hash-randomization-from-within-python-program

[6]. “插入顺序”在Python 3.6中实现，被Guido在Python 3.7中正式认可：https://mail.python.org/pipermail/python-dev/2017-December/151283.html

[7]. https://mail.python.org/pipermail/python-list/2000-March/048085.html

[8]. https://pyvideo.org/pycon-us-2017/modern-python-dictionaries-a-confluence-of-a-dozen-great-ideas.html

← Python中`__name__`有什么用编程的黄金时代结束了吗？ →

赏

使用支付宝打赏

使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

关注微信公众号，读文章、听课程，提升技能