本文概述
- 为什么我们需要散列？
- 通用散列
- 重新整理
哈希用于索引和检索数据库中的项目, 因为使用最短的哈希键查找项目要比使用原始值查找项目更快。它也用在许多加密算法中。
通过使用键（唯一值）生成哈希码。
散列是一种技术, 其中通过对键字段值应用相同的操作, 将给定的键字段值转换为记录的存储位置地址。
散列的优势在于, 即使对于较大的一侧, 基本操作的执行时间也可以保持恒定。
为什么我们需要散列？ 假设我们有50名员工, 并且必须为每个员工提供4位数字的密钥（出于安全性考虑）, 我们希望在输入密钥后将用户映射直接定向到存储数据的特定位置。
如果我们根据4位数字给出位置编号, 则我们将必须保留0000至9999个地址, 因为任何人都可以使用任何人作为密钥。有很多浪费。
为了解决此问题, 我们使用散列, 该散列将产生与用户键相对应的散列表的索引的较小值。
通用散列 【散列算法实现分析】令H为哈希函数的有限集合, 这些哈希函数将给定的键U映射到{0, 1 … .. m-1}范围内。如果对于每对不同的密钥k, l∈U, h（k）= h（l）最多为| H | / m的哈希函数h∈H的数量, 则认为这种集合是通用的。换句话说, 使用从H中随机选择的哈希函数, 如果h（k）和h（l）是随机且独立的, 则不同键k和l之间发生冲突的机会不大于发生冲突的机会的1 / m。从集合{0, 1, … m-1}中选择。
重新整理 如果任何阶段的哈希表几乎已满, 则操作的运行时间将开始占用太多时间, 在这种情况下插入操作可能会失败, 最佳解决方案如下：
- 创建一个新的哈希表, 其大小加倍。
- 扫描原始哈希表, 计算新的哈希值, 然后插入新的哈希表。
- 释放原始哈希表占用的内存。
解决方案：使用线性探测, 哈希表的最终状态将是：
文章图片
使用c1 = 1, c2 = 3的二次探查, 哈希表的最终状态为h（k, i）=（h’ （k）+ c1 * i + c2 * i2）mod m其中m = 11和h’ （k）= k mod m。
文章图片
使用双重哈希, 哈希表的最终状态将是：
文章图片
