【学习笔记】数据结构与算法04：哈希表、哈希冲突、哈希算法

知识出处：Hello算法：https://www.hello-algo.com/

文章目录

- 2.3 哈希表
- - 2.3.1 哈希表「 hash table」
  - - 2.3.1.1 哈希表常见操作
    - 2.3.1.2 哈希表的简单实现
    - 2.3.1.3 哈希冲突与扩容
  - 2.3.2 哈希冲突
  - - 2.3.2.1 「链式地址 separate chaining」
    - 2.3.2.2 「开放寻址 open addressing」
    - - **线性探测**
      - 平方探测
      - 多次哈希

2.3 哈希表

2.3.1 哈希表「 hash table」

又称「散列表」，通过建立键 key 与值 value 之间的映射，实现高效的元素查询。

哈希表的抽象表示

哈希表的查询、添加、删除元素的时间复杂度均为 O(1) ，非常高效。对比链表、数组如下：

思考：哈希表底层实现是数组、链表、二叉树，但为什么效率可以比它们更高呢？

A：首先，哈希表的时间效率变高，但空间效率变低了。哈希表本身需要更多的空间，而且相当一部分内存未使用。

其次，只是在特定使用场景下时间效率变高了。如果一个功能能够在相同的时间复杂度下使用数组或链表实现，那么通常比哈希表更快。这是因为哈希函数计算需要开销，时间复杂度的常数项更大。

因为是用到了函数渐进上界的数学思想去计算时间复杂度，在实际场景中，输入n不大时，常数项对耗时的影响还是比较大的，这也是为什么会反直觉的原因

2.3.1.1 哈希表常见操作

常见操作包括：初始化、查询操作、添加键值对和删除键值对。

有三种常用的遍历方式：遍历键值对KV、遍历键KEY和遍历值VALUE

Java中提供了Map接口和极其丰富的实现类，用比较常用的HashMap举例：

/* 初始化哈希表 */
Map<Integer, String> map = new HashMap<>();

/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");
System.out.println("\n添加完成后，哈希表为\nKey -> Value");
PrintUtil.printHashMap(map);

/* 查询操作 */
// 向哈希表中输入键 key ，得到值 value
String name = map.get(15937);
System.out.println("\n输入学号 15937 ，查询到姓名 " + name);

/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);
System.out.println("\n删除 10583 后，哈希表为\nKey -> Value");
PrintUtil.printHashMap(map);

/* 遍历哈希表 */
System.out.println("\n遍历键值对 Key->Value");
for (Map.Entry<Integer, String> kv : map.entrySet()) {
    System.out.println(kv.getKey() + " -> " + kv.getValue());
}
System.out.println("\n单独遍历键 Key");
for (int key : map.keySet()) {
    System.out.println(key);
}
System.out.println("\n单独遍历值 Value");
for (String val : map.values()) {
    System.out.println(val);
}

2.3.1.2 哈希表的简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。

将数组中的每个空位称为「桶 bucket」，每个桶可存储一个键值对。（查询操作就是通过key找到桶bucket
如何基于 key 定位对应的桶呢？这是通过**「哈希函数 hash function」**实现的。（哈希函数是一个单向的映射函数，可以将一个较大的输入空间映射到一个较小的输出空间。
在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。
换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

哈希函数工作原理

2.3.1.3 哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。当出现这种情况，就叫「哈希冲突 hash collision」。

哈希冲突示例

最简单的解决方法，就是通过扩容来实现，理论上，输出空间越接近输入空间，出现哈希冲突的几率就更小

最极端的情况，直接将value作为key存储，时间会从O(1)劣化到O(n)

但是缺点也很明显，哈希扩容类似数组扩容，也是需要迁移到新表才能实现，非常耗时空。而且每次扩容都意味着需要使用新的哈希函数重新计算，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。

例如在 Java 中，当负载因子超过 0.75 时，系统会将哈希表扩容至原先的 2 倍。

2.3.2 哈希冲突

前面提到，解决哈希冲突可以通过直接暴力扩容解决，但是效率低下，为了提高效率，我们可以采用以下策略。

改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。

哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。

2.3.2.1 「链式地址 separate chaining」

将原始哈希表中，每个桶的值转换为链表的形式，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。

链式地址哈希表

操作变化

查询元素：输入 key ，经过哈希函数得到桶索引，即可访问链表头节点，然后遍历链表并对比 key 以查找目标键值对。
添加元素：首先通过哈希函数访问链表头节点，然后将节点（键值对）添加到链表尾部。
删除元素：根据哈希函数的结果访问链表头部，接着遍历链表以查找目标节点并将其删除。

局限性

链式地址存在以下局限性。

占用空间增大：链表包含节点指针，它相比数组更加耗费内存空间。
查询效率降低：因为需要线性遍历链表来查找对应元素。（值得注意的是，当链表很长时，查询效率 O(n) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 O(log⁡n) 。

2.3.2.2 「开放寻址 open addressing」

当出现哈希冲突时，「开放寻址 open addressing」不引入额外的数据结构，而是通过“多次探测”来处理哈希冲突（按照一定的规则向后探测/查找空桶并存入），根据探测规则的不同探测方式主要包括线性探测、平方探测和多次哈希等。

三者特点差不多，以线性探测为例进行分析。

线性探测

线性探测采用固定步长的线性搜索来进行探测，其操作方法与普通哈希表有所不同。

在开放寻址中删除元素导致的查询问题

插入元素：

通过哈希函数计算桶索引，若没有元素，则进行正常插入。
若发现桶内已有元素（哈希冲突），则从冲突位置向后线性遍历（步长通常为 1 ），直至找到空桶，将元素插入其中。

