哈希是指使用称为哈希函数的数学公式从可变大小的输入生成固定大小的输出的过程。该技术确定数据结构中项目存储的索引或位置。
目录
为什么需要Hash数据结构
每天，互联网上的数据都在成倍增加，有效地存储这些数据总是很困难。在日常编程中，这些数据量可能不会那么大，但仍然需要轻松高效地存储、访问和处理这些数据。用于此目的的一种非常常见的数据结构是数组数据结构。
现在问题来了，如果 Array 已经存在，为什么需要一个新的数据结构！答案就在“效率”这个词上。尽管在 Array 中存储需要 O(1) 时间，但在其中搜索至少需要 O(log n) 时间。这个时间看起来很小，但是对于一个大数据集来说，它会引起很多问题，这反过来又会导致 Array 数据结构效率低下。
所以现在我们正在寻找一种数据结构，它可以存储数据并在恒定时间内在其中进行搜索，即在 O(1) 时间内。这就是散列数据结构发挥作用的方式。随着 Hash 数据结构的引入，现在可以轻松地以恒定时间存储数据，也可以在恒定时间内检索数据。
散列的组成部分
哈希主要有三个组成部分：
- 键：键可以是任何字符串或整数，它作为散列函数的输入提供，散列函数是确定数据结构中项目存储索引或位置的技术。
- 哈希函数：哈希函数接收输入键并返回称为哈希表的数组中元素的索引。该索引称为散列索引。
- 哈希表：哈希表是一种数据结构，它使用称为哈希函数的特殊函数将键映射到值。哈希以关联的方式将数据存储在数组中，其中每个数据值都有自己唯一的索引。
散列的组成部分
哈希是如何工作的？
假设我们有一组字符串 {“ab”、“cd”、“efg”}，我们想将其存储在一个表中。
我们这里的主要目标是在 O(1) 时间内快速搜索或更新存储在表中的值，我们不关心表中字符串的顺序。所以给定的一组字符串可以充当键，字符串本身将充当字符串的值，但是如何存储与键对应的值呢？
- 第 1 步：我们知道哈希函数（这是一些数学公式）用于计算哈希值，该哈希值充当存储该值的数据结构的索引。
-
第 2 步：那么，让我们分配
- “一个”= 1，
- “b”=2, .. 等等，所有字母字符。
- 第三步：因此，将字符串的所有字符相加得到的数值：
- “ab”= 1 + 2 = 3，
- “CD” = 3 + 4 = 7 ,
- “efg”= 5 + 6 + 7 = 18
- 第 4 步：现在，假设我们有一个大小为 7 的表来存储这些字符串。这里使用的散列函数是key mod Table size中字符的总和。我们可以通过取sum(string) mod 7来计算字符串在数组中的位置。
-
第 5 步：所以我们将存储
- “ab”在 3 mod 7 = 3,
- 7 mod 7 = 0 中的“cd”，以及
- 18 mod 7 中的“efg”= 4。
使用数组索引映射键
上述技术使我们能够使用简单的哈希函数计算给定字符串的位置，并快速找到存储在该位置的值。因此，散列的想法似乎是在表中存储（键，值）数据对的好方法。
什么是哈希函数？
哈希函数创建键和值之间的映射，这是通过使用称为哈希函数的数学公式来完成的。散列函数的结果称为散列值或散列。哈希值是原始字符串的表示，但通常比原始字符串小。
例如：将数组视为 Map，其中键是索引，值是该索引处的值。因此，对于数组 A，如果我们有索引i，它将被视为键，那么我们可以通过简单地查看 A[i] 处的值来找到该值。
简单地查找 A[i]。
哈希函数的类型：
有许多哈希函数使用数字或字母数字键：
- 划分法
- 中平法
- 折叠法
- 乘法 该方法包括以下步骤： 选择一个常数值 A 使得 0 < A 乘法。
好的散列函数的属性
将每个项目映射到其自己的唯一槽的哈希函数称为完美哈希函数。如果我们知道项目和集合永远不会改变，我们可以构造一个完美的哈希函数，但问题是没有系统的方法来构造一个给定任意项目集合的完美哈希函数。幸运的是，即使散列函数不完美，我们仍然可以获得性能效率。我们可以通过增加哈希表的大小来实现一个完美的哈希函数，这样每一个可能的值都可以容纳。因此，每个项目都会有一个唯一的插槽。虽然这种方法对于少量项目是可行的，但是当可能性很大时就不实用了。
所以，我们可以构造我们的哈希函数来做同样的事情，但是在构造我们自己的哈希函数时我们必须注意的事情。
一个好的哈希函数应该具备以下特性：
- 可高效计算。
- 应均匀分布键（每个表位置对每个位置的可能性相同。
- 应该尽量减少碰撞。
- 应该有一个低负载因子（表中的项目数除以表的大小）。
使用哈希函数计算哈希值的复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
散列问题
如果我们考虑上面的例子，我们使用的散列函数是字母的总和，但如果我们仔细检查散列函数，那么问题可以很容易地可视化，对于不同的字符串，散列函数开始生成相同的散列值。
例如：{“ab”、“ba”} 都具有相同的哈希值，字符串 {“cd”、“be”} 也生成相同的哈希值，等等。这就是所谓的冲突，它会在搜索中产生问题、插入、删除和更新值。
什么是碰撞？
散列过程为大键生成一个小数字，因此两个键有可能产生相同的值。新插入的键映射到一个已经被占用的键的情况，必须使用一些冲突处理技术来处理。
什么是哈希碰撞
如何处理碰撞？
处理碰撞的方法主要有两种：
- 独立链接：
- 打开寻址：
冲突解决技术
1)分离链接
这个想法是让哈希表的每个单元格指向一个具有相同哈希函数值的记录链表。链接很简单，但需要表外的额外内存。
示例：我们已经给出了一个散列函数，我们必须使用单独的链接方法在散列表中插入一些元素来解决冲突。
哈希函数 = key % 5,
元素 = 12、15、22、25 和 37。
让我们逐步了解如何解决上述问题：
-
第一步：首先根据提供的哈希函数画出空哈希表，哈希值的可能范围为0到4。
哈希表
- 第 2 步：现在将所有键一一插入哈希表中。要插入的第一个键是 12，它映射到桶号 2，这是使用哈希函数 12%5=2 计算得出的。
将 12 插入哈希表
- 第 3 步：现在下一个键是 22。它将映射到桶号 2，因为 22%5=2。但是 bucket 2 已经被 key 12 占用了。
将 22 插入哈希表
- 第 4 步：下一个键是 15。它将映射到槽号 0，因为 15%5=0。
将 15 插入哈希表
- 第 5 步：现在下一个键是 25。它的桶号将是 25%5=0。但是 bucket 0 已经被 key 25 占用了。因此，单独的链接方法将通过创建到 bucket 0 的链表来再次处理冲突。
将 25 插入哈希表
因此，以这种方式，分离链接方法被用作冲突解决技术。
2）开放寻址
在开放寻址中，所有元素都存储在哈希表本身中。每个表条目包含一条记录或 NIL。查找元素时，我们会逐个检查表槽，直到找到所需的元素或明确该元素不在表中。
2.a) 线性探测
在线性探测中，哈希表从哈希的原始位置开始按顺序搜索。如果万一我们得到的位置已经被占用，那么我们检查下一个位置。
算法：
- 计算哈希键。即key = data % size
- 检查hashTable[key]是否为空
- 通过hashTable[key] = data直接存储值
- 如果哈希索引已经有一些值那么
- 使用key = (key+1) % size 检查下一个索引
- 检查下一个索引是否可用 hashTable[key] 然后存储该值。否则尝试下一个索引。
- 执行上述过程，直到我们找到空间。
示例：让我们将一个简单的哈希函数视为“key mod 5”，要插入的一系列密钥为 50、70、76、85、93。
- Step1：首先根据提供的哈希函数画出空哈希表，哈希值的可能范围为0到4。
哈希表
- 第 2 步：现在将所有键一一插入哈希表中。第一个键是 50。它将映射到槽号 0，因为 50%5=0。所以将它插入插槽号 0。
向哈希表中插入 50
- 第 3 步：下一个键是 70。它将映射到槽号 0，因为 70%5=0 但 50 已经在槽号 0，因此，搜索下一个空槽并将其插入。
将 70 插入哈希表
- 第 4 步：下一个键是 76。它将映射到 1 号插槽，因为 76%5=1 但 70 已经在 1 号插槽上，因此，搜索下一个空插槽并将其插入。
将 76 插入哈希表
- 第五步：下一个key是93，它会映射到slot 3，因为93%5=3，所以把它插入到slot 3。
将 93 插入哈希表
2.b) 二次探测
二次探测是计算机编程中的一种开放寻址方案，用于解决哈希表中的哈希冲突。二次探测通过获取原始哈希索引并添加任意二次多项式的连续值直到找到空槽来运行。
使用二次探测的示例序列是：
H + 1 2 , H + 2 2 , H + 3 2 , H + 4 2 ……………………. H + k 2
这种方法也称为中方法，因为在这种方法中，我们在第 i 次迭代中寻找第 i 2个探针（槽），并且 i = 0, 1, ... 的值。. . n – 1。我们总是从原始哈希位置开始。如果只有位置被占用，那么我们检查其他插槽。
令 hash(x) 为使用哈希函数计算的槽索引，n 为哈希表的大小。
如果槽 hash(x) % n 已满，那么我们尝试 (hash(x) + 1 2 ) % n。
如果 (hash(x) + 1 2 ) % n 也满了，那么我们尝试 (hash(x) + 2 2 ) % n。
如果 (hash(x) + 2 2 ) % n 也满了，那么我们尝试 (hash(x) + 3 2 ) % n。将对i
的所有值重复此过程，直到找到空槽
示例：假设表 Size = 7，散列函数为 Hash(x) = x % 7 ，冲突解决策略为 f(i) = i 2。插入 = 25、33 和 105
- 第 1 步：创建一个大小为 7 的表。
哈希表
-
第 2 步– 插入 22 和 30
- Hash(25) = 22 % 7 = 1，因为索引 1 处的单元格是空的，我们可以很容易地在槽 1 处插入 22。
- Hash(30) = 30 % 7 = 2，因为索引 2 处的单元格是空的，我们可以很容易地在槽 2 处插入 30。
在哈希表中插入键 22 和 30
-
第 3 步：插入 50
- 哈希 (25) = 50 % 7 = 1
- 在我们的哈希表中，槽 1 已经被占用。因此，我们将搜索插槽 1+1 2，即 1+1 = 2，
- 再次发现 slot 2 被占用，所以我们将搜索 cell 1+2 2，即 1+4 = 5，
- 现在，单元格 5 没有被占用，所以我们将 50 放在插槽 5 中。
在哈希表中插入密钥 50
2.c) 双重哈希
双重哈希表中的一种冲突解决技术。双哈希利用两个哈希函数，
- 第一个哈希函数是h1(k)，它获取密钥并给出哈希表中的位置。但是如果新位置没有被占用或者是空的，那么我们可以很容易地放置我们的钥匙。
- 但是如果位置被占用（冲突），我们将结合使用第二个哈希函数h2(k)和第一个哈希函数h1(k)来找到哈希表上的新位置。
这种散列函数的组合形式为
h(k, i) = (h1(k) + i * h2(k)) % n
在哪里
- i 是一个非负整数，表示碰撞次数，
- k = 被散列的元素/键
- n = 哈希表大小。
双哈希算法的复杂性：
时间复杂度：O(n)
示例：将键 27、43、692、72 插入大小为 7 的哈希表。其中第一个哈希函数是h1 (k) = k mod 7，第二个哈希函数是h2(k) = 1 + (k模式 5)
-
第 1 步：插入 27
- 27 % 7 = 6，位置 6 为空，因此将 27 插入 6 槽。
在哈希表中插入键 27
-
第 2 步：插入 43
- 43 % 7 = 1，位置 1 为空，因此将 43 插入 1 个槽。
在哈希表中插入键 43
-
第 3 步：插入 692
- 692 % 7 = 6，但位置 6 已被占用，这是一次碰撞
- 所以我们需要使用双重哈希来解决这个冲突。
hnew = [h1(692) + i * (h2(692)] % 7
= [6 + 1 * (1 + 692 % 5)] % 7
= 9 % 7
= 2
现在，因为 2 是一个空槽，
所以我们可以将 692 插入第二个插槽。
在哈希表中插入密钥 692
-
第 4 步：插入 72
- 72 % 7 = 2，但位置 2 已被占用，这是一次碰撞。
- 所以我们需要使用双重哈希来解决这个冲突。
hnew = [h1(72) + i * (h2(72)] % 7
= [2 + 1 * (1 + 72 % 5)] % 7
= 5 % 7
= 5,
现在，因为 5 是一个空位，
所以我们可以将 72 插入第 5 个槽。
在哈希表中插入键 72