哈希

哈希是将字符串转换为通常更短的固定长度的值或键，该值或键代表原始字符串。

哈希用于索引和检索数据库中的项目，因为使用最短的哈希键查找项目比使用原始值查找项目更快。它还用于许多加密算法中。

哈希码是通过使用键生成的，键是一个唯一值。

哈希是一种技术，通过对给定的键字段值应用相同的操作，将其转换为记录存储位置的地址。

哈希的优点是即使对于更大的数据量，基本操作的执行时间也能保持不变。

我们为什么需要哈希？

假设我们有 50 个员工，我们必须为每个员工提供一个 4 位数的密钥（出于安全考虑），并且我们希望在输入密钥后，直接将用户映射到数据存储的特定位置。

如果我们根据 4 位数给出位置编号，我们将不得不保留 0000 到 9999 的地址，因为任何人都可以将任何一个用作密钥。这样会造成很多浪费。

为了解决这个问题，我们使用哈希，它将生成哈希表索引的一个较小值，该索引对应于用户的密钥。

通用哈希

设 H 是一个有限的哈希函数集合，它将给定的键的宇宙 U 映射到范围 {0, 1..... m-1}。如果对于每对不同的键 k,l∈U，满足 h(k)= h(l) 的哈希函数 h∈ H 的数量最多为 |H|/m，则称这样的集合是通用的。换句话说，从 H 中随机选择一个哈希函数，不同键 k 和 l 之间发生冲突的概率不超过 1/m，如果 h(k) 和 h(l) 是从集合 {0,1,...m-1} 中随机且独立地选择的，发生冲突的概率为 1/m。

Rehash

如果哈希表在任何阶段都变得几乎已满，则操作的运行时间将开始占用太多时间，在这种情况下，插入操作可能会失败，最好的解决方案如下所示

1. 创建一个新的哈希表，其大小加倍。
2. 扫描原始哈希表，计算新的哈希值并插入到新的哈希表中。
3. 释放原始哈希表占用的内存。

示例： 考虑使用开地址法将键 10、22、31、4、15、28、17、88 和 59 插入到长度为 m = 11 的哈希表中，其中主要的哈希函数 h' (k) = k mod m 。使用线性探测、使用二次探测 c₁=1 和 c₂=3，以及使用双重哈希 h₂(k) = 1 + (k mod (m-1)) 说明插入这些键的结果。

解决方案：使用线性探测，哈希表的最终状态将是

使用二次探测，其中 c₁=1，c₂=3，哈希表的最终状态将是 h (k, i) = (h' (k) +c₁*i+ c₂ *i²) mod m，其中 m=11 且 h' (k) = k mod m。

使用双重哈希，哈希表的最终状态将是