你们有没有想过 Python/ target=_blank class=infotextkey>Python 字典为何如此快速和可靠？答案是它们建立在另一种技术之上：哈希表。

了解 Python 哈希表的工作原理将使您更深入地了解字典的工作原理，这对于您理解 Python 来说是一个很大的优势，因为字典在 Python 中几乎无处不在。

 

哈希函数永久链接

在介绍哈希表及其 Python 实现之前，您必须了解什么是哈希函数及其工作原理。

哈希函数是一种可以将任意长度的数据映射为固定长度值的函数，称为哈希。

哈希函数具有三大特点：

1. 它们的计算速度很快：计算一段数据的哈希值必须是一个快速的操作。
2. 它们是确定性的：相同的字符串将始终产生相同的哈希值。
3. 它们产生固定长度的值：无论您的输入是一字节、十字节还是一万字节，生成的散列将始终具有固定的预定长度。

哈希函数中很常见的另一个特征是它们通常是单向函数：由于函数中实现了自愿数据丢失，您可以从字符串中获取哈希，但无法从哈希中获取原始字符串。这并不是每个哈希函数的强制功能，但当它们必须具有加密安全性时就变得很重要。

一些流行的哈希算法有MD5、SHA-1、SHA-2、NTLM。

哈希的常见用法永久链接

有很多东西依赖于哈希，哈希表只是其中之一。哈希的其他常见用法是出于加密和安全原因。

一个具体的例子是当您尝试从互联网下载开源软件时。通常，您还会发现一个伴随文件，它是该文件的签名。这个签名只是原始文件的哈希值，它非常有用，因为如果您自己计算原始文件的哈希值并与网站提供的签名进行检查，您可以确定您下载的文件没有已被篡改。

哈希的另一个常见用途是存储用户密码。您是否曾经问过自己，为什么当您忘记某个网站的密码并尝试恢复该密码时，该网站通常会让您选择另一个密码，而不是返回您选择的原始密码？答案是该网站不会存储您选择的整个密码，而仅存储其哈希值。

这样做是出于安全原因，因为如果某些黑客获得了网站数据库的访问权限，他们将无法知道您的密码，而只能知道您密码的哈希值，并且由于哈希函数通常是单向函数，因此您可以确定他们将永远无法从哈希值开始获取您的密码。

Python hash()函数永久链接

Python有一个内置函数来生成对象的哈希值，即函数hash()。该函数接受一个对象作为输入，并将哈希值作为整数返回。

在内部，此函数调用.__hash__()输入对象的方法，因此如果您想让自定义类可哈希，您所要做的就是实现该方法以.__hash__()根据对象的内部状态返回整数。

现在，尝试启动 Python 解释器并hash()稍微使用一下该函数。对于第一个实验，尝试对一些数值进行哈希处理：

>>> hash(1)
1
>>> hash(10)
10
>>> hash(10.00)
10
>>> hash(10.01)
230584300921368586
>>> hash(-10.01)
-230584300921368586

如果您想知道为什么这些散列似乎具有不同的长度，请记住 Pythonhash()函数返回整数对象，这些对象在标准 64 位 Python 3 解释器上始终用 24 个字节表示。

如您所见，默认情况下，整数值的哈希值就是该值本身。请注意，无论您要散列的值的类型如何，这都有效，因此整数1和浮点数1.0具有相同的散列：1。

这有什么特别之处？好吧，这显示了您之前学到的知识，即哈希函数通常是单向函数：如果两个不同的对象可能具有相同的哈希值，则不可能执行从哈希值开始并返回到原始对象的相反过程。在这种情况下，有关原始哈希对象的类型的信息已经丢失。

通过哈希数字您可以注意到的另一件有趣的事情是，十进制数具有与其值不同的哈希值，并且负值具有负哈希值。但是，如果您尝试对获得的十进制值的相同数字进行哈希处理，会发生什么情况？答案是您得到相同的哈希值，如以下示例所示：

>>> hash(0.1)
230584300921369408
>>> hash(230584300921369408)
230584300921369408
>>> hash(0.1) == hash(230584300921369408)
True

如您所见，整数 number 的哈希值230584300921369408与 number 的哈希值相同0.1。如果您想到之前学到的关于哈希函数的知识，这是完全正常的，因为如果您可以对任何数字或任何字符串进行哈希处理以获得固定长度值，因为您不能拥有由固定长度值表示的无限值，这意味着必须有重复的值。它们实际上是存在的，称为碰撞。当两个对象具有相同的哈希值时，就说它们发生了碰撞。

对字符串进行哈希处理与对数值进行哈希处理没有太大区别。启动 Python 解释器并尝试对字符串进行哈希处理：

>>> hash("Bad Behaviour")
7164800052134507161

