极客教程哈希(Hash)完整教程
Hashing 指使用称为哈希函数的数学公式从可变大小的输入生成固定大小输出的过程。这种技术确定数据结构中存储项的索引或位置。
为什么需要Hash数据结构
每一天，互联网上的数据都在成倍增长，而如何有效地存储这些数据一直是一个难题。在日常编程中，这些数据量可能没有那么大，但仍然需要轻松有效地存储、访问和处理这些数据。用于这种目的的一种非常常见的数据结构是Array数据结构。
现在问题来了，如果Array已经存在了，还需要新的数据结构吗?答案就在” efficiency ”。虽然在Array中存储需要O(1)时间，但在其中搜索至少需要O(log n)时间。这个时间看起来很小，但对于大型数据集来说，它可能会导致很多问题，这反过来又会使Array数据结构效率低下。
所以现在我们要找一个数据结构，它可以在常数时间内存储数据并在里面搜索，也就是O(1)的时间。这就是哈希数据结构如何发挥作用的。随着哈希数据结构的引入，现在可以轻松地在常量时间内存储数据，并在常量时间内检索数据。
Hash的组成
哈希主要有三个组成部分:
- Key: Key 可以是作为哈希函数输入的任何字符串或整数，哈希函数是确定数据结构中项的索引或存储位置的技术。
- Hash 函数: Hash 函数 接收输入键并返回名为哈希表的数组中元素的索引。该指数被称为 hash index .
- Hash 表: 哈希表是一种数据结构，它使用名为哈希函数的特殊函数将键映射到值。哈希以关联的方式将数据存储在数组中，其中每个数据值都有自己唯一的索引。
Hash是如何工作的
假设我们有一组字符串{” ab “， ” cd “， ” efg “}，我们想把它存储在一个表中。
这里我们的主要目标是在O(1)的时间内快速搜索或更新存储在表中的值，我们不关心字符串在表中的顺序。给定的一组字符串可以作为键字符串本身将作为字符串的值但是如何存储与键对应的值呢?
- Step 1: 我们知道哈希函数(这是一些数学公式)是用来计算哈希值的，哈希值是存储该值的数据结构的索引。
- Step 2: So, let’s assign
- “a” = 1,
- “b”= 2,. .等，所有字母字符。
- Step 3: 因此，数值为字符串中所有字符的总和:
- “ab” = 1 + 2 = 3,
- cd = 3 + 4 = 7，
- ” efg ” = 5 + 6 + 7 = 18
- Step 4: 现在，假设我们有一个大小为7的表来存储这些字符串。这里使用的哈希函数是中字符的和 表大小 ． 函数可以计算字符串在数组中的位置 sum(string) mod 7 .
- Step 5: 然后我们将存储
- ab在3中mod 7 = 3，
- “cd”在7 mod 7 = 0，和
- “efg”在18 mod 7 = 4。
上面的技术使我们能够通过使用一个简单的哈希函数来计算给定字符串的位置，并快速找到存储在该位置的值。因此，哈希似乎是在表中存储(键、值)对数据的一种很好的方法。
什么是Hash函数
哈希函数创建键和值之间的映射，这是通过使用称为哈希函数的数学公式来完成的。散列函数的结果被称为散列值或散列。哈希值是原始字符串的一种表示，但通常小于原始字符串。
例如:将数组视为Map，其中键是索引，值是该索引处的值。对于数组A，如果我们有index i 它将被视为键，然后我们可以通过简单地查看A[i]的值来找到值。
只是查找A[i]。
哈希函数的类型:
有许多使用数字或字母数字键的散列函数。本文主要讨论不同的哈希函数:
- Division函数
- Mid Square函数
- Folding函数
- 乘法函数
一个好的哈希函数的性质
将每一项映射到自己唯一槽的哈希函数被称为完美哈希函数。我们可以构造一个完美的哈希函数如果我们知道这些项和集合永远不会改变但问题是没有系统的方法来构造一个完美的哈希函数给定任意项的集合。幸运的是，即使哈希函数并不完美，我们仍然可以获得性能效率。我们可以通过增加哈希表的大小来实现一个完美的哈希函数，这样每个可能的值都可以被容纳。因此，每个项目将有一个唯一的插槽。虽然这种方法对少数项目是可行的，但当可能性的数量很大时，它就不实用了。
所以，我们可以构造我们的哈希函数来做同样的事情，但在构造我们自己的哈希函数时，我们必须注意的一点是。
一个 good散列函数 应该具有以下属性:
- 有效的可计算的。
- 应该均匀分配键(每个表位置对每个键的概率相等。
- 应该减少碰撞。
- 负载系数应该很低(表中的项数除以表的大小)。
使用哈希函数计算哈希值的复杂性
- 时间复杂度:O (n)
- 空间复杂度:O (1)
Hashing 的问题
如果我们考虑上面的例子，我们使用的哈希函数是字母的和，但如果我们仔细检查哈希函数，那么问题很容易就可以看到，对于不同的字符串，相同的哈希值是由哈希函数生成的。
例如:{” ab “， ” ba “}都有相同的哈希值，字符串{” cd “， ” be “}也产生相同的哈希值，等等。这就是所谓的 collision 它还会在搜索、插入、删除和更新值方面产生问题。
什么是collision
哈希过程为一个大的键生成一个小的数字，所以有可能两个键产生相同的值。新插入的键映射到已经被占用的键，必须使用一些碰撞处理技术来处理。
如何处理collision
主要有两种方法来处理碰撞:
- Separate Chaining
- Open Addressing
1)单独的链接
其思想是使哈希表的每个单元格指向具有相同哈希函数值的记录链表。链接很简单，但是需要额外的表外内存。
示例:我们给出了一个哈希函数，我们必须使用单独的链接方法在哈希表中插入一些元素，以实现冲突解决技术。
Hash function = key % 5,
Elements = 12, 15, 22, 25 and 37.
让我们来看看如何一步步解决上述问题:
- Step 1: 首先绘制一个空的哈希表，根据所提供的哈希函数，这个哈希表可能包含从0到4的哈希值范围。
- Step 2: 现在逐个插入哈希表中的所有键。插入的第一个键是12，该键映射到通过哈希函数12%5=2计算出的桶2。
- Step 3: 下一个键是15。它将映射到槽号0，因为15%5=0。所以把它插入5号桶。
- Step 4: 下一个键是22。它将映射到桶2，因为22%5=2。但是bucket 2已经被key 12占用。因此，单独的链接方法将通过创建桶2的链表来处理这个冲突。
- Step 5: 下一个键是25。它的桶数将是25%5=0。但是桶0已经被键25占用。因此，单独的链接方法将通过创建桶0的链表来再次处理冲突。
因此，采用分离链接法作为碰撞分辨技术。
2) Open Addressing
在开放寻址中，所有元素都存储在哈希表本身中。每个表项要么包含一条记录，要么包含NIL。当搜索一个元素时，我们逐个检查表槽，直到找到所需的元素，或者很明显该元素不在表中。
2.a) Linear Probing
在线性探测中，从哈希的原始位置开始顺序搜索哈希表。如果在这种情况下，我们得到的位置已经被占用，那么我们检查下一个位置。
Algorithm:
- 计算散列键。即。 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的哈希值范围。
- Step 2: 现在逐个插入哈希表中的所有键。第一个键是50。它将映射到槽号0，因为50%5=0。把它插入0号槽。
- Step 3: 下一个键是70。它将映射到0号槽，因为70%5=0，但50已经在0号槽，所以，搜索下一个空槽并插入它。
- Step 4: 下一个键是76。它将映射到1号槽，因为76%的5=1，但70已经在1号槽，所以，搜索下一个空槽并插入它。
- Step 5: 下一个键是93，它将映射到3号槽，因为93%5=3，所以将它插入3号槽。
2. b)二次探测
二次探测是计算机编程中用于解决哈希表中哈希冲突的一种开放寻址方案。二次探测的操作方法是取原始哈希索引，然后将任意二次多项式的连续值相加，直到找到一个开放的槽。
一个使用二次探测的示例序列是:
这种方法也被称为中平方法，因为在这种方法中我们寻找i 2 ‘第i次迭代的第一个探针(槽)，i的值为0,1，…n – 1。我们总是从原来的散列位置开始。如果只有这个位置被占用，那么我们就检查其他槽位。
设hash(x)是使用哈希函数计算的槽索引，n是哈希表的大小。
示例:让我们考虑表Size = 7，哈希函数为hash (x) = x % 7，冲突解决策略为f(i) = i 2 ． 插入= 25、33和105
- Step 1: 创建一个大小为7的表。
- Step 2 – 插入22 和 30
- 由于索引1的单元格是空的，我们可以很容易地在slot 1插入22。
- Hash(30) = 30% 7 = 2，因为索引2的单元格是空的，我们可以很容易地在slot 2插入30。
- Step 3: 插入 50
- Hash(25) = 50% 7 = 1
- 在我们的哈希表中，slot 1已经被占用。我们要搜索位置1+1 2 , i.e. 1+1 = 2,
- 再次发现槽2被占用，所以我们将搜索单元格1+2 2 , i.e.1+4 = 5,
- 现在，单元格5没有被占用，所以我们将50放在5号位置。
2.c) Double Hashing
双哈希是开放寻址哈希表中的一种冲突解决技术。二次哈希使用两个哈希函数，
- 第一个哈希函数是 h1(k) 它获取键并给出哈希表上的一个位置。但如果新位置没有被占用或空置，那么我们可以很容易地放置我们的钥匙。
- 但如果位置被占用(碰撞)，我们将使用二级哈希函数 h2(k) 与第一个哈希函数结合使用 h1(k) 查找哈希表上的新位置。
这种哈希函数的组合就是这种形式
h(k, i) = h1(k) + i * h2(k)) % n
其中
- i为非负整数，表示碰撞数，
- K =被散列的元素/键
- N =哈希表大小。
双哈希算法的复杂度:
Time complexity: O(n)
示例: 将键27、43、98、72插入大小为7的哈希表中。第一个哈希函数在哪里 h1(k) = k mod 7 第二个哈希函数是 H2 (k) = 1 + (k mod 5)
- Step 1: Insert 27
- 27 % 7 = 6，位置6是空的，所以插入27到6插槽。
- Step 2: 插入 43
- 43 % 7 = 1，位置1是空的，所以插入43到1插槽。
- Step 3: 插入 92
- 92% 7 = 6，但是6号位置已经有人了，这是一次碰撞
- 所以我们需要使用双重哈希来解决这个冲突。
- Step 4: 插入 72
- 72% 7 = 2，但位置2已经被占用，这是一个碰撞。
- 所以我们需要使用双重哈希来解决这个冲突。
Hash中的负载因子是什么意思
哈希表的负载因子可以定义为哈希表所包含的项数除以哈希表的大小。当我们想要重新哈希前面的哈希函数或想要向现有哈希表添加更多元素时，负载因子是决定性的参数。
它帮助我们确定哈希函数的效率，也就是说，它告诉我们所使用的哈希函数是否在哈希表中均匀分布键。
Load Factor = Total elements in hash table/ Size of hash table
什么是重新哈希
顾名思义，重新哈希就是再次哈希。基本上，当负载因子增加到超过其预定义值(负载因子的默认值为0.75)时，复杂性会增加。因此，为了克服这个问题，数组的大小增加了(两倍)，所有的值再次哈希并存储在新的两倍大小的数组中，以保持低负载因子和低复杂度。
哈希数据结构的应用
- 哈希在数据库中用于索引。
- 哈希用于基于磁盘的数据结构。
- 在Python等编程语言中，JavaScript散列用于实现对象。
哈希数据结构的实时应用
- 哈希用于缓存映射，以便快速访问数据。
- 散列可用于密码验证。
- 哈希在密码学中用作消息摘要。
哈希数据结构的优点
- 哈希提供了比其他数据结构更好的同步。
- 哈希表比搜索树或其他数据结构更有效
- 哈希为搜索、插入和删除操作提供了固定的平均时间。
哈希数据结构的缺点
- 当存在许多冲突时，哈希是低效的。
- 对于大量可能的键集，哈希冲突实际上是无法避免的。
- 哈希不允许空值。
总结
从上面的讨论中，我们得出结论，散列的目标是解决快速找到集合中的项的挑战。例如，如果我们有一个包含数百万个英语单词的列表，我们希望找到一个特定的术语，那么我们可以使用哈希来更有效地定位和找到它。在数以百万计的列表中检查每一项，直到找到匹配项，这将是低效的。哈希法通过在开始时将搜索限制在更小的单词集来减少搜索时间。