散列算法实现分析

本文概述

• 为什么我们需要散列？
• 通用散列
• 重新整理

散列是将字符串转换为通常较短的固定长度值或表示原始字符串的键。

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

通过使用键（唯一值）生成哈希码。

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

散列的优势在于, 即使对于较大的一侧, 基本操作的执行时间也可以保持恒定。

为什么我们需要散列？

假设我们有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}中选择。

重新整理

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

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

示例：考虑使用具有主要哈希函数h’（k）= k mod m的开放式寻址, 将密钥10、22、31、4、15、28、17、88和59插入长度为m = 11的哈希表中。说明使用线性探测, 使用c1 = 1和c2 = 3的二次探测以及使用h2（k）= 1 +（k mod（m-1））的双哈希进行插入的这些键的结果。

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

使用c1 = 1, c2 = 3的二次探查, 哈希表的最终状态为h（k, i）=（h’（k）+ c1 * i + c2 * i2）mod m其中m = 11和h’ （k）= k mod m。

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