哈希算法

“散列”一词指的是使用散列函数从可变大小的输入创建固定大小输出的操作。此方法确定了项将在数据结构中存储的索引或位置。

散列数据结构的需求

互联网上的数据量每天都在呈指数级增长，这使得有效存储所有数据变得困难。即使这些数据量在日常编程中可能不大，也必须方便地保存、检索和处理。数组数据结构是用于此类功能的最流行的结构之一。

现在提出的问题是，如果已经存在数组，为什么还要创建新的数据结构？“效率”一词是解决这个问题的关键。虽然在数组中搜索至少需要 O(log n) 时间，但将其存储仅需要 O(1) 时间。尽管这个时间看起来微不足道，但对于大量数据来说，它确实会引起很多问题，导致数组数据结构失效。我们现在正在寻找一种数据结构，它可以在 O(1) 时间或常数时间内存储数据并进行搜索。散列数据结构就是这样开发的。由于散列数据结构的出现，数据现在可以轻松地以常数时间存储，并以常数时间检索。

散列中的组件

散列主要由三个部分组成

• 键（Key）： 键是提供给散列函数的任何文本或数字，散列函数是一种用于确定项在数据结构中的索引或位置的方法。
• 散列函数（Hash Function）： 散列函数接收一个键作为输入，并输出散列表中条目的索引。索引有时被称为散列索引。
• 散列表（Hash Table）： 散列表是一种数据结构，它使用一种称为散列函数的独特函数来映射键值。散列以关联方式将数据保存在数组中，为每个数据值提供一个唯一的索引。

散列如何实现？

假设我们要将一组字符串，如“ab”、“cd”和“efg”存储在一个表中。

我们不关心表中字符串的顺序；我们的主要目标是以 O(1) 的时间快速查找或更新表中包含的信息。因此，提供的字符串集可以作为键，字符串本身将作为字符串的值。但是，我们如何存储与键对应的值呢？

步骤 1： 散列值（用作数据结构中存储项的索引）是通过散列函数（数学公式）计算得出的。

步骤 2： 接下来，我们为所有字母字符赋予值

“a”= 1，

“b”= 2，依此类推。

步骤 3： 因此，通过将所有字符相加来计算字符串的数值

“ab”= 1 + 2 = 3，

“cd”= 3 + 4 = 7，

“efg”= 5 + 6 + 7 = 18

步骤 4： 假设我们有一个 7 列的表来存储这些字符串。在这种情况下，字符之和模表大小用作散列函数。通过使用 sum(string) mod 7，我们可以确定字符串在数组中的位置。

步骤 5： 因此，我们将存储

“ab”在 3 mod 7 = 3，

“cd”在 7 mod 7 = 0，和

“efg”在 18 mod 7 = 4。

通过上述方法，通过使用简单的散列函数来确定给定文本的位置，我们可以快速找到存储在特定位置的值。因此，使用散列将 (键, 值) 对的数据存储在表中似乎是个好主意。

散列函数是什么意思？

散列函数使用称为散列函数的数学公式来生成键和值之间的映射。散列值或散列是散列函数输出的名称。散列值通常比原始字符串短，它是原始字符集的表示。

散列函数类型：许多散列函数使用数字或字母键。此页面主要讨论几种散列函数

• 除法技术。
• 平方中间值技术。
• 使用折叠技术
• 乘法技术

此过程的步骤如下：选择一个一致的数 A 乘法方法，使得 0 ≤ A < 1。

什么是一个好的散列函数？

一个完美的散列函数会将每个项分配到一个唯一的槽，并被称为这样。问题在于，对于给定的一组随机项，没有系统的方法来创建完美的散列函数。如果我们知道这些项并且该集合永远不会改变，我们就可以创建一个完美的散列函数。幸运的是，即使散列函数不完美，我们仍然可以提高性能效率。通过增大散列表的大小，使其能够容纳所有可想象的值，我们可以创建一个完美的散列函数。因此，每个对象都会有一个特殊的位置。对于少数产品，这种策略是可行的，但在有许多潜在结果时是不可行的。

因此，我们可以创建自己的散列函数来做同样的事情，但在这样做时需要考虑一些因素。

一个好的散列函数需要具备以下特性

• 易于计算 - 键应均匀分布在表中（每个表位置对于每个键都同样可能），应减少冲突。
• 负载因子应较低（表中项的数量与表大小的比率）。

使用散列函数计算散列值很困难。

• O(n) 时间复杂度
• O(1) 空间复杂度

散列问题

如果我们以上述案例为例，所使用的散列函数是字母之和；但是，如果我们仔细查看散列函数，就会发现该散列函数会为不同的文本生成相同的散列结果。

例如，“ab”和“ba”具有相同的散列值，而字符串“cd”和“be”都具有相同的散列结果。这被称为冲突，它会导致搜索、插入、删除和值更新出现问题。

描述冲突

由于散列过程为大键生成小数字，因此两个键可能产生相同的结果。当新插入的键对应于现有已占用槽时，必须使用冲突处理技术来解决问题。