正如您所看到的，字符串是可散列的并且也会生成数值，但是如果您尝试运行此命令，您可能会发现您的 Python 解释器没有返回与上面示例相同的结果。这是因为从 Python 3.3 开始，字符串和字节对象的值在哈希过程之前会使用随机值进行加盐。这意味着在进行哈希处理之前，字符串的值会在每次解释器启动时使用随机值进行修改。如果要覆盖此行为，可以PYTHONHASHSEED在启动解释器之前将环境变量设置为大于零的整数值。

正如您所料，这是一项安全功能。之前您了解到，网站通常存储密码的哈希值而不是密码本身，以防止对网站数据库的攻击窃取所有网站密码。如果网站仅存储计算出的哈希值，则攻击者可能很容易知道原始密码是什么。他们只需要获取大量常用密码（网络上充满了这些列表）并计算其相应的哈希值即可获得通常称为彩虹表的内容。

通过使用彩虹表，攻击者可能无法获取数据库中的每个密码，但仍然能够窃取其中的绝大多数。为了防止这种攻击，一个好主意是在对密码进行哈希处理之前对密码进行加盐，即在计算哈希值之前使用随机值修改密码。

从 Python 3.3 开始，解释器默认在散列之前对每个字符串和字节对象加盐，以防止可能的 DOS 攻击，正如 Scott Crosby 和 Dan Wallach 在2003 年论文中所演示的那样。

DOS 攻击（DOS 代表拒绝服务）是一种攻击者故意耗尽计算机系统资源，使系统无法再向客户端提供服务的攻击。在 Scott Crosby 演示的这个特定攻击案例中，攻击可能会向目标系统注入大量散列冲突的数据，从而使目标系统使用更多的计算能力来解决冲突。

Python 可哈希类型永久链接

所以此时，您可能想知道是否有任何 Python 类型是可哈希的。这个问题的答案是否定的，默认情况下，Python 中只有不可变类型是可哈希的。如果您使用不可变的容器（如元组），内容也应该是不可变的，以便可散列。

尝试在 Python 中获取不可哈希类型的哈希值，您将从TypeError解释器中获取 a ，如以下示例所示：

>>> 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'

但是，每个自定义定义的对象在 Python 中都是可哈希的，并且默认情况下其哈希值源自其 id。这意味着同一类的两个不同实例默认情况下具有不同的哈希值，如下例所示：

>>> class Car():
...     velocity = 0
...     direction = 0
...     damage = 0
...
>>> first_car = Car()
>>> second_car = Car()
>>> hash(first_car)
274643597
>>> hash(second_car)
274643604

正如您所看到的，默认情况下同一自定义对象的两个不同实例具有不同的哈希值。但是，可以通过.__hash__()在自定义类中实现方法来修改此行为。

哈希表永久链接

现在您知道什么是哈希函数，您可以开始检查哈希表了。哈希表是一种数据结构，允许您存储键值对的集合。

在哈希表中，每个键值对的键必须是可哈希的，因为存储的键值对是通过使用其键的哈希来索引的。哈希表非常有用，因为查找表中元素所需的平均指令数与表本身中存储的元素数无关。这意味着即使您的表增长十倍或一万倍，查找特定元素的整体速度也不会受到影响。

哈希表通常是通过创建可变数量的存储桶来实现的，这些存储桶将包含您的数据，并通过散列它们的键来索引这些数据。键的哈希值将确定用于该特定数据块的正确存储桶。

在下面的示例中，您可以找到 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) # here pformat is used to return a printable representation of the object

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')}")

查看for从第 9 行开始的循环。对于哈希表的每个元素，此代码计算键的哈希值（第 10 行），根据哈希值计算元素在存储桶中的位置（第 11 行）并添加一个元组在桶中（第 12 行）。

PYTHONHASHSEED将环境变量设置为值后尝试运行上面的示例46，您将得到以下输出，其中两个存储桶为空，另外两个存储桶各包含两个键值对：

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

请注意，如果您尝试在未设置PYTHONHASHSEED变量的情况下运行程序，您可能会得到不同的结果，因为您已经知道 Python 中的哈希函数，从 Python 3.3 开始，在哈希过程之前使用随机种子对每个字符串加盐。

在上面的示例中，您实现了一个 Python 哈希表，该哈希表采用元组列表作为输入，并将它们组织在多个等于输入列表长度的存储桶中，并使用模运算符来分配表中的哈希值。

但是，正如您在输出中看到的，您有两个空桶，而另外两个桶各有两个不同的值。当发生这种情况时，就说Python 哈希表中存在冲突。

使用标准库的hash()函数，哈希表中的冲突是不可避免的。您可以决定使用更多数量的桶并降低发生碰撞的风险，但您永远无法将风险降低到零。

此外，您要处理的存储桶数量越多，浪费的空间就越多。要测试这一点，您可以简单地使用两倍于输入列表长度的存储桶数量来更改前一个示例的存储桶大小：

