Hashing 指使用称为哈希函数的数学公式从可变大小的输入生成固定大小输出的过程。这种技术确定数据结构中存储项的索引或位置。

每一天，互联网上的数据都在成倍增长，而如何有效地存储这些数据一直是一个难题。在日常编程中，这些数据量可能没有那么大，但仍然需要轻松有效地存储、访问和处理这些数据。用于这种目的的一种非常常见的数据结构是Array数据结构。

现在问题来了，如果Array已经存在了，还需要新的数据结构吗?答案就在” efficiency ”。虽然在Array中存储需要O(1)时间，但在其中搜索至少需要O(log n)时间。这个时间看起来很小，但对于大型数据集来说，它可能会导致很多问题，这反过来又会使Array数据结构效率低下。

所以现在我们要找一个数据结构，它可以在常数时间内存储数据并在里面搜索，也就是O(1)的时间。这就是哈希数据结构如何发挥作用的。随着哈希数据结构的引入，现在可以轻松地在常量时间内存储数据，并在常量时间内检索数据。

哈希主要有三个组成部分:

假设我们有一组字符串{” ab “， ” cd “， ” efg “}，我们想把它存储在一个表中。

这里我们的主要目标是在O(1)的时间内快速搜索或更新存储在表中的值，我们不关心字符串在表中的顺序。给定的一组字符串可以作为键字符串本身将作为字符串的值但是如何存储与键对应的值呢?

上面的技术使我们能够通过使用一个简单的哈希函数来计算给定字符串的位置，并快速找到存储在该位置的值。因此，哈希似乎是在表中存储(键、值)对数据的一种很好的方法。

哈希函数创建键和值之间的映射，这是通过使用称为哈希函数的数学公式来完成的。散列函数的结果被称为散列值或散列。哈希值是原始字符串的一种表示，但通常小于原始字符串。

例如:将数组视为Map，其中键是索引，值是该索引处的值。对于数组A，如果我们有index i 它将被视为键，然后我们可以通过简单地查看A[i]的值来找到值。

只是查找A[i]。

有许多使用数字或字母数字键的散列函数。本文主要讨论不同的哈希函数:

将每一项映射到自己唯一槽的哈希函数被称为完美哈希函数。我们可以构造一个完美的哈希函数如果我们知道这些项和集合永远不会改变但问题是没有系统的方法来构造一个完美的哈希函数给定任意项的集合。幸运的是，即使哈希函数并不完美，我们仍然可以获得性能效率。我们可以通过增加哈希表的大小来实现一个完美的哈希函数，这样每个可能的值都可以被容纳。因此，每个项目将有一个唯一的插槽。虽然这种方法对少数项目是可行的，但当可能性的数量很大时，它就不实用了。

所以，我们可以构造我们的哈希函数来做同样的事情，但在构造我们自己的哈希函数时，我们必须注意的一点是。

一个 good散列函数 应该具有以下属性:

如果我们考虑上面的例子，我们使用的哈希函数是字母的和，但如果我们仔细检查哈希函数，那么问题很容易就可以看到，对于不同的字符串，相同的哈希值是由哈希函数生成的。

例如:{” ab “， ” ba “}都有相同的哈希值，字符串{” cd “， ” be “}也产生相同的哈希值，等等。这就是所谓的 collision 它还会在搜索、插入、删除和更新值方面产生问题。

哈希过程为一个大的键生成一个小的数字，所以有可能两个键产生相同的值。新插入的键映射到已经被占用的键，必须使用一些碰撞处理技术来处理。

主要有两种方法来处理碰撞:

其思想是使哈希表的每个单元格指向具有相同哈希函数值的记录链表。链接很简单，但是需要额外的表外内存。

示例:我们给出了一个哈希函数，我们必须使用单独的链接方法在哈希表中插入一些元素，以实现冲突解决技术。

让我们来看看如何一步步解决上述问题:

因此，采用分离链接法作为碰撞分辨技术。

在开放寻址中，所有元素都存储在哈希表本身中。每个表项要么包含一条记录，要么包含NIL。当搜索一个元素时，我们逐个检查表槽，直到找到所需的元素，或者很明显该元素不在表中。

在线性探测中，从哈希的原始位置开始顺序搜索哈希表。如果在这种情况下，我们得到的位置已经被占用，那么我们检查下一个位置。

Algorithm:

示例: 让我们考虑一个简单的哈希函数“key mod 5”，将要插入的键序列是50,70,76,85,93。

二次探测是计算机编程中用于解决哈希表中哈希冲突的一种开放寻址方案。二次探测的操作方法是取原始哈希索引，然后将任意二次多项式的连续值相加，直到找到一个开放的槽。

一个使用二次探测的示例序列是:

这种方法也被称为中平方法，因为在这种方法中我们寻找i 2 ‘第i次迭代的第一个探针(槽)，i的值为0,1，…n – 1。我们总是从原来的散列位置开始。如果只有这个位置被占用，那么我们就检查其他槽位。

设hash(x)是使用哈希函数计算的槽索引，n是哈希表的大小。

示例:让我们考虑表Size = 7，哈希函数为hash (x) = x % 7，冲突解决策略为f(i) = i 2 ． 插入= 25、33和105

双哈希是开放寻址哈希表中的一种冲突解决技术。二次哈希使用两个哈希函数，

这种哈希函数的组合就是这种形式

其中

双哈希算法的复杂度:

示例: 将键27、43、98、72插入大小为7的哈希表中。第一个哈希函数在哪里 h1​(k) = k mod 7 第二个哈希函数是 H2 (k) = 1 + (k mod 5)

哈希表的负载因子可以定义为哈希表所包含的项数除以哈希表的大小。当我们想要重新哈希前面的哈希函数或想要向现有哈希表添加更多元素时，负载因子是决定性的参数。

它帮助我们确定哈希函数的效率，也就是说，它告诉我们所使用的哈希函数是否在哈希表中均匀分布键。

顾名思义，重新哈希就是再次哈希。基本上，当负载因子增加到超过其预定义值(负载因子的默认值为0.75)时，复杂性会增加。因此，为了克服这个问题，数组的大小增加了(两倍)，所有的值再次哈希并存储在新的两倍大小的数组中，以保持低负载因子和低复杂度。

从上面的讨论中，我们得出结论，散列的目标是解决快速找到集合中的项的挑战。例如，如果我们有一个包含数百万个英语单词的列表，我们希望找到一个特定的术语，那么我们可以使用哈希来更有效地定位和找到它。在数以百万计的列表中检查每一项，直到找到匹配项，这将是低效的。哈希法通过在开始时将搜索限制在更小的单词集来减少搜索时间。