如何处理冲突？

主要有两种处理冲突的方法

• 链式寻址
• 开放寻址

1. 分离链接

目标是创建具有相同散列函数值的记录的链表，散列表的每个单元都可以指向该链表。虽然链式寻址很简单，但需要表外的额外内存。

示例：使用不同的链式寻址机制来解决冲突，在收到散列函数后，我们必须将某些条目插入散列表中。

让我们一步一步地解决上述问题

步骤 1： 使用指定的散列算法创建一个空的散列表，其潜在的散列值范围在 0 到 4 之间。

步骤 2： 现在单独添加每个键到散列表。使用散列函数 12%5=2 来确定要添加的第一个键（12）的存储桶编号 2。

步骤 3： 现在 22 是下一个键。由于 22%5=2，它将对应于存储桶编号 2。但是键 12 已经占用了存储桶 2。

步骤 4： 下一个键是 15。由于 15%5=0，它将映射到槽号 0。

步骤 5： 现在 25 是下一个键。它将具有存储桶编号 25%5=0。但是键 25 已经占用了存储桶 0。为了解决冲突，单独链式寻址技术将再次创建一个包含存储桶 0 的链表。

因此，在这种情况下，冲突分辨率方法是单独链式寻址方法。

2. 开放寻址

在开放寻址中，散列表本身包含所有条目。每个表条目都包含一个记录或 NIL。在查找元素时，我们逐个表槽地进行搜索，直到找到所需的元素，或者可以清楚地表明该元素不在表中。

a) 线性探测

在线性探测中，散列表从散列的初始点开始系统地检查。如果我们得到的站点已经被占用，我们就寻找另一个站点。

算法

• 计算散列键。即 key = data % size
• 检查，如果 hashTable[key] 为空，则直接将值存储在 hashTable[key] = data
• 如果散列索引已经有值，则使用 key = (key+1) % size 检查下一个索引
• 检查，如果下一个索引可用 hashTable[key]，则存储该值。否则尝试下一个索引。
• 执行上述过程直到找到空间。

示例：考虑以下基本散列函数“key mod 5”，以及要插入的键：50、70、76、85 和 93。

步骤 1： 首先，使用指定的散列算法创建一个空的散列表，其潜在的散列值范围在 0 到 4 之间。

步骤 2： 现在单独添加每个键到散列表。50 是第一个键。由于 50%5=0，它将映射到槽号 0。因此，将其放在槽号 0。

步骤 3： 现在 70 是下一个键。由于 50 已经在槽号 0 中，它将映射到槽号 0，因为 70%5=0，因此查找下一个可用的槽并将其放在那里。

步骤 4： 现在 76 是下一个键。由于 76%5=1，它将映射到槽号 1，但由于槽号 1 已经被 70 占用，找到下一个可用的槽并插入它。

步骤 5： 现在 93 是下一个键。由于 93%5=3，它将映射到槽号 3，因此将其放在那里。

b) 二次探测

在计算机编程中，二次探测是一种用于解决散列表中散列冲突的开放寻址方法。直到找到一个可用的槽，二次探测通过将任意二次多项式的连续值添加到初始散列索引来工作。

此技术通常被称为“平方中间值法”，因为它在 i² 次迭代中搜索 i² 次探测（槽），其中 i = 0, 1,... n - 1。我们总是从散列生成的地方开始。如果某个位置已经被占用，我们会检查其他位置。

设 n 为散列表的大小，hash(x) 为由散列算法确定的槽索引。

示例：考虑以下示例表：大小 = 7，Hash(x) = x% 7，冲突分辨率策略：f(i) = i²。添加 22、30 和 50。

步骤 1：创建一个大小为 7 的表。

步骤 2：添加 22 和 30。

Hash(25) = 22 % 7 = 1，由于索引 1 处的单元是空的，我们可以直接将 22 放在槽 1。

Hash(30) = 30 % 7 = 2，由于索引 2 处的单元是空的，我们可以直接将 30 放在槽 2。

步骤 3：插入 50

Hash(25) = 50 % 7 = 1

在我们的散列表槽 1 已经被占用。所以，我们将搜索槽 1+1²，即 1+1 = 2，

再次发现槽 2 被占用，所以我们将搜索单元 1+2²，即 1+4 = 5。现在，单元 5 未被占用，所以我们将 50 放在槽 5。

散列中的“负载因子”是什么意思？

散列表中的条目数除以散列表的大小称为散列表的负载因子。当我们想要重新散列以前的散列函数或想要向现有散列表添加更多条目时，负载因子是我们的关键参数。

它有助于评估散列函数的有效性，通过指示使用该特定散列算法时键是否均匀分布在散列表中。

复杂度和负载因子

