【UCB CS 61B SP24】Lecture 19 20: Hashing Hashing II 学习笔记

本文首先介绍了哈希表中的两大关键概念：哈希函数与哈希码，并使用 Java 实现了一个通过链地址法解决哈希冲突的哈希表。

1. 哈希函数与哈希码

1.1 动态多列表实现整数集合

我们在 Lecture 11 中第一次介绍了集合（Set），并且用数组实现了一个 ArraySet。但是每次查询都需要遍历一边数组，有没有办法在这中数据结构的基础上对效率进行优化？

假设我们现在考虑实现一个仅存放整数的集合，如果我们用 10 个数组来存放整数（记为 $M=10$），根据键的最后一位数字将其放入对应的数组中：

这样如果我们的键大小在 $0\sim 9$ 之间那么理论上插入与查找的效率为 $O(1)$，如果键大小在 $0\sim 99$ 之间那么理论上效率会慢 10 倍。

那么随着键大小范围的变化我们设定的 $M$ 也跟着变化是不是能保持这种高效的效果？有没有通用的方式来表示类似“键的最后一位数字”这种说法？其实这在整数中的通用表示就是取模操作：

这样我们就能让这种方法适用于任何 $M$ 的情况，即：$key\%M$。为了保持高效的时间复杂度，我们需要 $N/M$ 小于某个常数 $k$。有两种方法来维持：

• 当最长的数组长度超过 $k$ 时增加 $M$，这种办法一般会产生很多空数组，所以不使用；
• 当所有数组的平均大小超过 $k$ 时，增加 $M$。

与以前讲到过的动态数组扩容原理相似，在增加 $M$ 时，最好的方式就是每次将其翻倍，我们来看一个例子：

1.2 字符串集合

我们已经有方法将数字分别映射到不同的数组中了，如果我们像存字符串怎么办？其中一种方法是我们可以将字符串的首字符映射为数字（假设只考虑小写字母），例如：$a=0,b=1,\dots ,z=25$。那么此时如果我们要存入 cat，就可以放入 2 号数组中。

如果扩容了集合，那么同理我们可以考虑前两个字符，例如：$aa=0,ab=1,\dots ,zz=675$。但是这样做有什么问题？

• 这样并不满足随机分布，因为某些字母在单词中作为前缀的概率远大于其他字母，例如 aa 作为单词前缀基本很少；
• 当扩容集合后，小于前缀长度的单词如何映射，例如单字符单词 a。

这种方法最大的问题是我们让集合负责计算如何对字符串进行分类，但这不应该是集合的工作，否则集合就必须知道存在的每一个对象（包括尚未构建的对象），以及如何对它们进行分类。

集合在处理整型时是最灵活的，所以我们可以让集合只对整型起作用，那么我们就需要定义一个方法 int f(String s)，该方法能够将字符串转换为整型，然后将字符串 s 存在 f(s) 对应的位置中。这种方法我们称其为哈希函数（Hash Function）。

常见哈希函数如下：

• 除留余数法：hash(key) = key % capacity（适合整数键）。
• 乘法哈希：hash(key) = floor(capacity * (key * A % 1))（A 为黄金分割比例）。
• 多项式滚动哈希：用于字符串（如 hash("abc") = a * P² + b * P + c，P 为质数）。
• 加密哈希：如 SHA-256（用于分布式系统，但速度慢）。

将字符串映射到整数最佳的哈希函数为多项式滚动哈希，首先还是利用之前最初提到的思路，先用 26 进制将每个字母映射到 $1\sim 26$ 这 26 个整数上，然后我们可以用下面这个公式进行映射，还是以 cat 为例：

$$f(cat)=3\ast 26^2+1\ast 26^1+20\ast 26^0=2074$$

这种哈希方式同样适用于整数字符串：

$$f(7901)=7\ast 10^3+9\ast 10^2+0\ast 10^1+1\ast 10^0=7901$$

但是我们比较整数与字符串，能够发现他们还是有一点区别的，那就是在整数中 000 与 0 相同，而在字符串中 aaa 与 a 明显不相同，如果 $a=0$ 似乎不太合理，$a=1$ 就能避免这个问题，因此可以将所有字符的映射关系加一，这就是为什么我们前面说将每个字母映射到 $1\sim 26$ 上。

