Python哈希表：了解字典

大家好，你们有没有想过Python字典怎么会这么快、这么可靠？答案是它们建立在另一种技术之上：哈希表。

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

在介绍哈希表及其Python实现之前，您必须了解什么是哈希函数以及它是如何工作的。

散列函数是可以将任意长度的数据映射到固定长度值(称为散列)的函数。

它们的计算速度很快：计算一段数据的散列必须是一个快速的操作。

它们产生固定长度的值：不管您的输入是1字节、10字节还是10,000字节，结果散列将始终是固定的、预定的长度。

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

如果你想自己尝试这些算法中的一个，只需将你的浏览器指向https://www.md5online.org，，在文本框中插入任意长度的文本，点击加密按钮，就可以找回你的128bitMD5hash。

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

一个具体的例子是当你试图从互联网上下载开源软件时。通常，您还会找到一个配套文件，它是文件的签名。这个签名只是原始文件的散列，它非常有用，因为如果您自己计算原始文件的散列，并将其与网站提供的签名进行核对，您可以确保下载的文件没有被篡改。

散列的另一个常见用途是存储用户密码。你有没有问过自己，为什么当你忘记一个网站的密码并试图找回它时，该网站通常会让你选择另一个密码，而不是把你选择的原始密码还给你？答案是，网站不会存储您选择的整个密码，而只存储其散列。

这样做是出于安全原因，因为如果某个黑客获得了访问站点数据库的权限，他们将不能知道您的密码，而只能知道您的密码的散列，而且由于散列函数通常是单向函数，您可以肯定他们永远无法从散列开始返回您的密码。

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

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

现在，尝试启动Python解释器并使用一下hash()函数。在第一个实验中，尝试散列一些数值：

如果您想知道为什么这些散列看起来长度不同，请记住Python hash()函数返回整数对象，在标准的64位Python3解释器上，这些对象总是用24字节表示。

如您所见，缺省情况下，整数值的哈希值就是值本身。请注意，无论您散列的值的类型是什么，这都会起作用，因此整数1和浮点数1.0具有相同的散列：1。

这有什么特别的吗？这说明了您在前面学到的东西，即哈希函数通常是单向函数：如果两个不同的对象可能具有相同的哈希，则不可能从哈希开始并返回到原始对象来执行相反的过程。在这种情况下，有关原始散列对象的类型的信息已丢失。

通过对数字进行散列，您可以注意到另一件有趣的事情，那就是十进制数的散列与它们的值不同，负值的散列也是负的。但是，如果您尝试散列得到的十进制值相同的数字，会发生什么情况呢？答案是您将获得相同的散列，如下例所示：

如您所见，整数230584300921369408的散列与数字0.1的散列相同。如果你想一想你之前学到的哈希函数，这是非常正常的，因为如果你可以对任何数字或任何字符串进行散列，得到一个固定长度的值，因为你不能有一个固定长度的值来表示无限的值，那就意味着一定有重复的值。它们实际上是存在的，它们被称为碰撞。当两个对象具有相同的散列时，就说它们发生了冲突。

对字符串进行散列与对数值进行散列没有太大区别。启动Python解释器并尝试散列一个字符串：

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

如您所料，这是一项安全功能。前面您了解到，网站通常存储您的密码的散列，而不是密码本身，以防止对网站数据库的攻击，从而窃取所有网站密码。如果网站只存储计算出来的散列，攻击者很容易知道原始密码是什么。他们只需要得到一个大的常用密码列表(网络上到处都是这样的列表)，然后计算相应的散列，就可以得到通常所说的彩虹表。

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

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

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

因此，在这一点上，您可能想知道是否有任何Python类型是Hasable的，这个问题的答案是否定的，默认情况下，在Python中只有不可变的类型才是Hasable的。如果您使用的是不可变的容器(比如元组)，那么内容也应该是不可变的，这样才是可哈希的。

尝试在Python中获取不可缓存类型的散列时，将从解释器获得TypeError，如下例所示：

>；>；>；散列(["；R"；，"；e"；，"；a"；，"；l"；，"；P"；，"；y"；，"；t"；，"；h"；，"；o"；，"；n"；；])回溯(最近一次调用)：文件"；<；标准输入&>"；，第1行，<；模块>；类型错误：不可散列的类型：'；列表'；

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

>；>；>；class car()：...。速度=0...。方向=0...。损坏=0...>；>；>；First_CAR=CAR()>；>；>；Second_CAR=CAR()>；>；>；哈希(First_CAR)274643597>；>；哈希(Second_CAR)274643604。

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

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

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

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

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

类哈希表：def init(self，element)：self.bucket_size=len(Element)self.bucket=[[]for i in range(self.bucket_size)]self._assign_bucket(Element)。

Def_assign_bucket(self，element)：对于key，元素中的值：HASHED_VALUE=HASH(KEY)index=HASHED_VALUE%self.bucket_size sel.bucket[index].append((key，value))def get_value(self，input_key)：HASHED_VALUE=HASH(INPUT_KEY)index=HASHED_VALUE%self.bucket_size bucket=self.bucket[index]对于key，存储桶中的值：if key==input_key：return(Value)return Nonedef__str__(Self)：return pprint.pformat(self.bucket)#这里使用pformat返回对象的可打印表示形式。

If Name==“Main”：Capitals=[(‘法国’，‘巴黎’)，(‘美国’，‘华盛顿特区’)，(‘意大利’，‘罗马’)，(‘加拿大’，‘渥太华’)]哈希表=意大利的Hashtable(capitals)print(hashtable)print(f”The首都是{hashtable.get_value(‘意大利’)}“)。