• K 和散列函数决定了第一步需要多长时间。例如，如果键是字符串“abcd”，则字符串的长度可能会影响散列函数。但是，对于非常大的 n 值，map 条目的数量和键的长度与 n 相比几乎可以忽略不计，因此可以将散列计算视为在常数时间内完成，即 O(1)。
• 第二步需要遍历存在于该索引处的 K-V 对列表。在这种情况下，最坏的情况是所有 n 个项都位于同一个索引处。因此，时间复杂度为 O(n)。但是，已经做了足够的工作来确保散列算法均匀地划分数组的键，因此这种情况很少发生。
• 因此，如果有 n 个条目且 b 是数组的大小，则每个索引上将有 n/b 个项。负载因子，即 n/b，是表示我们 map 负载的数字。
• 必须保持较低的负载因子，以减少单个索引中的条目数量，并保持几乎恒定的复杂度，即 O(1)。

重新散列是什么意思？

顾名思义，重新散列就是再次散列。本质上，随着负载因子超过其初始值（默认负载因子为 0.75），复杂度会增加。为了保持较低的负载因子和最小的复杂度，数组的大小会增加（加倍），并且所有值都会被重新散列并存储在新加倍大小的数组中。

当散列映射填满时，负载因子（即项数与桶数的比例）会增加。随着负载因子的增加，冲突的增加可能会导致性能问题。这可以通过调整散列映射的大小并将项重新散列到新桶中来避免，这会降低负载因子并降低冲突的可能性。

在重新散列过程中，会遍历散列映射的每个元素，并使用适合更改后的散列映射大小的新散列函数来确定每个元素的新的桶位置。虽然这个过程可能需要一段时间，但保持散列映射的正常运行至关重要。

为什么需要重新散列？

为了避免冲突并保持数据结构的效率，需要重新散列。

当元素被添加到散列映射时，负载因子（即项数与桶数的比率）会增加。当负载因子超过某个阈值（通常设置为 0.75）时，随着冲突的增加，散列映射会失去效率。这可以通过调整散列映射的大小并将项重新散列到新桶中来避免，这会降低负载因子并降低冲突的可能性。此过程称为重新散列。

重新散列在时间和空间上都可能很昂贵，但保持散列映射的有效性非常重要。

重新散列如何工作？

以下是一些重新散列的示例

• 每次向 map 添加新条目时，检查负载因子。
• 如果超过预定义值（或未提供，则为默认值 0.75），则重新散列。
• 为 Rehash 创建一个新的桶数组，其大小是旧数组的两倍。
• 然后，逐个遍历旧桶数组，并对每个元素使用 insert() 将其添加到新的、更大的桶数组中。

散列数据结构的使用

• 数据库使用散列进行索引。
• 基于磁盘的数据结构使用散列。
• JavaScript 散列用于在 Python 等各种编程语言中实现对象。

散列数据结构的实时应用

• 缓存映射使用散列来快速访问数据。
• 可以使用散列进行密码验证。
• 在密码学中，散列用作消息摘要。
• 使用 Rabin-Karp 方法进行字符串模式匹配。
• 计算字符串有多少个不同的子串。

散列数据结构的优点

• 与其他数据结构相比，散列提供了更高的同步性。
• 与搜索树或其他数据结构相比，散列表更有效。
• 平均而言，散列在搜索、插入和删除等活动中提供恒定的速度。

散列数据结构的缺点

• 当存在大量冲突时，散列会浪费资源。
• 对于大量的潜在键，散列冲突几乎是无法避免的。
• 散列不允许空值。

现在让我们看一个散列数据结构的例子

两个集合的不重叠和

陈述： 给定大小为 n 的两个数组 A[] 和 B[]。已知这两个数组各自包含不同的元素。我们需要找到所有不公共元素的总和。

例如

蛮力法： 一种直接的方法是首先检查 A[] 中的每个元素是否也存在于 B[] 中，然后，如果存在，只需将其加到结果中。以相同的方式，遍历 B[] 并将 B 中不存在的每个元素添加到结果中。

时间复杂度： O(n²)

辅助空间： O(1)，因为不断消耗额外空间。

使用散列思想，用两个数组的内容填充空的散列。然后，遍历散列表并将计数为 1 的每个成员相加。（根据查询，每个数组的项都是分开的。）

下面是上述方法在 C++ 中的解决方案

输出

35
...........
Process executed in 0.11 seconds
Press any key to continue.

说明

由于无序映射添加的摊销常数性质，时间复杂度为 O(n)，空间复杂度为 O(n)。

使用集合数据结构是另一种策略

• 将数组 A 的项添加到集合数据结构并对其进行求和。
• 确定 B 的元素是否存在于集合中；如果存在，则从集合中删除当前元素；否则，将当前元素添加到总和中。
• 最后，提供总和

下面是 C++ 中该问题的更好方法的程序

输出

39
........
Process executed in 0.05 seconds
Press any key to continue.

结论

根据上述描述，散列的目的是解决在集合中快速定位项的问题。例如，如果我们有一百万个英语单词的列表，并且想找到一个特定的关键字，我们将使用散列来更有效地查找和找到它。逐个搜索数百万个列表直到找到匹配项效率低下。通过首先将搜索范围缩小到较小的单词集，散列可以加快搜索过程。