现在每个字符串就能唯一对应一个整数：

1.3 哈希码

但是字符串中除了小写字母之外可能还有大写字母、数字、标点符号之类的字符，如果我们希望将每个可能的字符串映射到唯一的整数上，那么就需要为每个可能的字符分配一个整数，我们可以之间用 ASCII 码来表示这种字符与整数的映射关系。

如果字符串还要兼容汉字字符怎么办？还有一种 Unicode 码能够表示这些字符。但是如果我们的字符串太长或者要使用 Unicode 这种大型的编码当字符串转换成整数后可能这个数会非常大，计算机无法表示这么大的数，这样就会发生整数溢出（Integer Overflow）。

例如在 Java 中，最大的整数为 2147483647：

int x = 2147483647;
System.out.println(x);  // 2147483647
System.out.println(x + 1);  // -2147483648

我们需要将溢出的数转换到一个固定的更小的范围内，映射后的结果我们就称其为哈希码（Hash Code）。哈希码（Hash Code）是一个整数值，用于表示对象的某种“摘要”或“标识”。它是通过哈希函数（Hash Function）计算得到的，核心作用是将任意大小的数据映射到固定大小的整数空间。

哈希码的核心目的是为了快速定位对象在哈希表中的存储位置，而不关注对象之间的顺序关系（如 HashMap、HashSet 的底层实现）。

完美的哈希码设计原则如下：

• 均匀性：不同对象的哈希码应尽可能分布均匀，减少冲突；
• 高效性：计算速度快，避免复杂计算（如频繁调用 hashCode() 时不应耗时）；
• 一致性：同一对象多次计算的哈希码必须相同（前提是对象未被修改）；
• 与 equals() 一致：必须保证 equals() 为 true 的对象哈希码相同。

由于哈希码的范围是有限的，我们无法将每个字符串映射到唯一的值上，在 Java 中，获取字符串哈希码的默认方法如下：

