【UCBCS61BSP24】Lecture1920:HashingHashingII学习笔记

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

1. 哈希函数与哈希码 1.1 动态多列表实现整数集合

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

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

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

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

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

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

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

1.2 字符串集合

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

如果扩容了集合，那么同理我们可以考虑前两个字符，例如： a a = 0 , a b = 1 , … , z z = 675 aa = 0, ab = 1, \dots, zz = 675 aa=0,ab=1,…,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 ∼ 26 1\sim 26 1∼26 这 26 个整数上，然后我们可以用下面这个公式进行映射，还是以 cat 为例：

f ( c a t ) = 3 ∗ 2 6 2 + 1 ∗ 2 6 1 + 20 ∗ 2 6 0 = 2074 f(cat) = 3 * 26^2 + 1 * 26^1 + 20 * 26^0 = 2074 f(cat)=3∗262+1∗261+20∗260=2074

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

f ( 7901 ) = 7 ∗ 1 0 3 + 9 ∗ 1 0 2 + 0 ∗ 1 0 1 + 1 ∗ 1 0 0 = 7901 f(7901) = 7 * 10^3 + 9 * 10^2 + 0 * 10^1 + 1 * 10^0 = 7901 f(7901)=7∗103+9∗102+0∗101+1∗100=7901

但是我们比较整数与字符串，能够发现他们还是有一点区别的，那就是在整数中 000 与 0 相同，而在字符串中 aaa 与 a 明显不相同，如果 a = 0 a = 0 a=0 似乎不太合理， a = 1 a = 1 a=1 就能避免这个问题，因此可以将所有字符的映射关系加一，这就是为什么我们前面说将每个字母映射到 1 ∼ 26 1\sim 26 1∼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()); // 98262 System.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; } @Override public boolean equals(Object obj) { if (obj instanceof Person person) return name.equals(person.name) && age == person.age; return false; } @Override public 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() 后为 true System.out.println(p1.equals(p2)); // 重写 hashCode() 前为 false，重写 hashCode() 后为 true System.out.println(p1.hashCode() == p2.hashCode()); Set<Person> set = new HashSet<>(); set.add(p1); // 只有在同时重写 equals() 与 hashCode() 后为 true System.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(1) O(1)（假设哈希函数良好且负载因子合理）。最坏情况：所有键冲突，退化为链表或线性探测序列，时间复杂度 O ( n ) O(n) O(n)。

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

2.2 冲突解决机制

（1）链地址法（Separate Chaining）

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

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

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

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

原理：使用两个哈希表 T1, T2 和两个哈希函数 h1, h2。实现步骤： 计算 h1(key) 和 h2(key)。若 T1[h1(key)] 为空，插入键值对。若冲突，踢出 T1 中旧键 old_key，将其插入 T2 的 h2(old_key) 位置。若再次冲突，递归踢出，直到无冲突或达到最大循环次数（触发扩容）。 优点：查询最坏时间复杂度为 O ( 1 ) O(1) 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 已存在，只更新 value V 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")); // 10 System.out.println(map.get("Banana")); // 30 // 删除测试 System.out.println(map.remove("Banana")); // 30 System.out.println(map.get("Banana")); // null System.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")); // 10 System.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()); // 962 items.add(7); System.out.println(items.hashCode()); // 29829 System.out.println(st.contains(items)); // false } }

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