查看从第9行开始的`for`循环。对于哈希表的每个元素，此代码计算键的散列(第10行)，它根据散列计算元素在桶中的位置(第11行)，并在桶中添加一个元组(第12行)。尝试在将环境变量`PYTHONHASHSEED`设置为值`46`之后运行上面的示例，您将得到以下输出，其中两个桶为空，另外两个桶包含两个键。)，('；加拿大'；，'；渥太华'；)]，[('；法国#39；，'；巴黎#39；)，('；意大利#39；，'；罗马#39；)]意大利的首都是罗马

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

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

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

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

此外，您将处理的存储桶数量增加得越多，浪费的空间就越多。要测试这一点，只需使用两倍于输入列表长度的存储桶数量更改上一个示例的存储桶大小即可：

``python hl_ines=“3”类哈希表：def init(self，element)：self.bucket_size=len(Element)*2 self.bucket=[[]for i in range(self.bucket_size)]sel._assign_bucket(Element)。

运行这个示例，我最终得到了更好的输入数据分布，但是我有一个冲突和五个未使用的存储桶：``console[[]，[(('；Canada&39；，'；Ottawa'；)]，[('；United States'；，'；Washington D.C.'；)，('；意大利&39；，'；罗马&#)。)，[(('；France&39；，'；Paris；)]意大利的首都是罗马。

如您所见，两个散列发生冲突，并已插入到同一存储桶中。

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

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

在开放寻址策略中，如果您应该使用的存储桶很忙，您只需不断搜索要使用的新存储桶即可。要实现此解决方案，您需要对如何将存储桶分配给新元素以及如何检索键值进行一些更改。从_Assign_Buckets()函数开始，您必须使用默认值初始化存储桶，如果应该使用的存储桶已被占用，则继续查找空存储桶：

对于KEY，元素中的值：HASHED_VALUE=HASH(KEY)index=HASHED_VALUE%self.bucket_size而self.bucket[index]不是None：print(f"；key{key}与{self.bucket[index]}"；)index=(index+1)%self.bucket_size self.bucket[index]=((key，value))``。

如您所见，在第9行中，所有存储桶在赋值之前都被设置为默认的NONE值，而在第15行中，While循环继续寻找空的存储桶来存储数据。

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

``python linenum=“21”def get_value(self，input_key)：HASHED_VALUE=HASH(INPUT_KEY)INDEX=HASHED_VALUE%self.bucket_size，而self.bucket[index]不是NONE：key，value=self.bucket[index]if key==input_key：返回值index=(index+1)%self.bucket_size。

在查找过程中，在第24行的`get_value()`方法中，您使用`None`值检查何时需要停止查找键，并在第26行检查数据的键，以确保返回的值正确。运行上面的示例时，`Italy`的键与之前插入的元素(`France`)冲突，因此已重新定位到第一个可用的空闲存储桶中。不过，对“意大利”的搜索结果与预期一致：``安慰关键的意大利与('；法国，#39；巴黎)[无，无，(#39；加拿大，#39；渥太华)，无，(#39；法国，#39；巴黎；)，('；意大利，'；，'；罗马；)。华盛顿特区意大利首都是罗马

开放寻址策略的主要问题是，如果还必须处理表中元素的删除，则需要执行逻辑删除而不是物理删除，因为如果删除冲突期间占用存储桶的值，将永远找不到其他冲突的元素。

在我们前面的示例中，意大利与先前插入的元素(法国)发生冲突，因此它已被重新定位到下一个存储桶，因此删除法国元素将使意大利无法访问，因为它不占用其自然目的地存储桶，而该目标存储桶对解释器来说似乎是空的。

因此，当使用开放寻址策略时，要删除一个元素，您必须用一个虚拟值替换它的存储桶，这向解释器表明，对于新的插入，它必须被认为是删除的，但是为了检索的目的，它必须被占用。

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

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

国际象棋玩家={..."；Carlsen"；：2863，..."；Caruana"；：2835，..."；Ding"；：2791，..."；尼泊尔国际象棋"；：2784，..."；Vachier-Lagrave"；：2778，...}。

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

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

如果您尝试访问不存在的元素，Python解释器会抛出一个关键错误异常：

要迭代整个字典，可以使用.Items()方法，该方法返回元组中所有键-值对的可迭代对象：

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

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

国际象棋玩家["；Grischuk"；]=2777；>；>；>；国际象棋玩家{'；Carlsen'；：2863，'；Caruana'；：2835，'；丁'；：2791，&39；尼波姆尼亚奇'；：2784，&39；瓦契尔-。

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

请注意，因为字典是建立在哈希表之上的，所以您只能在元素的键是Hasable的情况下才能插入该元素。如果元素的键不可哈希(例如，类似于列表)，则解释器将抛出TypeError异常：

>；>；>；my_list=["；Giri&34；，"；]CHESS_Player[My_List]=2764Traceback(最近一次调用)：file"；<；stdin>；"；，行1，在<；模块>；类型错误：无法缓存的类型：'；list'；

要删除元素，需要使用del语句，指定要删除的键：

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

现在您知道字典是Python哈希表，但是您可能想知道实现是如何在幕后工作的，所以在本章中，我将尝试给您一些关于Python哈希表的实际实现的信息。

请记住，我在这里提供的信息是基于Python的最新版本，因为在Python3.6版本中，字典发生了很大变化，现在更小、更快，甚至更强大，因为它们现在是按插入顺序排序的(插入顺序保证。

.