```python 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 （元素）

Running this example, I ended up with a better distribution of the input data, but I had however a collision and five unused buckets:

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

正如您所看到的，两个哈希发生冲突并已被插入到同一个存储桶中。

由于冲突通常是不可避免的，因此要实现哈希表，还需要实现冲突解决方法。解决哈希表中冲突的常见策略是：

• 开放寻址
• 单独链接

单独的链接是您在上面的示例中已经实现的链接，它包括使用另一个数据结构在同一存储桶中创建值链。在该示例中，您使用了一个嵌套列表，在过度占用的存储桶中查找特定值时必须完全扫描该列表。

在开放寻址策略中，如果您应该使用的存储桶繁忙，您只需不断寻找要使用的新存储桶即可。要实现此解决方案，您需要对如何将存储桶分配给新元素以及如何检索键的值进行一些更改。从该_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))

None正如你所看到的，所有的桶在赋值之前都被设置为默认值，并且while循环不断寻找一个空的桶来存储数据。

由于存储桶的分配发生了变化，检索过程也应该发生变化，因为在该get_value()方法中，您现在需要检查键的值，以确保您找到的数据是您正在寻找的数据：

    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

在查找过程中，在该 get_value()方法中，您使用该None值来检查何时需要停止查找键，然后检查数据的键以确保返回正确的值。

运行上面的示例，键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无法访问，因为它不占用其自然目标存储桶，这对于解释器来说似乎是空的。

因此，当使用开放寻址策略时，要删除一个元素，您必须将其存储桶替换为虚拟值，这向解释器表明，必须将其视为已删除以进行新插入，但必须将其用于检索目的。

字典：实现 Python 哈希表永久链接

现在您已经了解了什么是哈希表，让我们来看看它们最重要的 Python 实现：字典。Python 中的字典是使用哈希表和开放寻址冲突解决方法构建的。

您已经知道字典是键值对的集合，因此要定义字典，您需要提供用大括号括起来的以逗号分隔的键值对列表，如下例所示：

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

在这里，您创建了一个名为 的字典chess_players，其中包含世界上排名前五的国际象棋棋手及其实际等级。

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

>>> chess_players["Nepomniachtchi"]
2784

如果尝试访问不存在的元素，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

要迭代 Python 字典的键或值，您也可以使用.keys()或方法：.values()

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

要将另一个元素插入字典中，您只需为新键分配一个值：

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

要更新现有键的值，只需为先前插入的键分配不同的值即可。

请注意，由于字典是建立在哈希表之上的，因此您只能插入键为hashable 的元素。如果元素的键不可散列（例如列表），解释器会抛出异常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语句，指定要删除的键：

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

删除条目不会删除字典中的实际值，它只是用虚拟值替换键，以便开放寻址冲突解决方法将继续工作，但解释器会为您处理所有这些复杂性，忽略已删除的元素。

Python 哈希表的 Pythonic 实现永久链接

现在您知道字典是 Python 哈希表，但您可能想知道其实现原理是如何工作的，因此在本章中，我将尝试为您提供一些有关 Python 哈希表实际实现的信息。

请记住，我在这里提供的信息基于最新版本的 Python，因为 Python 3.6 字典已经发生了很大变化，现在更小，更快，甚至更强大，因为它们现在是插入有序的（插入有序保证已已在 Python 3.6 中实现，但在 Python 3.7 中已被 Guido 正式认可）。

尝试创建一个空的Python字典并检查它的大小，你会发现一个空的Python字典占用了240字节的内存：

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

通过运行这个例子可以看到，Python字典的基本占用是240字节。但如果您决定添加一个值会发生什么？嗯，这可能看起来很奇怪，但大小并没有改变：

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

那么，为什么字典的大小没有改变呢？因为从 Python 3.6 开始，值存储在不同的数据结构中，并且字典仅包含指向实际值存储位置的指针。此外，当您创建一个空字典时，它会开始创建一个包含 8 个存储桶、长度仅为 240 字节的 Python 哈希表，因此字典中的第一个元素的大小根本没有改变。

现在尝试添加更多元素并查看字典的行为方式，您将看到字典增长：

>>> 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

正如您所看到的，在插入第六个和第十一个元素后，字典变大了，但为什么呢？因为为了使我们的 Python 哈希表更快并减少冲突，解释器在字典已满三分之二时会不断调整字典的大小。

现在，尝试删除字典中的所有元素，一次一个，完成后再次检查大小，你会发现即使字典为空，空间也没有被释放：

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

发生这种情况的原因是，由于字典的内存占用非常小，并且在使用字典时删除并不频繁，因此解释器宁愿浪费一点空间，也不愿在每次删除后动态调整字典的大小。但是，如果通过调用该.clear()方法清空字典，由于这是批量删除，因此会释放空间，并且字典大小将达到最小值 72 字节：

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

正如你所想象的，在这个字典上的第一次插入将使解释器保留8个桶的空间，回到最初的情况。