Python哈希表：了解字典

作者:凯撒
发布时间:2024-03-31 11:50:48 (24天前)
来源:https://thesephist.com/posts/tools/

Python Hash Tables: Understanding Dictionaries
大家好，您是否想过Python字典如何如此快速和可靠？答案是它们建立在另一种技术之上：哈希表。

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

哈希函数永久链接
在介绍哈希表及其Python实现之前，您必须了解什么是哈希函数及其工作方式。

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

哈希函数具有三个主要特征：

它们的计算速度很快：计算一条数据的哈希必须是一项快速的操作。
它们是确定性的：相同的字符串将始终产生相同的哈希值。
它们产生固定长度的值：无论您输入的是1个，10个字节还是1万个字节都没有关系，生成的哈希将始终具有固定的预定长度。
哈希函数中非常普遍的另一个特征是它们通常是单向函数：由于在函数中实现了自愿数据丢失，因此您可以从字符串中获取哈希，但无法从哈希中获取原始字符串。这不是每个哈希函数的强制性功能，但在必须加密保护它们时变得很重要。

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

如果您想自己尝试这些算法之一，只需将浏览器指向https://www.md5online.org，在文本框中插入任意长度的文本，然后单击crypt按钮并取回128位MD5哈希即可。

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

一个具体的例子是，当您尝试从Internet下载开源软件时。通常，您还会找到一个伴随文件，该文件是文件的签名。此签名只是原始文件的哈希，它非常有用，因为如果您自己计算原始文件的哈希，然后根据网站提供的签名进行检查，则可以确保下载的文件没有已被篡改。

散列的另一种常见用法是存储用户密码。您是否曾经问过自己为什么忘记网站密码并尝试恢复该密码时，该网站通常允许您选择另一个密码而不是将原来选择的密码还给您？答案是该网站不会存储您选择的整个密码，而只会存储其哈希值。

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

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
如果您想知道为什么这些哈希值似乎具有不同的长度，请记住Python hash()函数返回整数对象，在标准的64位Python 3解释器上，该对象始终以24个字节表示。

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

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

您可以通过对数字进行散列来注意到的另外两点有趣的事情是，十进制数字的哈希值与它们的值不同，负值的哈希值为负。但是，如果您尝试对与十进制值相同的数字进行哈希运算会怎样？答案是，您将获得相同的哈希，如以下示例所示：

>>> hash(0.1)
230584300921369408
>>> hash(230584300921369408)
230584300921369408
>>> hash(0.1) == hash(230584300921369408)
True
如您所见，整数230584300921369408的哈希值与number的哈希值相同0.1。这是完全正常的，如果您想起您先前了解的有关散列函数的知识，因为如果您可以对任何数字或任何具有固定长度值的字符串进行散列，因为您不能拥有由固定长度值表示的无限值，则意味着必须有重复的值。它们实际上存在，它们被称为碰撞。当两个对象具有相同的哈希值时，可以说它们发生冲突。

散列字符串与散列数值没有太大区别。启动您的Python解释器，然后尝试对字符串进行哈希处理：

>>> hash("Bad Behaviour")
7164800052134507161
如您所见，字符串是可散列的，并且也产生数字值，但是如果您尝试运行此命令，则可能会发现Python解释器未返回与上面示例相同的结果。这是因为在Python开始字符串值3.3和字节对象是咸与哈希处理前的随机值。这意味着该字符串的值被修改为一个随机值，该值在您的解释器每次启动时都会在散列之前更改。如果要覆盖此行为，可以PYTHONHASHSEED在启动解释器之前将环境变量设置为大于零的整数值。

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

通过使用彩虹表，攻击者可能无法获取数据库中的每个密码，但仍然能够窃取其中的大部分密码。为了防止这种攻击，一个好主意是盐散列他们，这是计算散列之前修改了随机值密码前的密码。

从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__()在自定义类中实现一个方法来修改此行为。

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

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

哈希表通常是通过创建可变数量的存储区来实现的，这些存储区将包含您的数据，并通过对它们的键进行哈希处理来索引此数据。密钥的哈希值将确定要用于该特定数据段的正确存储桶。

在下面的示例中，您可以在Python中找到基本哈希表的实现。这只是一个实现，可以使您了解哈希表如何工作，因为您将在稍后知道，在Python中，无需创建哈希表的自定义实现，因为它们被实现为字典。让我们看看这个实现是如何工作的：

```python linenums =” 1”导入pprint

类Hashtable：def init（自我，元素）：self.bucket_size = len（elements）self.buckets = [[] for range in i（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

如果名称 ==“ 主要 ”：首都= [（'法国'，'巴黎'），（'美国'，'华盛顿特区'），（'意大利'，'罗马'），（'加拿大'，'渥太华'）] hashtable = Hashtable（资本）print（hashtable）print（f”意大利的首都是{hashtable.get_value（'Italy'）}”）

Look at the `for` loop starting at line 9. For each element of the hashtable this code calculate the hash of the key (line 10), it calculate the position of the element in the bucket depending on the hash (line 11) and add a tuple in the bucket (line 12).

Try to run the example above after setting the environment varible `PYTHONHASHSEED` to the value `46` and you will get the the following output, where two buckets are empty and two other buckets contains two key-value pairs each:

```console
[[('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”类哈希表：def init（self，elements）：self.bucket_size = len（elements）* 2 self.buckets = [[]用于范围内的i（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()函数开始，您必须使用默认值初始化存储桶，如果已经使用了您需要使用的存储桶，则继续寻找空存储桶：

```python linenums =” 8” def _assign_buckets（self，elements）：self.buckets = [无] * 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)) ```
如您所见，在第9行中，所有存储区都None在分配之前设置为默认值，在第15行中，while循环继续寻找空存储区来存储数据。

由于存储桶的分配已更改，因此检索过程也应更改，因为在此get_value()方法中，您现在需要检查密钥的值以确保找到的数据是您要查找的数据：

```python linenums =“ 21” def get_value（self，input_key）：hashed_value = hash（input_key）索引= hashed_value％self.bucket_size而self.buckets [index]不为None：key，value = self.buckets [index ]，如果键==输入键：返回值索引=（索引+ 1）％self.bucket_size

During the lookup process, in the  `get_value()` method at line 24 you use the `None` value to check when you need to stop looking for a key and in line 26 you check the key of the data to be sure that you are returning the correct value.

Running the example above, the key for `Italy` collided with a previously inserted element (`France`) and for this reason has been relocated to the first free bucket available. However, the search for `Italy` worked as expected:

```console
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}
要更新现有键的值，只需为先前插入的键分配一个不同的值。

请注意，由于字典是建立在哈希表的顶部，您可以仅当它的关键是插入一个元素哈希的。如果元素的键不可哈希（例如列表），则解释器将引发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中实现，但Guido在Python 3.7中已正式认可它）。

尝试创建一个空的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开始，值存储在不同的数据结构中，而字典仅包含指向实际值存储位置的指针。而且，当您创建一个空字典时，它会开始创建一个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
如您所见，在您插入第六和第十一元素之后，字典就变大了，但是为什么呢？因为要使我们的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个存储桶保留空间，回到初始状态。

结论固定链接
在本文中，您了解了什么是哈希表以及如何在Python中实现它们。

2 条回复

1#
回复此人
凯撒 | 2020-08-23 18-47

heheh

编辑

登录后才能参与评论