哈希的认识

文章目录

• 前言
• 哈希的概念
• 哈希表数据结构
• 哈希函数
• • 直接定址法
  • 除留余数法
• 哈希冲突及解决方法
• • 闭散列(开放定址法)
  • 开散列(哈系桶 / 拉链法)

前言

哈希（Hash）是计算机科学中一种极其重要的思想和技术，它通过一个函数（哈希函数）将任意长度的数据映射到一个固定长度的值（哈希值）。这个值通常用作数据的索引，从而实现快速查找、数据校验等目的。

哈希的概念

哈希（Hash），又称散列，是一种将输入（键）通过哈希函数转换为固定长度输出（哈希值）的过程。这个输出通常是一个整数。哈希函数具有以下性质：

• 确定性：相同的输入必须产生相同的输出。
• 高效性：计算过程必须快速。
• 均匀性：理想情况下，不同的输入应均匀地映射到输出空间，减少冲突。

哈希最常见的应用是哈希表（Hash Table），它利用哈希值作为数组下标来存储数据，从而实现近乎常数时间的查找、插入和删除操作。

例如： 待插入数据集合为：{1，7，6，4，5，9}; 哈希函数为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

capacity = 10， hash(1)= 1%10=1 hash(7)=7%10=7 hash(6)= 6%10= 6 hash(4)=4%10=4 hash(5)= 5%10=5 hash(9)= 9%10 =9

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，但当我们向集合中插入元素44时，会出现什么问题？元素44与元素4通过该哈希函数得到的哈希值是相同的，此时出现了哈希冲突！

哈希表数据结构

哈希表是一种根据键直接访问内存位置的数据结构。它由两个主要部分组成：

• 桶数组（Bucket Array）：一块连续的内存空间，每个位置称为一个桶。
• 哈希函数：将键映射到桶的索引。

当我们插入一个键值对时，先计算键的哈希值，然后通过哈希函数得到桶的索引，将值存入该桶。查找时同样计算哈希值，直接定位到桶。

哈希函数

哈希函数的目标是让键均匀分布在桶中。常用的哈希函数有：

直接定址法

哈希函数为 H(key) = a*key + b，其中a和b为常数。适用于关键字分布基本连续的情况，可以避免冲突，但若关键字不连续，会造成空间浪费。 通常a=1，b=0是最简单的形式，即H(key)=key；

• 优点：简单、不会产生冲突（如果关键字不重复），查找效率最高 O(1)。
• 缺点：要求关键字集合中的值连续且分布范围不大。如果关键字不连续（如 1, 100, 1000），会导致大量空位，浪费存储空间。
• 适用：适用于关键字分布基本连续且范围较小的静态集合，如学号从 2023001~2023100 的学生记录。

除留余数法

哈希函数为 H(key) = key % p，其中p通常为小于或等于表长的质数或素数。这种方法简单，适用范围广，但可能产生冲突，需要处理冲突。需要选择合适的p以减少冲突。

• 优点：计算简单，适用范围广，关键字可以是整数、字符串（先转换为整数）等。
• 缺点：会产生冲突（不同关键字映射到同一地址），需要配合冲突解决策略（如链地址法、开放地址法）。
• 适用：绝大多数哈希表实现采用此方法（如 C++ unordered_set/map 的哈希函数底层会结合其他混合算法，但基本思想基于取模）。

哈希冲突及解决方法

负载因子： α = 元素个数 / 桶数。它反映了哈希表的填充程度。当 α 过大时，冲突概率增加，性能下降。通常实现中会设定一个阈值（如 0.75），当 α 超过阈值时，进行重哈希（rehash）：将桶数组扩大（通常翻倍）并重新计算所有元素的哈希索引，插入新表。重哈希是 O(n) 的操作，但均摊后仍为 O(1)。

由于键的数量可能远大于桶的数量，多个键可能被映射到同一个桶，这称为哈希冲突。冲突处理是哈希表设计的核心。常见方法有：

闭散列(开放定址法)

所有元素都存储在桶数组本身，每个桶要么空，要么存有元素。当冲突发生时，按照某种规则寻找下一个空闲桶。开放地址法必须保证负载因子小于1（通常 ≤0.75），否则性能急剧下降。删除元素时需要特殊标记（如“已删除”），不能直接置空，否则会破坏探测链。 通过一个探测序列在表中寻找下一个空闲桶。探测序列由哈希函数和步长决定。通用的探测函数形式为： H(key) = (H(key) + f(i)) mod m;

• H(key) 是初始哈希地址（如除留余数法）
• i是探测次数(i = 0, 1, 2…)
• f(i) 是偏移量函数，决定了探测序列
• m是表长

常见探查方式有：

线性探测的偏移量函数为：f(i)=i，即第 i 次探测的位置为：H(key) = (H(key) + i) mod m； 也就是说，如果 H(key) 被占，就检查下一个位置 H(key) + 1，再下一个 H(key) + 2…直到找到空位或遍历全表。 例如： 哈希表： 待插入数据集合：{10，20，30}； 依次插入关键字：10（地址0）、20（地址0冲突，探测0→1空闲）、30（地址1冲突，探测0→1被占→2空闲）。过程： 10 → 0 20 → 0冲突，i=1 → 1（空）插入 30 → 0冲突，i=1 → 1被占，i=2 → 2（空）插入

**优点：**实现简单，只需顺序扫描，且连续访问内存。 **缺点：**当多个关键字映射到同一片连续区域时，它们会堆积成连续的占用块，使得后续需要插入该区域或附近的关键字需要探测很长距离，导致查找效率下降

二次探测的偏移量函数为：f(i)=i*i，即第 i 次探测的位置为：H(key) = (H(key) + i*i) mod m；

例如： 哈希表： 待插入数据集合：{10，20，30}； 依次插入关键字：10（地址0）、20（地址0冲突，探测0→1空闲）、30（地址1冲突，探测0→1被占→4空闲）。过程： 10 → 0 20 → 0冲突，i=1 → 1（空）插入 30 → 0冲突，i=1 → 1被占，i=2 → 4（空）插入

开散列(哈系桶 / 拉链法)

该方法是解决哈希冲突的一种经典方法。它的核心思想是：将哈希表的每个桶（bucket）看作一个链表的头节点（或更复杂的数据结构），所有哈希地址相同的元素都存储在同一个桶的链表中。这样，即使多个关键字映射到同一个位置，它们也能被依次保存下来。

在开散列中，负载因子 α 可以大于 1（因为链表可以无限长）。但为了保持平均查找时间较短，通常控制 α 在 1 左右。

哈希表：

待插入数据集合：{10，20，15，35，66，16，1000，17}；

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

优点：

• 空间利用率高：桶数组可以适度稀疏，装载因子可以大于 1，不会像开放地址法那样因装载因子接近 1 而性能剧降。
• 无聚集现象：不同桶之间完全独立，不会产生开放地址法中的一次聚集或二次聚集。
• 适合动态增长：扩容时只需重新分配桶数组，链表中的节点可以复用，无需移动节点内容（仅改变桶指针指向）。

缺点：

• 额外内存开销：每个节点需要存储指针（通常 4 或 8 字节），对于小对象可能浪费较多内存。
• 最坏情况性能差：若哈希函数不佳，链表可能变得很长，导致 O(n) 操作。
• 缓存不友好：链表节点在内存中不一定连续，遍历时可能多次缓存缺失，速度比开放地址法的连续数组慢。