哈希表：链式哈希与线性探测的深入解析

### 哈希表：链式哈希与线性探测的深入解析 #### 1. 哈希表简介 哈希表是一种高效存储少量整数的数据结构，这些整数来自一个较大的范围 $U = \{0, ..., 2^w - 1\}$。哈希表涵盖了广泛的数据结构类型，这里主要介绍两种常见的实现方式：链式哈希表（ChainedHashTable）和线性探测哈希表（LinearHashTable）。 当哈希表存储非整数类型的数据时，会为每个数据项关联一个整数哈希码，并在哈希表中使用该哈希码。 #### 2. 链式哈希表（ChainedHashTable） ##### 2.1 基本结构 链式哈希表使用一个列表数组 `t` 来存储数据，整数 `n` 用于记录所有列表中的总项数。数据项 `x` 的哈希值 `hash(x)` 范围是 $\{0, ..., t.length - 1\}$，所有哈希值为 `i` 的项都存储在 `t[i]` 列表中。为确保列表不会过长，维持不变式 $n \leq t.length$，使得每个列表中存储的平均元素数 $n/t.length \leq 1$。 ```java ChainedHashTable List<T>[] t; int n; ``` ##### 2.2 操作方法 - **添加元素（add）**： 1. 检查元素是否已存在，若存在则返回 `false`。 2. 若 `n + 1 > t.length`，则对 `t` 进行扩容。 3. 计算元素的哈希值 `i`，将元素追加到 `t[i]` 列表中，并将 `n` 加 1。 4. 返回 `true`。 ```java ChainedHashTable boolean add(T x) { if (find(x) != null) return false; if (n+1 > t.length) resize(); t[hash(x)].add(x); n++; return true; } ``` - **移除元素（remove）**： 1. 遍历 `t[hash(x)]` 列表，找到元素 `x` 并移除。 2. 若找到并移除，将 `n` 减 1 并返回该元素；若未找到，返回 `null`。 ```java ChainedHashTable T remove(T x) { Iterator<T> it = t[hash(x)].iterator(); while (it.hasNext()) { T y = it.next(); if (y.equals(x)) { it.remove(); n--; return y; } } return null; } ``` - **查找元素（find）**： 1. 对 `t[hash(x)]` 列表进行线性搜索。 2. 若找到元素 `x` 则返回该元素，若未找到则返回 `null`。 ```java ChainedHashTable T find(Object x) { for (T y : t[hash(x)]) if (y.equals(x)) return y; return null; } ``` ##### 2.3 乘法哈希（Multiplicative Hashing） 乘法哈希是一种基于模运算和整数除法生成哈希值的高效方法。使用大小为 $2^d$ 的哈希表，哈希公式为： $hash(x) = ((z \cdot x) \mod 2^w) \div 2^{w - d}$ 其中，`z` 是在 $\{1, ..., 2^w - 1\}$ 中随机选择的奇数。 ```java ChainedHashTable int hash(Object x) { return (z * x.hashCode()) >>> (w-d); } ``` 相关引理： - **引理 5.1**：对于任意两个不同的值 $x$ 和 $y$，$Pr\{hash(x) = hash(y)\} \leq 2/2^d$。 - **引理 5.2**：对于任何数据值 `x`，列表 `t[hash(x)]` 的期望长度至多为 $n_x + 2$，其中 $n_x$ 是 `x` 在哈希表中出现的次数。 ##### 2.4 性能总结 链式哈希表实现了 USet 接口。忽略扩容成本，链式哈希表支持 `add(x)`、`remove(x)` 和 `find(x)` 操作，每个操作的期望时间复杂度为 $O(1)$。从空的链式哈希表开始，任何 $m$ 次 `add(x)` 和 `remove(x)` 操作序列在所有扩容调用中总共花费的时间为 $O(m)$。 ```mermaid graph TD; A[开始] --> B{元素是否存在}; B -- 是 --> C[返回 false]; B -- 否 --> D{是否需要扩容}; D -- 是 --> E[扩容]; D -- 否 --> F[计算哈希值]; E --> F; F --> G[添加元素到列表]; G --> H[更新 n]; ```