Python 中的哈希表
哈希表
哈希表（Hash Table）是一种旨在实现快速操作的数据结构。
人们有时会选择使用哈希表而非数组或链表，原因在于，即使处理大量数据，哈希表也能非常快速地完成数据的搜索、添加和删除操作。
在链表中，查找名为 "Bob" 的人需要耗费时间，因为我们必须从一个节点遍历到下一个节点，逐个检查每个节点，直到找到包含 "Bob" 的节点。
如果已知索引，在列表/数组中查找“Bob”可能会很快，但当我们只知道名字 "Bob" 时，就需要逐个比较元素，这会耗费时间。
然而，在哈希表中，查找 "Bob" 的速度非常快，因为有一种方法可以直接定位到 "Bob" 的存储位置，这种方法就是使用哈希函数。
从零开始构建哈希表
为了理解哈希表是什么，让我们尝试从零开始构建一个，用于存储唯一的名字。
我们将分五个步骤构建哈希表：
- 创建一个空列表（也可以是字典或集合）。
- 创建一个哈希函数。
- 使用哈希函数插入元素。
- 使用哈希函数查找元素。
- 处理冲突。
第一步：创建一个空列表
为了简单起见，让我们创建一个包含 10 个空元素的列表。
my_list = [None, None, None, None, None, None, None, None, None, None]
在哈希表中，这些元素中的每一个都称为一个桶（bucket）。
第二步：创建一个哈希函数
现在，我们来看看与哈希表交互的特殊方式。
我们希望将名字直接存储到数组中的正确位置，这时哈希函数就派上用场了。
哈希函数可以通过多种方式创建，这取决于哈希表的创建者。一种常见的方法是找到一种方法，将值转换为一个数字，该数字等于哈希表的索引号之一，在本例中是 0 到 9 之间的数字。
在我们的示例中，我们将使用每个字符的 Unicode 码点，将它们相加，然后进行模 10 运算，以得到 0 到 9 之间的索引号。
实例
创建一个哈希函数，该函数将每个字符的 Unicode 码点相加，并返回一个 0 到 9 之间的数字：
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
print("'Bob' has hash code:", hash_function('Bob'))
字符 B 的 Unicode 码点是 66，o 是 111，b 是 98。将它们相加得到 275。275 模 10 的结果是 5，因此 "Bob" 应该存储在索引 5 处。
哈希函数返回的数字称为哈希码（hash code）。
Unicode 码点：我们计算机中的所有内容都以数字形式存储，Unicode 码点是每个字符独有的数字。例如，字符 A 的 Unicode 码点是 65。
有关字符如何表示为数字的更多信息，请参阅此页面。
模运算：模运算将一个数除以另一个数，并给出余数。例如，7 % 3 将给出余数 1。（将 7 个苹果分给 3 个人，意味着每个人得到 2 个苹果，还剩下 1 个苹果。）
在 Python 和大多数编程语言中，模运算符写作 %。
第三步：插入元素
根据我们的哈希函数，"Bob" 应该存储在索引 5 处。
让我们创建一个函数，用于向哈希表中添加项：
实例
def add(name):
index = hash_function(name)
my_list[index] = name
add('Bob')
print(my_list)
在索引 5 处存储“Bob”后，我们的数组现在如下所示：
my_list = [None, None, None, None, None, 'Bob', None, None, None, None]
我们可以使用相同的函数来存储 "Pete"、"Jones"、"Lisa" 和 "Siri"。
实例
add('Pete')
add('Jones')
add('Lisa')
add('Siri')
print(my_list)
使用哈希函数将这些名字存储在正确的位置后，我们的数组如下所示：
实例
my_list = [None, 'Jones', None, 'Lisa', None, 'Bob', None, 'Siri', 'Pete', None]
第四步：查找名字
现在，我们已经有了一个非常基础的哈希表，让我们看看如何从中查找一个名字。
要在哈希表中查找 "Pete"，我们将名字 "Pete" 传递给哈希函数。哈希函数返回 8，这意味着 "Pete" 存储在索引 8 处。
实例
def contains(name):
index = hash_function(name)
return my_list[index] == name
print("'Pete' is in the Hash Table:", contains('Pete'))
因为我们不需要逐个检查元素来确定 "Pete" 是否在其中，我们可以直接使用哈希函数跳转到正确的元素！
第五步：处理冲突
让我们也将 "Stuart" 添加到我们的哈希表中。
我们将 "Stuart" 传递给哈希函数，它返回 3，这意味着 "Stuart" 应该存储在索引 3 处。
尝试将 "Stuart" 存储在索引 3 处时，会出现所谓的冲突，因为 "Lisa" 已经存储在索引 3 处。
为了解决冲突，我们可以在同一个桶中为更多元素腾出空间。以这种方式解决冲突问题称为链地址法（chaining），即在同一个桶中为更多元素提供空间。
首先，创建一个与原始列表大小相同但桶为空的新列表：
my_list = [ [], [], [], [], [], [], [], [], [], [] ]
重写 add() 函数，并添加与之前相同的名字：
实例
def add(name):
index = hash_function(name)
my_list[index].append(name)
add('Bob')
add('Pete')
add('Jones')
add('Lisa')
add('Siri')
add('Stuart')
print(my_list)
在将每个桶实现为列表后，"Stuart" 也可以存储在索引 3 处，我们的哈希集合现在如下所示：
结果
my_list = [ [None], ['Jones'], [None], ['Lisa', 'Stuart'], [None], ['Bob'], [None], ['Siri'], ['Pete'], [None] ]
现在查找 "Stuart" 需要稍微多一点时间，因为我们还会在同一个桶中找到 "Lisa"，但仍然比搜索整个哈希表快得多。
哈希表的用途
哈希表非常适合：
- 检查某物是否在集合中（比如在图书馆中查找一本书）。
- 存储唯一项并快速查找它们（比如存储电话号码）。
- 将值与键关联起来（比如将名字与电话号码关联起来）。
哈希表之所以非常适合这些用途，最重要的原因是与数组和链表相比，哈希表的速度非常快，尤其是对于大数据集而言。数组和链表的搜索和删除操作的时间复杂度为 O(n)，而哈希表的平均时间复杂度仅为 O(1)。
哈希表总结
哈希表元素存储在称为桶的存储容器中。
哈希函数使用元素的键来生成哈希码。
哈希码指示元素属于哪个桶，因此我们可以直接定位到该哈希表元素：对其进行修改、删除或检查其是否存在。
当两个哈希表元素具有相同的哈希码时，就会发生冲突，因为这意味着它们属于同一个桶。
冲突可以通过链地址法解决，即使用列表来允许同一个桶中有多个元素。