查找元素：

通过哈希函数计算桶索引，找到键值对进行匹配，成功则返回value
若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；
如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

删除元素：

不难发现，使用开放寻址的哈希表是不能直接删除元素的。直接删除查询到的元素会导致寻址规则被破坏。
为了解决该问题，我们可以采用「懒删除 lazy deletion」机制：它不直接从哈希表中移除元素，而是利用一个常量 TOMBSTONE(也可以理解为删除标记) 来标记这个桶。
然而，懒删除可能会加速哈希表的性能退化。

聚集现象

线性探测容易产生“聚集现象”。具体来说，数组中连续被占用的位置越长，这些连续位置发生哈希冲突的可能性越大，从而进一步促使该位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

平方探测

平方探测与线性探测类似，当发生冲突时，而是跳过“探测次数的平方”的步数（ 1,4,9,… 步）

平方探测主要具有以下优势。

平方探测通过跳过探测次数平方的距离，试图缓解线性探测的聚集效应。
平方探测会跳过更大的距离来寻找空位置，有助于数据分布得更加均匀。

然而，平方探测并不是完美的。

仍然存在聚集现象，即某些位置比其他位置更容易被占用。
空间利用不完全，由于平方的增长，平方探测可能不会探测整个哈希表，这意味着即使哈希表中有空桶，平方探测也可能无法访问到它。

多次哈希

顾名思义，多次哈希方法使用多个哈希函数 f1(x)、f2(x)、f3(x)、… 进行探测。

插入元素：若哈希函数 f1(x) 出现冲突，则尝试 f2(x) ，以此类推，直到找到空位后插入元素。
查找元素：在相同的哈希函数顺序下进行查找，直到找到目标元素时返回；若遇到空位或已尝试所有哈希函数，说明哈希表中不存在该元素，则返回 None 。

与线性探测相比，多次哈希方法不易产生聚集，但多个哈希函数会带来额外的计算量。

Tip：

Java 采用链式地址。自 JDK 1.8 以来，当 HashMap 内数组长度达到 64 且链表长度达到 8 时，链表会转换为红黑树以提升查找性能。

哈希算法

无论是开放寻址还是链式地址，它们只能保证哈希表可以在发生冲突时正常工作，而无法减少哈希冲突的发生。

如果哈希冲突过于频繁，哈希表的性能则会急剧劣化。理想情况下键值对均匀分布在各个桶中，达到最佳查询效率，而键值对的分布情况由哈希函数决定。也就说：

当哈希表容量 capacity 固定时，哈希算法 hash() 决定了输出值，进而决定了键值对在哈希表中的分布情况。

哈希算法的目标

为了实现“既快又稳”的哈希表数据结构，哈希算法不能只是简单取余计算，一个优秀哈希算法应具备以下特点。

确定性。相同的输入，哈希算法始终只产生相同的输出，这样才能保证可靠性
效率高。计算花销越小越好，速度越快越好（对比一些加密算法，会要求足够多的计算以保证准确
均匀分布：哈希算法应使得键值对均匀分布在哈希表中。分布越均匀，哈希冲突的概率就越低。

Tip：哈希算法作为一种加密算法，也可以在其他领域发挥作用：比如密码加密，或者验证数据完整性。而对于密码学相关应用，为了防止根据哈希值反推出原始密码的逆向工程，哈希算法则需要兼备更高级的特点：

单向性：无法通过哈希值反推出关于输入数据的任何信息。
抗碰撞性：应当极难找到两个不同的输入，使得它们的哈希值相同。
雪崩效应：输入的微小变化应当导致输出的显著且不可预测的变化。

哈希算法的设计

一些简单的哈希算法思路：

加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值。
乘法哈希：利用乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中。
异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。
旋转哈希：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作。

常见哈希算法

不难发现，以上介绍的简单哈希算法都比较“脆弱”，远远没有达到哈希算法的设计目标。

在实际中，我们通常会用一些标准哈希算法，例如 MD5、SHA-1、SHA-2 和 SHA-3 等。它们可以将任意长度的输入数据映射到恒定长度的哈希值。

Java内置了MD5加密和SHA-1的、SHA-256、SHA-384、SHA-512型哈希算法，但实际的hashmap计算远比这些复杂

数据结构的哈希值

哈希表的 key 可以是整数、小数或字符串等数据类型。编程语言通常会为这些数据类型提供内置的哈希算法，用于计算哈希表中的桶索引。

整数和布尔量的哈希值就是其本身。
浮点数和字符串的哈希值计算较为复杂，有兴趣的读者请自行学习。
数组的哈希值是对其中每一个元素进行哈希，然后将这些哈希值组合起来，得到单一的哈希值。
对象的哈希值基于其内存地址生成。通过重写对象的哈希方法，可实现基于内容生成哈希值。

int num = 3;
int hashNum = Integer.hashCode(num);
// 整数 3 的哈希值为 3

boolean bol = true;
int hashBol = Boolean.hashCode(bol);
// 布尔量 true 的哈希值为 1231

double dec = 3.14159;
int hashDec = Double.hashCode(dec);
// 小数 3.14159 的哈希值为 -1340954729

String str = "Hello 算法";
int hashStr = str.hashCode();
// 字符串“Hello 算法”的哈希值为 -727081396

Object[] arr = { 12836, "小哈" };
int hashTup = Arrays.hashCode(arr);
// 数组 [12836, 小哈] 的哈希值为 1151158

ListNode obj = new ListNode(0);
int hashObj = obj.hashCode();
// 节点对象 utils.ListNode@7dc5e7b4 的哈希值为 2110121908