原文：
zh.annas-archive.org/md5/97bc15629f1b51a0671040c56db61b92译者：飞龙
第十章：哈希和符号表
我们之前看过列表，其中项目按顺序存储并通过索引号访问。索引号对计算机来说很有效。它们是整数，因此它们快速且易于操作。但是，它们并不总是对我们很有效。例如，如果我们有一个地址簿条目，索引号为 56，那个数字并没有告诉我们太多。没有什么可以将特定联系人与编号 56 联系起来。它只是列表中的下一个可用位置。
在本章中，我们将研究一个类似的结构：字典。字典使用关键字而不是索引号。因此，如果该联系人被称为James，我们可能会使用关键字James来定位该联系人。也就是说，我们不再通过调用contacts [56]来访问联系人，而是使用contacts [“james”]。
字典通常是使用哈希表构建的。顾名思义，哈希表依赖于一个称为哈希的概念。这就是我们将开始讨论的地方。
在本章中，我们将涵盖以下主题：
- 哈希
- 哈希表
- 具有元素的不同函数
哈希
哈希是将任意大小的数据转换为固定大小的数据的概念。更具体地说，我们将使用这个概念将字符串（或可能是其他数据类型）转换为整数。这可能听起来比实际复杂，所以让我们看一个例子。我们想要对表达式 hello world 进行哈希，也就是说，我们想要得到一个数值，可以说代表这个字符串。
通过使用 ord() 函数，我们可以得到任何字符的序数值。例如，ord('f') 函数返回 102。要得到整个字符串的哈希值，我们可以简单地对字符串中每个字符的序数值求和：
>>> sum(map(ord, 'hello world')) 1116
这很好地运行了。但是，请注意我们可以改变字符串中字符的顺序并得到相同的哈希值：
>>> sum(map(ord, 'world hello')) 1116
字符的序数值的总和对于字符串 gello xorld 也是相同的，因为 g 的序数值比 h 小 1，x 的序数值比 w 大 1，因此：
>>> sum(map(ord, 'gello xorld')) 1116
完美的哈希函数
完美的哈希函数是指每个字符串（目前我们只讨论字符串）都保证是唯一的。在实践中，哈希函数通常需要非常快，因此通常不可能创建一个能给每个字符串一个唯一哈希值的函数。相反，我们要接受有时会发生碰撞（两个或更多个字符串具有相同的哈希值），当发生这种情况时，我们需要想出一种解决策略。
与此同时，我们至少可以想出一种避免一些碰撞的方法。例如，我们可以添加一个乘数，使得每个字符的哈希值成为乘数值乘以字符的序数值。随着我们在字符串中的进展，乘数会增加。这在下面的函数中显示：
def myhash(s): mult = 1 hv = 0 for ch in s: hv += mult * ord(ch) mult += 1 return hv
我们可以在先前使用的字符串上测试这个函数：
for item in ('hello world', 'world hello', 'gello xorld'): print("{}: {}".format(item, myhash(item)))
运行程序，我们得到以下输出：
% python hashtest.py hello world: 6736 world hello: 6616 gello xorld: 6742
请注意，最后一行是将第 2 行和第 3 行的值相乘得到的，例如 104 x 1 等于 104。
这次我们得到了不同的字符串的哈希值。当然，这并不意味着我们有一个完美的哈希。让我们尝试字符串 ad 和 ga：
% python hashtest.py ad: 297 ga: 297
在这里，我们仍然得到了两个不同字符串相同的哈希值。正如我们之前所说的，这并不一定是一个问题，但我们需要想出一种解决碰撞的策略。我们很快将会看到这一点，但首先我们将研究哈希表的实现。
哈希表
哈希表是一种列表形式，其中元素是通过关键字而不是索引号访问的。至少，这是客户端代码将看到的方式。在内部，它将使用我们稍微修改过的哈希函数的版本，以便找到应该插入元素的索引位置。这给了我们快速查找，因为我们使用的是与键的哈希值对应的索引号。
我们首先创建一个类来保存哈希表的项目。这些项目需要有一个键和一个值，因为我们的哈希表是一个键-值存储：
class HashItem: def __init__(self, key, value): self.key = key self.value = value
这给了我们一种非常简单的存储项目的方式。接下来，我们开始着手处理哈希表类本身。和往常一样，我们从构造函数开始：
class HashTable: def __init__(self): self.size = 256 self.slots = [None for i in range(self.size)] self.count = 0
哈希表使用标准的 Python 列表来存储其元素。我们也可以使用之前开发的链表，但现在我们的重点是理解哈希表，所以我们将使用我们手头上的东西。
我们将哈希表的大小设置为 256 个元素。稍后，我们将研究如何在开始填充哈希表时扩展表的策略。现在，我们初始化一个包含 256 个元素的列表。这些元素通常被称为槽或桶。最后，我们添加一个计数器，用于记录实际哈希表元素的数量：
重要的是要注意表的大小和计数之间的区别。表的大小是指表中槽的总数（已使用或未使用）。表的计数，另一方面，只是指填充的槽的数量，或者换句话说，我们已经添加到表中的实际键-值对的数量。
现在，我们将把我们的哈希函数添加到表中。它将类似于我们在哈希函数部分演变的内容，但有一个小小的不同：我们需要确保我们的哈希函数返回一个介于 1 和 256 之间的值（表的大小）。一个很好的方法是返回哈希除以表的大小的余数，因为余数总是一个介于 0 和 255 之间的整数值。
哈希函数只是用于类内部的，我们在名称前面加下划线(_)来表示这一点。这是 Python 中用于表示某些内容是内部使用的常规约定：
def _hash(self, key): mult = 1 hv = 0 for ch in key: hv += mult * ord(ch) mult += 1 return hv % self.size
目前，我们将假设键是字符串。我们将讨论如何稍后使用非字符串键。现在，只需记住_hash()函数将生成字符串的哈希值。
放置元素
我们使用put()函数添加元素到哈希表，并使用get()函数检索。首先，我们将看一下put()函数的实现。我们首先将键和值嵌入到HashItem类中，并计算键的哈希：
def put(self, key, value): item = HashItem(key, value) h = self._hash(key)
现在我们需要找到一个空槽。我们从与键的哈希值对应的槽开始。如果该槽为空，我们就在那里插入我们的项目。
然而，如果槽不为空并且项目的键与我们当前的键不同，那么我们就会发生冲突。这就是我们需要想办法处理冲突的地方。我们将通过在先前的哈希值上加一，并取除以哈希表的大小的余数来解决这个问题。这是一种线性解决冲突的方法，非常简单：
while self.slots[h] is not None: if self.slots[h].key is key: break h = (h + 1) % self.size
我们已经找到了插入点。如果这是一个新元素（即先前包含None），那么我们将计数增加一。最后，我们将项目插入到所需位置的列表中：
if self.slots[h] is None: self.count += 1 self.slots[h] = item
获取元素
get()方法的实现应该返回与键对应的值。我们还必须决定在表中不存在键时该怎么办。我们首先计算键的哈希：
def get(self, key): h = self._hash(key)
现在，我们只需开始在列表中寻找具有我们正在搜索的键的元素，从具有传入键的哈希值的元素开始。如果当前元素不是正确的元素，那么就像在put()方法中一样，我们在先前的哈希值上加一，并取除以列表大小的余数。这就成为我们的新索引。如果我们找到包含None的元素，我们停止寻找。如果我们找到我们的键，我们返回值：
while self.slots[h] is not None: if self.slots[h].key is key: return self.slots[h].value h = (h+ 1) % self.size
最后，我们决定如果在表中找不到键要做什么。在这里，我们将选择返回None。另一个好的选择可能是引发一个异常：
return None
测试哈希表
为了测试我们的哈希表，我们创建一个HashTable，把一些元素放进去，然后尝试检索这些元素。我们还将尝试get()一个不存在的键。还记得我们的哈希函数返回相同的哈希值的两个字符串 ad 和 ga 吗？为了确保，我们也把它们放进去，看看冲突是如何正确解决的：
ht = HashTable() ht.put("good", "eggs") ht.put("better", "ham") ht.put("best", "spam") ht.put("ad", "do not") ht.put("ga", "collide") for key in ("good", "better", "best", "worst", "ad", "ga"): v = ht.get(key) print(v)
运行这个代码返回以下结果：
% python hashtable.py eggs ham spam None do not collide
如你所见，查找键 worst 返回None，因为该键不存在。键ad和ga也返回它们对应的值，显示它们之间的冲突是如何处理的。
使用哈希表的[]
然而，使用put()和get()方法看起来并不是很好。我们希望能够将我们的哈希表视为一个列表，也就是说，我们希望能够使用ht["good"]而不是ht.get("good")。这可以很容易地通过特殊方法__setitem__()和__getitem__()来实现：
def __setitem__(self, key, value): self.put(key, value) def __getitem__(self, key): return self.get(key)
我们的测试代码现在可以这样写：
ht = HashTable() ht["good"] = "eggs" ht["better"] = "ham" ht["best"] = "spam" ht["ad"] = "do not" ht["ga"] = "collide" for key in ("good", "better", "best", "worst", "ad", "ga"): v = ht[key] print(v) print("The number of elements is: {}".format(ht.count))
注意，我们还打印了哈希表中的元素数量。这对我们接下来的讨论很有用。
非字符串键
在大多数情况下，只使用字符串作为键更有意义。但是，如果必要，你可以使用任何其他的 Python 类型。如果你创建了自己的类来用作键，你可能需要重写该类的特殊__hash__()函数，以便获得可靠的哈希值。
注意，你仍然需要计算哈希值的模运算和哈希表的大小，以获得插槽。这个计算应该发生在哈希表中，而不是在键类中，因为表知道自己的大小（键类不应该知道它所属的表的任何信息）。
扩大哈希表
在我们的示例中，哈希表的大小设置为 256。显然，随着我们向列表中添加元素，我们开始填满空插槽。在某个时候，所有的插槽都将被填满，表也将被填满。为了避免这种情况，我们可以在表快要填满时扩大表。
为了做到这一点，我们比较大小和计数。记住size保存了插槽的总数，count保存了包含元素的插槽的数量？如果count等于size，那么我们已经填满了表。
哈希表的负载因子给了我们一个指示，表中有多大比例的可用插槽正在被使用。它的定义如下：
当负载因子接近 1 时，我们需要扩大表格。实际上，我们应该在它达到那里之前就这样做，以避免变得太慢。0.75 可能是一个很好的值，用来扩大表格。
下一个问题是要扩大表多少。一个策略是简单地将表的大小加倍。
开放寻址
我们在示例中使用的冲突解决机制，线性探测，是开放寻址策略的一个例子。线性探测非常简单，因为我们在探测之间使用固定的间隔。还有其他的开放寻址策略，但它们都共享一个想法，即有一个插槽数组。当我们想要插入一个键时，我们会检查插槽是否已经有项目。如果有，我们会寻找下一个可用的插槽。
如果我们有一个包含 256 个插槽的哈希表，那么 256 就是哈希中最大的元素数量。此外，随着负载因子的增加，找到新元素的插入点将需要更长的时间。
由于这些限制，我们可能更喜欢使用不同的策略来解决冲突，例如链接。
链接
链接是一种解决冲突并避免哈希表中元素数量限制的策略。在链接中，哈希表中的插槽初始化为空列表：
当插入元素时，它将被追加到与该元素的哈希值对应的列表中。也就是说，如果您有两个具有相同哈希值 1167 的元素，这两个元素都将被添加到哈希表的插槽 1167 中存在的列表中：
上图显示了具有哈希值 51 的条目列表。
然后通过允许多个元素具有相同的哈希值来避免冲突。它还避免了插入的问题，因为负载因子增加时，我们不必寻找插槽。此外，哈希表可以容纳比可用插槽数量更多的值，因为每个插槽都包含一个可以增长的列表。
当然，如果特定插槽有很多项，搜索它们可能会变得非常缓慢，因为我们必须通过列表进行线性搜索，直到找到具有所需键的元素。这可能会减慢检索速度，这并不好，因为哈希表的目的是高效的：
上图演示了通过列表项进行线性搜索，直到找到匹配项。
我们可以在表插槽中使用另一个允许快速搜索的结构，而不是使用列表。我们已经看过二叉搜索树（BSTs）。我们可以简单地在每个插槽中放置一个（最初为空的）BST：
插槽 51 包含我们搜索键的 BST。但我们仍然可能会遇到一个问题：根据将项添加到 BST 的顺序，我们可能会得到一个搜索树，其效率与列表一样低。也就是说，树中的每个节点都只有一个子节点。为了避免这种情况，我们需要确保我们的 BST 是自平衡的。
符号表
符号表被编译器和解释器用来跟踪已声明的符号及其相关信息。符号表通常使用哈希表构建，因为高效地检索表中的符号很重要。
让我们看一个例子。假设我们有以下 Python 代码：
name = "Joe" age = 27
这里有两个符号，名称和年龄。它们属于一个命名空间，可以是__main__，但如果您将其放在那里，它也可以是模块的名称。每个符号都有一个值；名称的值为Joe，年龄的值为27。符号表允许编译器或解释器查找这些值。符号名称和年龄成为哈希表中的键。与之关联的所有其他信息，例如值，都成为符号表条目的一部分。
不仅变量是符号，函数和类也是。它们都将被添加到我们的符号表中，因此当需要访问它们中的任何一个时，它们都可以从符号表中访问：
在 Python 中，每个加载的模块都有自己的符号表。符号表被赋予该模块的名称。这样，模块就充当了命名空间。我们可以有多个名为年龄的符号，只要它们存在于不同的符号表中。要访问其中任何一个，我们通过适当的符号表进行访问：
总结
在本章中，我们已经研究了哈希表。我们研究了如何编写哈希函数将字符串数据转换为整数数据。然后我们看了如何使用哈希键快速高效地查找对应于键的值。
我们还注意到哈希函数并不完美，可能会导致多个字符串具有相同的哈希值。这促使我们研究了冲突解决策略。
我们研究了如何扩展哈希表，以及如何查看表的负载因子，以确定何时扩展哈希表。
在本章的最后一节中，我们学习了符号表，通常使用哈希表构建。符号表允许编译器或解释器查找已定义的符号（变量、函数、类等）并检索有关其所有信息。
在下一章中，我们将讨论图和其他算法。
第十一章：图和其他算法
在本章中，我们将讨论图。 这是来自称为图论的数学分支的概念。
图用于解决许多计算问题。 它们的结构比我们所看到的其他数据结构要少得多，遍历等操作可能更加不寻常，我们将会看到。
在本章结束时，您应该能够做到以下几点：
- 了解图是什么
- 了解图的类型及其组成部分
- 知道如何表示图并遍历它
- 对优先队列有一个基本的概念
- 能够实现优先队列
- 能够确定列表中第 i 个最小元素
图
图是一组顶点和边，它们之间形成连接。 在更正式的方法中，图 G 是顶点集 V 和边集 E 的有序对，以G = (V, E)的形式给出。
这里给出了一个图的示例：
现在让我们来看一些图的定义：
- 节点或顶点：图中通常由一个点表示。 顶点或节点是 A、B、C、D 和 E。
- 边：这是两个顶点之间的连接。 连接 A 和 B 的线就是边的一个例子。
- 环：当来自节点的边与自身相交时，该边形成一个环。
- 顶点的度：这是与给定顶点相交的顶点数。 顶点 B 的度为
4。 - 邻接：这指的是节点与其邻居之间的连接。 节点 C 与节点 A 相邻，因为它们之间有一条边。
- 路径：一系列顶点，其中每对相邻的顶点都由一条边连接。
有向和无向图
图可以根据它们是无向的还是有向的进行分类。 无向图简单地将边表示为节点之间的线。 除了它们连接在一起这一事实之外，关于节点之间关系的其他信息都没有：
在有向图中，边除了连接节点外还提供方向。 也就是说，边将被绘制为带有箭头的线，箭头指示边连接两个节点的方向：
边的箭头确定了方向的流动。 在上图中，只能从A到B。 而不能从B到A。
加权图
加权图在边上添加了一些额外的信息。 这可以是指示某些内容的数值。 例如，假设以下图表表示从点A到点D的不同路径。 您可以直接从A到D，也可以选择通过B和C。 与每条边相关的是到达下一个节点所需的时间（以分钟为单位）：
也许旅程AD需要您骑自行车（或步行）。 B和C可能代表公交车站。 在B，您需要换乘另一辆公交车。 最后，CD可能是到达D的短途步行。
在这个例子中，AD和ABCD代表两条不同的路径。 路径只是两个节点之间穿过的边的序列。 沿着这些路径，您会发现总共需要40分钟的旅程AD，而旅程ABCD需要25分钟。 如果您唯一关心的是时间，即使需要换乘公交车，您也最好沿着ABCD行驶。
边可以是有向的，并且可能包含其他信息，例如所花费的时间或路径上关联的其他值，这表明了一些有趣的事情。在我们之前使用的数据结构中，我们绘制的线只是连接器。即使它们有箭头从一个节点指向另一个节点，也可以通过在节点类中使用next或previous、parent或child来表示。
对于图来说，将边视为对象与节点一样是有意义的。就像节点一样，边可以包含跟随特定路径所必需的额外信息。
图表示
图可以用两种主要形式表示。一种方法是使用邻接矩阵，另一种方法是使用邻接表。
我们将使用以下图来开发图的两种表示形式：
邻接表
可以使用简单的列表来表示图。列表的索引将表示图中的节点或顶点。在每个索引处，可以存储该顶点的相邻节点：
盒子中的数字代表顶点。索引0代表顶点A，其相邻节点为B和C。
使用列表进行表示相当受限，因为我们缺乏直接使用顶点标签的能力。因此，使用字典更合适。为了表示图中的图表，我们可以使用以下语句：
graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['E','A'] graph['C'] = ['A', 'B', 'E','F'] graph['E'] = ['B', 'C'] graph['F'] = ['C']
现在我们很容易确定顶点A有相邻顶点B和C。顶点 F 只有顶点C作为其邻居。
邻接矩阵
图可以使用邻接矩阵来表示的另一种方法。矩阵是一个二维数组。这里的想法是用 1 或 0 来表示两个顶点是否通过一条边连接。
给定邻接表，应该可以创建邻接矩阵。需要一个图的键的排序列表：
matrix_elements = sorted(graph.keys()) cols = rows = len(matrix_elements)
键的长度用于提供矩阵的维度，这些维度存储在cols和rows中。这些值在cols和rows中是相等的：
adjacency_matrix = [[0 for x in range(rows)] for y in range(cols)] edges_list = []
然后我们设置了一个cols乘以rows的数组，并用零填充它。edges_list变量将存储构成图中边的元组。例如，节点 A 和 B 之间的边将存储为(A, B)。
使用嵌套的 for 循环填充多维数组：
for key in matrix_elements: for neighbor in graph[key]: edges_list.append((key,neighbor))
顶点的邻居是通过graph[key]获得的。然后，结合neighbor使用edges_list中存储的元组。
迭代的输出如下：
>>> [('A', 'B'), ('A', 'C'), ('B', 'E'), ('B', 'A'), ('C', 'A'), ('C', 'B'), ('C', 'E'), ('C', 'F'), ('E', 'B'), ('E', 'C'), ('F', 'C')]
现在需要做的是通过使用 1 来填充我们的多维数组，以标记边的存在，使用行adjacency_matrix[index_of_first_vertex][index_of_second_vertex] = 1：
for edge in edges_list: index_of_first_vertex = matrix_elements.index(edge[0]) index_of_second_vertex = matrix_elements.index(edge[1]) adjacecy_matrix[index_of_first_vertex][index_of_second_vertex] = 1
matrix_elements数组的rows和cols从 A 到 E，索引从 0 到 5。for循环遍历我们的元组列表，并使用index方法获取要存储边的相应索引。
生成的邻接矩阵如下所示：
>>> [0, 1, 1, 0, 0] [1, 0, 0, 1, 0] [1, 1, 0, 1, 1] [0, 1, 1, 0, 0] [0, 0, 1, 0, 0]
在第 1 列和第 1 行，0 表示 A 和 A 之间没有边。在第 2 列和第 3 行，C 和 B 之间有一条边。
图遍历
由于图不一定具有有序结构，遍历图可能更加复杂。遍历通常涉及跟踪已经访问过的节点或顶点以及尚未访问过的节点或顶点。一个常见的策略是沿着一条路径走到死胡同，然后向上走，直到有一个可以选择的路径。我们也可以迭代地从一个节点移动到另一个节点，以遍历整个图或部分图。在下一节中，我们将讨论用于图遍历的广度优先搜索和深度优先搜索算法。
广度优先搜索
广度优先搜索算法从一个节点开始，选择该节点或顶点作为其根节点，并访问相邻节点，然后探索图的下一级邻居。
考虑以下图表作为图：
该图是一个无向图的示例。我们继续使用这种类型的图来帮助解释，而不会太啰嗦。
图的邻接列表如下：
graph = dict() graph['A'] = ['B', 'G', 'D'] graph['B'] = ['A', 'F', 'E'] graph['C'] = ['F', 'H'] graph['D'] = ['F', 'A'] graph['E'] = ['B', 'G'] graph['F'] = ['B', 'D', 'C'] graph['G'] = ['A', 'E'] graph['H'] = ['C']
为了以广度优先的方式遍历这个图，我们将使用队列。算法创建一个列表来存储已访问的节点，随着遍历过程的进行。我们将从节点 A 开始遍历。
节点 A 被排队并添加到已访问节点的列表中。之后，我们使用while循环来实现对图的遍历。在while循环中，节点 A 被出队。它未访问的相邻节点 B、G 和 D 按字母顺序排序并排队。队列现在包含节点 B、D 和 G。这些节点也被添加到已访问节点的列表中。此时，我们开始while循环的另一个迭代，因为队列不为空，这也意味着我们并没有真正完成遍历。
节点 B 被出队。在它的相邻节点 A、F 和 E 中，节点 A 已经被访问。因此，我们只按字母顺序排队节点 E 和 F。然后将节点 E 和 F 添加到已访问节点的列表中。
此时，我们的队列中包含以下节点：D、G、E 和 F。已访问节点的列表包含 A、B、D、G、E、F。
节点 D 被出队，但是它的所有相邻节点都已经被访问过，所以我们只是出队它。队列前面的下一个节点是 G。我们出队节点 G，但是我们也发现它的所有相邻节点都已经被访问，因为它们在已访问节点的列表中。节点 G 也被出队。我们也出队节点 E，因为它的所有节点都已经被访问。现在队列中唯一的节点是节点 F。
节点 F 被出队，我们意识到它的相邻节点 B、D 和 C 中，只有节点 C 还没有被访问。然后我们将节点 C 排队并将其添加到已访问节点的列表中。节点 C 被出队。节点 C 有相邻节点 F 和 H，但 F 已经被访问，只剩下节点 H。节点 H 被排队并添加到已访问节点的列表中。
最后，while循环的最后一次迭代将导致节点 H 被出队。它唯一的相邻节点 C 已经被访问过。一旦队列完全为空，循环就会中断。
在图中遍历的输出是 A、B、D、G、E、F、C、H。
广度优先搜索的代码如下所示：
from collections import deque def breadth_first_search(graph, root): visited_vertices = list() graph_queue = deque([root]) visited_vertices.append(root) node = root while len(graph_queue) > 0: node = graph_queue.popleft() adj_nodes = graph[node] remaining_elements = set(adj_nodes).difference(set(visited_vertices)) if len(remaining_elements) > 0: for elem in sorted(remaining_elements): visited_vertices.append(elem) graph_queue.append(elem) return visited_vertices
当我们想要找出一组节点是否在已访问节点的列表中时，我们使用语句remaining_elements = set(adj_nodes).difference(set(visited_vertices))。这使用了集合对象的差异方法来找出在adj_nodes中但不在visited_vertices中的节点。
在最坏的情况下，每个顶点或节点和边都将被遍历，因此算法的时间复杂度是O(|V| + |E|)，其中|V|是顶点或节点的数量，而|E|是图中边的数量。
Python 入门指南（四）（2）https://developer.aliyun.com/article/1507401