public int hashCode() {int h = 0;for (char c : value) {  // value 是 String 内部的字符数组h = 31 * h + c;  // 31 是经验选择的质数}return h;
}

我们可以来测试一下字符串的默认哈希码：

package CS61B.Lecture19;public class HashCode {public static void main(String[] args) {System.out.println("cat".hashCode());  // 98262System.out.println('c' * (int) Math.pow(31, 2) + 'a' * 31 + 't');  // 98262}
}

为什么 Java 这里选择 31 来计算哈希码？31 是奇质数，乘法操作可优化为 (h << 5) - h（即 31 * h = 32 * h - h），提升计算效率；其次经验表明 31 能较好平衡冲突率和计算速度。

1.4 hashCode() 与 equals()

Java 中所有对象的哈希码默认基于对象的内存地址（但不完全等价于地址）获得，通过 Object.hashCode() 方法生成，该方法的默认实现是本地方法（Native）：

public class Object {public native int hashCode();  // 默认实现与内存地址相关
}

其特性如下：

• 两个不同对象的默认哈希码大概率不同。
• 若未重写 hashCode()，同一对象的哈希码在其生命周期内不变（即使对象内容变化）。

Java 规定，若重写 equals() 方法，必须同时重写 hashCode() 方法，且需满足以下条件：

• 一致性：若 a.equals(b) == true，则 a.hashCode() == b.hashCode()。
• 逆否命题：若 a.hashCode() != b.hashCode()，则 a.equals(b) 必须为 false。
• 不唯一性：不同对象允许有相同哈希码（哈希冲突是允许的）。

既然所有对象都默认拥有哈希函数，为什么我们还要重写 hashCode() 方法？因为若两个对象 equals() 为 true 但哈希码不同，存入哈希表时会被分配到不同桶，导致无法正确检索或去重：

package CS61B.Lecture19;import java.util.HashSet;
import java.util.Set;class Person {private String name;private int age;public Person(String name, int age) {this.name = name;this.age = age;}@Overridepublic boolean equals(Object obj) {if (obj instanceof Person person)return name.equals(person.name) && age == person.age;return false;}@Overridepublic int hashCode() {return (name + age).hashCode();}
}public class HashCode {public static void main(String[] args) {Person p1 = new Person("Alice", 25);Person p2 = new Person("Alice", 25);// 重写 equals() 前为 false，重写 equals() 后为 trueSystem.out.println(p1.equals(p2));// 重写 hashCode() 前为 false，重写 hashCode() 后为 trueSystem.out.println(p1.hashCode() == p2.hashCode());Set<Person> set = new HashSet<>();set.add(p1);// 只有在同时重写 equals() 与 hashCode() 后为 trueSystem.out.println(set.contains(p2));}
}

注意最后的 set.contains(p2)，只有在同时重写 equals() 与 hashCode() 后为 true，这里就需要挖一下集合比较对象是否相等的逻辑了。

在 Java 中，集合（如 HashSet）判断对象是否已存在的逻辑依赖于两个核心方法：hashCode() 和 equals()。这两个方法必须同时满足特定规则，才能确保集合确识别重复对象。如果只重写其中一个方法，会导致逻辑不一致，集合无法正确判断对象的唯一性。

以 HashSet 为例，其底层实现是基于 HashMap 的键（Key）存储。HashSet 的添加、删除和查找操作，实际是通过 HashMap 的键操作实现的。HashMap 判断键是否重复的逻辑分为两步：

• 通过 hashCode() 定位桶（Bucket）：计算键的哈希码，确定该键应存放在哪个桶中。
• 通过 equals() 比较桶内元素：如果多个键的哈希码相同（哈希冲突），则在同一个桶内遍历所有元素，调用 equals() 方法逐一比较，判断是否存在重复键。

因此，集合的正确行为依赖于以下两点：

• 相同的对象必须产生相同的哈希码（hashCode() 一致）。
• 相等的对象必须被 equals() 方法判定为 true。

2. 哈希表

2.1 基本概念

哈希表是一种通过哈希函数将键（Key）映射到数组中的特定位置（桶，Bucket）来存储键值对（Key-Value Pair）的数据结构。其核心组件如下：

• 哈希函数：将键转换为数组索引，理想情况下应均匀分布键以减少冲突。
• 冲突解决机制：处理多个键映射到同一索引的情况，常见方法包括：
  • 链地址法（Chaining）：每个桶维护一个链表或树结构，存储冲突的键值对。
  • 开放寻址法（Open Addressing）：通过线性探测、二次探测等方法寻找下一个可用桶。
• 负载因子（Load Factor）：已用桶数与总桶数的比例，触发扩容的阈值（如 0.75）。

时间复杂度分析：

• 平均情况：插入、删除、查找操作均为 $O(1)$（假设哈希函数良好且负载因子合理）。
• 最坏情况：所有键冲突，退化为链表或线性探测序列，时间复杂度 $O(n)$。

相比于之前学过的搜索树，哈希表的平均时间复杂度极低（搜索树的平均操作时间为 $O(logn)$），适合高频单点查询，且实现简单，内存紧凑（尤其开放寻址法）；但哈希表的数据是无序的，不支持范围查询，哈希函数设计也很影响性能，扩容成本高，在最坏情况下性能很差。

2.2 冲突解决机制

（1）链地址法（Separate Chaining）

• 原理：每个桶存储一个链表（或树），冲突的键值对追加到链表中。
• 实现步骤：
  1. 哈希函数计算索引 i = hash(key)。
  2. 若桶 i 为空，直接插入键值对。
  3. 若冲突，遍历链表查找键是否存在，存在则更新值，不存在则追加新节点。
• 优化：链表转红黑树，即当链表长度超过阈值（如 Java 8 的 HashMap 中阈值为 8），转为红黑树，避免链表过长导致查询退化为 $O(n)$。
• 优点：实现简单，负载因子容忍度高（可超过 1）。
• 缺点：内存开销大（存储链表指针），缓存不友好。

（2）开放寻址法（Open Addressing）

• 原理：所有键值对直接存储在数组中，冲突时按规则探测下一个可用桶。
• 实现方式：
  1. 线性探测（Linear Probing）
     • 探测公式：index = (hash(key) + i) % capacity（i 为探测次数）。
     • 步骤：计算初始索引 i = hash(key)，若桶 i 为空，插入键值对；若被占用且键相同，更新值；若键不同，探测 i + 1, i + 2, ... 直到找到空桶。
     • 缺点：易产生聚集（Clustering），导致连续占用区域增大。
  2. 二次探测（Quadratic Probing）
     • 探测公式：index = (hash(key) + c1 * i + c2 * i²) % capacity（c1, c2 为常数）。
     • 优点：减少聚集现象。
     • 缺点：可能导致无法找到空桶（即使数组未满）。
  3. 双重哈希（Double Hashing）
     • 探测公式：index = (hash1(key) + i * hash2(key)) % capacity，使用第二个哈希函数 hash2 计算步长。
     • 优点：避免聚集，分布更均匀。

（3）布谷鸟哈希（Cuckoo Hashing）

• 原理：使用两个哈希表 T1, T2 和两个哈希函数 h1, h2。
• 实现步骤：
  1. 计算 h1(key) 和 h2(key)。
  2. 若 T1[h1(key)] 为空，插入键值对。
  3. 若冲突，踢出 T1 中旧键 old_key，将其插入 T2 的 h2(old_key) 位置。
  4. 若再次冲突，递归踢出，直到无冲突或达到最大循环次数（触发扩容）。
• 优点：查询最坏时间复杂度为 $O(1)$。
• 缺点：插入可能失败，需多次扩容。

2.3 Java 实现哈希表

现在我们使用链地址法（不考虑红黑树）实现一个哈希表：

package CS61B.Lecture19;public class MyHashMap<K extends Comparable<K>, V> {private static class Node<K, V> {K key;V value;Node<K, V> next;public Node(K key, V value, Node<K, V> next) {this.key = key;this.value = value;this.next = next;}}private static final int DEFAULT_INITIAL_CAPACITY = 16;  // 默认初始容量private static final double DEFAULT_LOAD_FACTOR = 0.75;  // 默认负载因子private Node<K, V>[] hashTable;private int size;  // 当前容量private int threshold;  // 扩容阈值public MyHashMap() {this(DEFAULT_INITIAL_CAPACITY);}public MyHashMap(int initialCapacity) {hashTable = (Node<K, V>[]) new Node[initialCapacity];size = 0;threshold = (int) (initialCapacity * DEFAULT_LOAD_FACTOR);}/** 核心操作：添加，若 key 已存在则更新 value 后返回旧的 value，否则添加新键值对后返回 null */public V put(K key, V value) {if (size >= threshold) resize();  // 当前容量达到阈值则先扩容int idx = hash(key) % hashTable.length;  // 桶的索引，如果容量固定是 2 的幂次可以写成 hash(key) & (hashTable.length - 1) 加速取模运算Node<K, V> p = hashTable[idx];while (p != null) {if (p.key.equals(key)) {  // key 已存在，只更新 valueV oldValue = p.value;p.value = value;return oldValue;}p = p.next;}// key 不存在，则使用头插法将新键值对插入到桶的首部，如果使用尾插法则每次插入都要遍历一次桶hashTable[idx] = new Node<>(key, value, hashTable[idx]);size++;return null;}/** 将容量扩容至原来的两倍 */private void resize() {int newCapacity = hashTable.length << 1;Node<K, V>[] newHashTable = (Node<K, V>[]) new Node[newCapacity];// 遍历旧哈希表中的所有元素，重新计算哈希码后添加到新哈希表中for (Node<K, V> p : hashTable) {while (p != null) {int newIdx = hash(p.key) % newCapacity;p.next = newHashTable[newIdx];  // 头插法newHashTable[newIdx] = p;p = p.next;}}threshold = (int) (newCapacity * DEFAULT_LOAD_FACTOR);hashTable = newHashTable;}/** 哈希函数 */private int hash(K key) {if (key == null) return 0;  // 允许 null 键（存放在第 0 个桶）int h = key.hashCode();return h ^ (h >>> 16);  // 高位与低位混合，以减少哈希冲突}/** 核心操作：查找，若 key 存在则返回其对应的 value，否则返回 null */public V get(K key) {int idx = hash(key) % hashTable.length;Node<K, V> p = hashTable[idx];while (p != null) {if (p.key.equals(key)) return p.value;p = p.next;}return null;}/** 核心操作：删除，若 key 存在则删除键值对后返回其 value，否则返回 null */public V remove(K key) {int idx = hash(key) % hashTable.length;Node<K, V> cur = hashTable[idx];Node<K, V> prev = null;while (cur != null) {if (cur.key.equals(key)) {if (prev == null) {  // 注意需要判断删除的键是否为头节点hashTable[idx] = cur.next;} else {prev.next = cur.next;}size--;return cur.value;}prev = cur;cur = cur.next;}return null;}/** 获取大小 */public int size() {return size;}/** 是否为空 */public boolean isEmpty() {return size == 0;}/** 测试 */public static void main(String[] args) {MyHashMap<String, Integer> map = new MyHashMap<>();// 添加测试map.put("Apple", 5);map.put("Banana", 3);map.put("Cherry", 10);map.put("Banana", 30);System.out.println(map.get("Cherry"));  // 10System.out.println(map.get("Banana"));  // 30// 删除测试System.out.println(map.remove("Banana"));  // 30System.out.println(map.get("Banana"));  // nullSystem.out.println(map.size());  // 2// 扩容测试for (int i = 0; i < 26; i++) map.put(String.valueOf((char) (i + 'A')), i);System.out.println(map.get("K"));  // 10System.out.println(map.size());  // 28}
}

注意我们的哈希函数 hash() 中使用 h ^ (h >>> 16)（其中 >>> 为无符号右移运算，而 >> 为带符号右移运算）来求解哈希码的原因是因为将 hashCode() 方法获得的哈希码高位与低位混合，目的是将哈希码的高 16 位信息“扩散”到低 16 位，使得低位更随机，这样能够减少哈希冲突。使用 h >>> 16 可以确保高位补 0，无论原哈希码是正还是负，混合后的结果更均匀；如果使用 h >> 16，负数的符号位会污染高位，导致混合后的值仍偏向负数。Java 8 的 HashMap 中的哈希函数如下：

static final int hash(Object key) {int h = key.hashCode();return (h == 0) ? 0 : h ^ (h >>> 16);  // 高位与低位异或
}

其计算桶索引的流程如下，注意如果容量固定是 2 的幂次可以写成 hashCode & (hashTable.length - 1) 来加速取模运算：

3. 可变对象与不可变对象

可变对象（Mutable Objects）是指对象创建后，其状态可通过公共方法（如 setter）被修改，例如 Java 中的 ArrayList、StringBuilder，可变对象的潜在风险如下：

• 状态意外修改：对象可能被外部代码或线程意外修改。
• 哈希表失效：若对象作为集合的键，修改后哈希码变化，导致无法正确检索。
• 并发问题：多线程同时修改状态可能导致数据竞争（Data Race）。

不可变对象（Immutable Objects）的状态在创建后无法被修改。所有字段被声明为 final，且不提供修改内部状态的方法（如 setter），例如 Java 中的 String、Integer、LocalDateTime，不可变对象的特点如下：

• 线程安全：无需同步，多线程共享时不会出现状态不一致。
• 哈希表友好：哈希码在对象生命周期内不变，适合作为集合的键。
• 可缓存性：无需担心被修改，可安全缓存。

我们看一下如果在集合中存入的是可变对象会有什么后果：

package CS61B.Lecture19;import java.util.*;public class MutableObjectDemo {public static void main(String[] args) {List<Integer> items = new ArrayList<>(List.of(0, 1));Set<List<Integer>> st = new HashSet<>();st.add(items);st.add(List.of(1, 2));System.out.println(items.hashCode());  // 962items.add(7);System.out.println(items.hashCode());  // 29829System.out.println(st.contains(items));  // false}
}

我们首先将一个列表 [0, 1] 添加到集合中，这时候其哈希码为 962，假设此时我们的集合容量为 4，那么可以计算出桶的索引为：$962\%4=2$。但是由于 List 是可变对象，我们将其加入集合后再往列表中添加一个元素后其哈希码就改变了，当我们再向集合中查询 [0, 1, 7] 时计算出的桶索引为：$29829\%4=1$，而在 1 号桶中肯定是永远找不到列表 [0, 1, 7] 的：