哈希技术全面解析

### 哈希技术全面解析 #### 1. 引言 在计算机科学领域，建立数据的概念用户视图与计算机系统中实际物理存储之间的映射函数至关重要。用户看到的数据视图和实际存储在介质上的数据往往不同，这在软件工程、数据库系统和操作系统等课程中会有更清晰的体现。 另一个关键问题是如何查找存储的数据。以金融机构的交易文件为例，其中包含数百万条记录。对于以批处理模式运行的非交互式程序，顺序访问文件记录是合适的，但对于需要根据不同客户提供交互式响应的程序则不适用。虽然可以使用 BST、堆或 B - 树等数据结构，但如何确定文件记录在存储介质上的实际存储位置，以便在需要时轻松检索，哈希技术就是解决这一问题的有效方法。 哈希是一种解决数据在物理存储介质上的存储位置和检索问题的技术。在哈希中，用于标识记录的键值与记录在存储介质上的位置之间存在可预测的关系。哈希函数通过对键值应用算法来确定其位置，它将键值从较大的定义域映射到较小的地址范围。然而，这可能会导致冲突，即两个或多个键映射到相同的地址，因此需要解决冲突问题。 #### 2. 哈希函数 一个好的哈希函数应具备两个重要特征：一是计算简单快速；二是能将键值（随机或非随机）均匀地分散在地址空间中。常见的哈希函数有以下几种： ##### 2.1 绝对寻址 在绝对寻址中，地址就是键值，即 `Address := KeyValue`。这是一种简单的哈希方法，仅适用于简单情况。在大多数实际场景中，由于存储空间有限，这种方法并不适用。 ##### 2.2 直接表查找 严格来说，直接表查找不是哈希函数，而是一种哈希策略。其步骤如下： 1. 首先通过某种方法生成地址，生成地址的方法可以是本节讨论的任何技术或其他技术。 2. 将键和地址作为单独的索引（目录）存储。 3. 访问记录时，先查询索引以确定其地址。 该技术有三个显著优点：对于中小规模文件的存储非常高效；实现简单；避免了冲突问题。但也存在两个问题：需要管理存储介质上的两个独立物理文件；随着数据文件大小的增加，索引文件的大小也会增加。 ##### 2.3 除留余数法 除留余数法是将键值除以一个适当的数，然后将除法的余数作为记录的地址。在计算机科学中，取整数除法余数的操作称为取模（通常缩写为 mod），即 `Address := KeyValue Mod Divisor`。 使用该方法时需要注意：如果除数是 N，则地址空间的最小大小必须为 N（即 0 到 N - 1）；为了最小化冲突数量，除数通常是一个不包含小于 20 的质因数的大数字，例如 997 或 1011 比 1024 更合适。 该方法的优点是实现简单、对小文件高效且避免使用两个物理文件存储单个数据文件。缺点是不能保证无冲突、在均匀分布键值方面表现不佳，且随着数据集大小的增加，冲突的可能性也会增加。 ##### 2.4 平方取中法 平方取中法是将键值平方，然后从结果的“中间”提取特定数量的数字作为哈希地址。如果需要 N 位的地址空间，则截断平方键值的两端，保留中间的 N 位数字。 例如，若需要一个 4 位地址，键值为 7895，计算过程为 `Address := Mid - square(7895) = 62331025 = 3310`。该方法比除留余数法略有改进，具有实现简单、对大小文件都高效、能较好地均匀分布键值以及避免使用两个物理文件等优点，但同样不能保证无冲突。 ##### 2.5 折叠法 折叠法是将键分割成几个部分，然后通过乘法、加法或减法等方式组合这些部分以获得哈希地址。 例如，假设折叠方法是加法，地址空间为 4 位，对于键值 625149，可以有 `Address := 625 + 149 = 0774` 或 `Address := 6251 + 49 = 6300`。折叠法的优缺点与平方取中法类似。 ##### 2.6 截断法 截断法是忽略键的一部分，将另一部分用作哈希地址。 例如，若地址空间为 4 位，对于键值 625149，可以有 `Address := 625149 = 6251` 或 `Address := 625149 = 5149`。截断法过于简单，不适合实际应用，可能导致重复冲突，且无法均匀分布键值。 ##### 2.7 处理字母数字键值 在很多情况下，键值是字母数字而不是纯数字。此时需要将字母数字数据转换为数字形式，有多种方法可以实现。 以下是常见哈希函数的对比表格： | 哈希函数 | 优点 | 缺点 | | ---- | ---- | ---- | | 绝对寻址 | 简单 | 仅适用于简单情况，存储空间受限 | | 直接表查找 | 存储中小文件高效、实现简单、避免冲突 | 需要管理两个文件，索引文件会随数据文件增大 | | 除留余数法 | 实现简单、小文件高效、避免双文件 | 不能保证无冲突、分布不均、数据集增大冲突增加 | | 平方取中法 | 实现简单、大小文件高效、分布较好、避免双文件 | 不能保证无冲突 | | 折叠法 | 与平方取中法类似 | 与平方取中法类似 | | 截断法 | 简单 | 易冲突、分布不均 | #### 3. 冲突解决 当应用哈希函数时，冲突很可能会发生。常见的冲突解决技术有以下三种： ##### 3.1 线性探测法 线性探测法规定，当发生冲突时，找到离哈希地址最近的空位置并使用。如果到达表的末尾，允许回绕。 负载因子 f 定义为表中要存储的记录数与表的实际大小之比，即 `f = n/s`，其中 n 是要存储的记录数，s 是表的大小。 随着元素添加到表中，会形成占用单元格的块，这称为主聚集。主聚集会增加冲突的可能性，并延长后续插入元素的探测时间。当表填满时，搜索时间会变长。 插入和不成功搜索的预期探测次数为 `½[1 + 1/(1 – f)²]`，成功搜索的预期探测次数为 `½[1 + 1/(1 – f)]`。 线性探测法的优点是概念简单、实现容易，且每个阶段的计算量很小。缺点是会出现主聚集，导致哈希表以簇的形式填充，而不是均匀分布在地址空间中，随着文件变满，搜索时间会变长，冲突可能性增加。 ##### 3.2 同义词链法 同义词链法将哈希地址作为一个列表（可以实现为链表、向量或数组列表）的索引，而不是记录的实际存储位置，这样可以处理具有相同哈希地址的多个记录。 哈希表可以通过以下策略实现： 1. 链表或队列数组 2. 链表或队列的数组列表 3. 数组列表/向量的数组列表/向量 4. 链表或队列的向量 负载因子方面，表大小 s 是链（桶）的数量，而不是节点的数量。每个链的平均长度为 n/s，也就是负载因子 f。不成功搜索需要检查 f 个元素，成功搜索平均需要检查 1 + f/2 个元素，性能明显优于线性探测法。 同义词链法的优点是减少了冲突地址记录的访问时间、插入节点相对容易、键（节点）在地址空间中分布均匀。缺点是需要额外的空间存储链表，链表不能随机访问，确定合适的桶数量可能具有挑战性，但可以通过让用户指定初始大小和期望的负载因子，并让哈希表自动调整大小来解决。 ##### 3.3 再哈希法 再哈希法是另一种开放寻址策略，可显著减少聚集。该技术通过应用第二个哈希函数来解决第一个哈希函数可能产生的冲突。原则上，再哈希可以继续到其他级别，直到冲突解决。但在实