哈希

Posted Nov 4, 2025 Updated Nov 25, 2025

By 何翌闻

42 min read

哈希

哈希就是一种索引

核心思想：哈希是一种通过一个函数（哈希函数），将任意长度的输入（如字符串、对象等），映射到一个固定长度的输出（哈希值）的技术。这个输出通常是一个整数，可以作为数组的索引。

目标：理想情况下，通过这个索引可以直接访问到目标数据，从而实现近乎 O(1) 时间复杂度的查找、插入和删除操作。

1. 哈希的总体思想

哈希（Hashing）是一种用 O(1) 常数时间存取数据的技术。

核心思想只有一句话：

用一个函数 H(key) 直接把 key 映射到数组下标 → 从而达到 O(1) 的存取效率。

传统查找的复杂度对比：

方法	查找时间	特点
顺序查找	O(n)	最慢
二分查找	O(log n)	需要有序表
哈希查找	O(1)（平均）	最快，核心是哈希函数质量

哈希表 = 一个数组，每个位置称为 桶（bucket）。

关键问题有三个：

构造一个好的哈希函数
哈希值冲突怎么处理
选择合适的装载因子 α

其中： $\alpha = \frac{n}{b}$

n = 表中元素个数
b = 桶数

α > 1 时冲突多 α < 1 越小越好（但浪费空间）

2. 哈希函数（Hash Function）

一个好的哈希函数应满足：

计算快
尽量均匀分布
尽可能减少冲突

经典方法如下。

2.1 取余法（Mod 方法）

\[H(key) = key % M\]

其中 M 一般取 小于表长的最大质数。

为什么 M 要取质数？

原因：若 M 含有小质因子（如 21=3×7），则所有含这些因子的 key 都会被映射到相同的桶的倍数上，冲突显著增大。

2.2 平方取中法（Middle-Square）

思想：

计算 key²
取其中间若干位作为哈希值
适合 key 有明显模式时使用

2.3 乘法散列法（Multiplication Method）

通用公式： $H(key) = \lfloor M({A \cdot key}) \rfloor$ 其中

A 取 0~1 的某个常数
常用黄金比例 A = 0.618…

优点：

结果分布更均匀
选择 M 不受限制（不一定要质数）

2.4 字符串的哈希

低质量版本（简单求 ASCII 和）

  
for each character c in string:
    sum += c;
return sum % tableSize;

缺点：

字符 8 个以内 → sum 范围极小 → 大量桶永远用不到 → 浪费空间

优秀版本：多项式滚动哈希

\[hashVal = c_0 + 37c_1 + 37^2c_2 + ...\]

这是广泛使用的字符串哈希标配方式。

特点：

分布非常均匀
实际可用于哈希表、字符串模式匹配（如 KMP 变体）、字典树替代等

3. 冲突（Collision）与处理方案

即：不同 key 通过 H(key) 落到了同一个桶。

开放地址法（Open Addressing）思路：如果位置被占了，就到别的位置继续查找。

3.1 线性探测（Linear Probing）

探测序列： $d, \ d+1, \ d+2, \dots$ 遇到冲突就挨个往后找。

优点：

实现最简单
命中缓存效率高（连续数组）

缺点：

产生一次性堆积（Clustering）
冲突越多，连续探测越长
最终形成一大长串连续区域 → 主聚集（Primary Clustering）

删除问题

不能直接把元素删掉，否则后续查找会断链，导致找不到本应存在的元素。

解决：

需要一个 deleted 标记（lazy deletion） 这个在 C++ 模板代码里用 empty[] 数组实现。

3.2 二次探测（Quadratic Probing）

探测序列： $d + 1^2,\ d + 2^2,\ d + 3^2, \dots$ 例子中序列为：$d+1, d+4, d+9, …$

优点：

避免一次性堆积（Clustering）

缺点：

会产生二次聚集（所有同 hash 的 key 有相同探测序列）
如果表大小 M 是质数，那么平方探测可以探测到至少一半的槽位（更准确说，能探测到 ⌈M/2⌉ 个不同位置）。如果 M是形如 4k+3 的质数，那么平方探测能探测到所有槽位。

3.3 双重散列（Double Hashing）

探测序列： $d + i \times h_2(key)$ h2 是第二个哈希函数（不能为 0）。

例如 PPT：

h1(k) = k % 10
h2(k) = R - (k % R)   // R 为小质数

优点：

探测路径几乎“随机”
避免各种聚集
是开放地址法中 效果最好的方法

缺点：

要计算两次哈希
删除仍需要 deleted 标记

再散列（Rehashing）

当表的装载因子 α 太大（典型阈值 0.7）：

必须扩容

过程：

找到下一个大质数
建立新表
将旧表所有 active 元素重新插入

PPT 示例：原表长 7 → 扩容到 17（> 14 且为质数）

分离链接法（Separate Chaining）

思路：

每个桶不是存单一元素，而是一个链表（或 vector）
一旦冲突，就将 key 插入该桶的链表

优点：

删除简单（链表删除即可）
装载因子 α 可以大于 1
不存在探测问题
实际工程中最常用的哈希表方法（例如 Java HashMap 的底层结构）

缺点：

指针链表导致缓存局部性差
内存开销大

实现思想（C++ & Java）

C++ 的线性探测 HashTable

关键结构：

ht[]：元素数组
empty[]：是否空位（处理删除用）
hSearch()：探测函数

逻辑：

若找到空位或相同 key，则返回位置
否则 j = (j+1) % D 线性探测
若一圈探测完，则表满

Java 的二次探测表（Quadratic Probing）

关键概念：

HashEntry（保存 element + isActive）
findPos() 使用二次探测
rehash() 触发扩容
insert() 会检查装载因子 > 0.5 时 rehash

链地址法版本则用 LinkedList[] 数组，实现简单。

七：配图讲解 PPT 练习题

练习 1：{4371,1323,6173,4199,4344,9679,1989}，H(x)=x%10

a. Separate Chaining 结果

桶 0~9 分别挂各自链表：

key % 10	链表（从前到后）
0	4370 类？（无）
1	4371
2	1322（无）
3	6173, 9679
4	4344
5	1323?（实际 1323 % 10 = 3，因此加入 3 桶）
9	4199,1989

你需要的话我可以画详细图。

b. 线性探测 → 最终数组状态（我可画出完整表）

c. 二次探测 → 最终数组状态

d. 双重散列 → 最终数组状态

如需我能为每个子问画全表（10×n 表格形式）并给出完整插入过程。

练习 2：HT[13]，线性探测 + 全部插入 + ASLsucc

我也可以给你完整的 13 格散列表图，以及每个 key 的探测次数、最终平均值。

总结：你学到了什么？

读完后你掌握了：

什么是哈希
哈希函数设计的所有经典方法
为什么要用质数
所有冲突处理策略（线性、二次、双重）及优缺点
再散列什么时候触发
分离链接法为什么更常用
C++ 和 Java 如何实现
章节内所有例子、表格和演算逻辑

你完全不需要 PPT，这份讲义已包含所有知识 + 额外解释，更容易理解。

如果你愿意，我可以继续为你补充：

✔ 一份 “本章精华知识点一页纸总结” ✔ 整套例题的 带图解析 ✔ 一套 可直接用于考试/作业的练习题 + 解答 ✔ 一份 Hashing 的 C++ 完整代码模板（开地址 + 链地址）

需要哪一项？

  
import java.util.Vector;
import java.util.Scanner;

/**
 * 1) 什么是哈希（Hash）？
 *    - 哈希是把任意大小的数据（key）通过哈希函数（hashCode）映射到一个整数，再把整数转换为表索引的过程。
 *    - 目的：实现接近 O(1) 的查找、插入、删除操作（平均情况）。
 *
 * 2) 为什么需要处理冲突（Collision）？
 *    - 不同的 key 经过哈希函数后可能映射到同一个索引（称为冲突）。
 *    - 常见冲突处理方法：
 *       a) 链地址法（Chaining）：在每个桶（索引）维护一个链表，把冲突的条目串起来。
 *       b) 开放寻址法（Probing）：当目标槽被占用时，按照一定探测序列找下一个空槽（线性、二次、双重哈希等）。
 *
 * 3) 本文件包含两个类：
 *    - ChainedTable<K,V>：基于链表的哈希表（链地址法），适合高负载因子时仍保持稳定，但需要额外内存用于链表节点。
 *    - ProbedTable<K,V>：基于开放寻址的哈希表（探测法），使用数组存储节点（节省内存），但表满或删除复杂。
 *
 * 4) 如何选择：
 *    - 想要实现简单、删除频繁或不想处理删除复杂性时用链式（Chaining）。
 *    - 想节省内存且负载因子较低时用开放寻址（Probing），但需要慎重设计探测函数和装载因子（load factor）。
 *
 */

/* =========================
   链地址法实现：ChainedTable
   ========================= */
class ChainedTable<K,V> {
    /**
     * Node 是链表的节点类型，用于在同一个桶（index）上串起多个键值对（key-value）。
     * 结构：
     *   K key               -> 存放键（key），哈希映射是基于 key 的 hashCode
     *   V value             -> 存放对应的值（value）
     *   Node<K,V> next      -> 指向链中的下一个节点（如果没有则为 null）
     *
     * 为何用链表？
     *   - 在冲突发生时，把多个条目连接起来，插入与查找只需遍历链表（平均条目数 = load factor）。
     *   - 插入（末尾插入或头插）很简单，不需要移动数组元素。
     */
    class Node<K,V> {
        K key;
        V value;
        Node<K,V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    /**
     * table 是一个 Vector（动态数组）用于存放每个桶的链表头（Node 或 null）。
     * 这里每个索引位置存放的并不是单个键值对，而是一个链表的起始节点。
     *
     * 注意：Vector 与 ArrayList 的差别在于 Vector 是同步的（线程安全的），但也更慢。
     *      本质上它仍然充当一个固定大小的“桶数组”。
     */
    Vector<Node<K,V>> table;

    /**
     * 构造函数 ChainedTable(int M)
     * - M 表示哈希表桶的数量（也称为容量 capacity）
     * - 一般建议 M 取质数或与哈希函数协同选择以减少冲突，但此处直接使用传入的 M。
     * - 初始化时把每个槽位设置为 null（表示链表为空）。
     *
     * 其它注意：
     * - 哈希表的性能依赖于“装载因子”（load factor = 元素数量 / M）。
     *   较大的装载因子会增加链表长度，使查找时间变慢；通常要在插入时考虑扩容（本例暂未实现自动扩容）。
     */
    ChainedTable(int M) {
        table = new Vector<>();
        for (int i = 0; i < M; i++) {
            table.addElement(null);
        }
    }

    /**
     * V lookUp(K key)
     *
     * 查找流程（求 key 对应的 value）：
     * 1) 如果 key 为 null，直接返回 null（本实现选择不支持 null 作为键）。
     * 2) 通过 getPreferredIndex(key) 得到首选桶索引 preferredIndex。
     * 3) 从 table.get(preferredIndex) 获取链表头，顺着 next 遍历链表：
     *      - 每次比较当前节点的 key 和查找 key（使用 equals），若相等则返回该节点的 value。
     *      - 遍历完链表仍未找到，返回 null（表示键不存在）。
     *
     * 复杂度：
     *  - 平均情况：O(1 + α)，α 为装载因子（平均链表长度）。
     *  - 最坏情况：O(n)（当所有键都落到同一桶并形成一条链时）。
     */
    V lookUp(K key) {
        if (key == null) {
            return null;
        }

        int preferredIndex = getPreferredIndex(key);

        Node<K,V> node = table.get(preferredIndex);
        while (node != null) {
            if (key.equals(node.key)) {
                return node.value;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * V insert(K key, V value)
     *
     * 插入（或更新）流程：
     * 1) 如果 key 为 null，返回 null（同样选择不支持 null 键）。
     * 2) 计算 preferredIndex（首选桶）。
     * 3) 遍历该桶的链表，检查是否已存在相同 key：
     *      - 若存在：保存旧值、更新节点的 value 为新值，并返回旧值（用于调用端知道这是覆盖操作）。
     * 4) 若遍历结束没有找到相同 key，说明这是新的键：
     *      - 创建新节点 newNode。
     *      - 若 prev == null —— 表示链表为空（该桶为空），直接把 newNode 放在 table[preferredIndex]。
     *      - 否则把 newNode 接到链表末尾（prev.next = newNode）。
     * 5) 返回 null 表示此前没有该键（插入成功且未覆盖任何值）。
     *
     * 注意事项与优化点：
     *  - 此处插入是把新节点放在链表末尾 —— 也可以选择头插法（把新节点放在头部，O(1) 不需遍历到末尾）。
     *    头插法会改变链表遍历顺序（新键优先出现在头部），但通常能减少插入成本。
     *  - 未实现自动扩容：当元素变多，建议扩容（例如当 load factor > 0.75 时把 M 扩大为 2*M 或下一个质数并重哈希）。
     */
    V insert(K key, V value) {
        if (key == null) {
            return null;
        }
        int preferredIndex = getPreferredIndex(key);

        // 检查是否已存在该键
        Node<K,V> node = table.get(preferredIndex);
        Node<K,V> prev = null;
        while (node != null) {
            if (key.equals(node.key)) {
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }
            prev = node;
            node = node.next;
        }

        // 键不存在，插入新节点
        Node<K,V> newNode = new Node<>(key, value);
        if (prev == null) {
            // 桶为空
            table.set(preferredIndex, newNode);
        } else {
            // 添加到链表末尾
            prev.next = newNode;
        }
        return null; // 之前没有该键
    }

    /**
     * getPreferredIndex(K key)
     *
     * 哈希索引映射细节：
     * - 这里把 Java 自带的 key.hashCode() 取绝对值（Math.abs）再对 table.size() 取模得到索引。
     * - 重要注意点：hashCode() 可能为负，所以取绝对值是必要的（注意 Math.abs(Integer.MIN_VALUE) 仍可能为负，这是细微边界情况，但对于教学示例通常可以忽略）。
     *
     * - 更健壮的实现应该处理 Integer.MIN_VALUE 的情况，或使用 (hash & 0x7FFFFFFF) 来确保正数。
     *
     * 为什么取模 table.size()？
     * - hashCode 返回一个很大的整数（可能远大于 table 的大小），用 mod 操作把它映射到 [0, table.size()-1] 的索引范围。
     */
    private int getPreferredIndex(K key) {
        return Math.abs(key.hashCode()) % table.size();
    }
}

/* =========================
   开放寻址实现：ProbedTable（探测法）
   ========================= */

/**
 * ProbedTable 使用开放寻址法（Open Addressing）把键值放在数组中。
 * 当首选位置被占用时，按照某种探测序列（probing sequence）找下一个位置。
 *
 * 三种探测策略（ProbingStyle）：
 *  - LINEAR：线性探测，next = current + 1。优点：实现简单。缺点：聚集（primary clustering）问题导致性能下降。
 *  - QUADRATIC：二次探测，next = current + step^2。相对缓解线性聚集，但需小心表大小与探测次数保证能覆盖全部槽位或至少足够数量。
 *  - DOUBLE_HASHING：双重哈希，使用第二个哈希函数 h2，step * h2。优点：通常聚集更小、分布更均匀，但必须保证 h2 与 tableSize 相互适配（例如 h2 与 tableSize 互质）。
 *
 * 注意：开放寻址中删除较复杂（需要标记删除 tombstone），并且当表接近满时性能急剧下降。本实现只含查找与插入（无删除）。
 */
class ProbedTable<K,V> {
    enum ProbingStyle {
        LINEAR,
        QUADRATIC,
        DOUBLE_HASHING,
    }

    /**
     * Open addressing 中的节点类型（没有 next 指针，因为不存在链表）
     * - key：键
     * - value：值
     *
     * 注意：若要支持删除，通常需要额外的状态（比如 tombstone 标记）来区分“从未使用”和“已删除但曾用过”的槽位。
     */
    class Node<K,V> {
        K key;
        V value;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * table：存放 Node 或 null 的数组/向量。
     * - 使用 Vector 来保持和你原始代码一致。
     * - 每个槽位要么为 null（表示从未放置过元素），要么存放一个 Node（表示占用）。
     * - 若实现删除，需要一个 tombstone 标记来表示“已删除但非空”，以便查找和插入逻辑正确（本代码未实现删除）。
     */
    Vector<Node<K,V>> table;
    private ProbingStyle probingstyle;

    /**
     * 构造函数：默认探测样式为 LINEAR（线性探测）。
     * - M 为表大小（槽位数）
     * - 初始化所有槽位为 null（表示空）
     */
    ProbedTable(int M) {
        this(M, ProbingStyle.LINEAR);
    }

    /**
     * 构造函数：指定探测样式
     */
    ProbedTable(int M, ProbingStyle style) {
        table = new Vector<>();
        for (int i = 0; i < M; i++) {
            table.add(null);
        }
        this.probingstyle = style;
    }

    /**
     * V lookUp(K key)
     *
     * 查找流程（开放寻址）：
     * 1) 若 key 为 null，返回 null（不支持 null 键）。
     * 2) 计算首选索引 preferredIndex（通常由 hash 映射）。
     * 3) 设置 step = 0, currentIndex = preferredIndex。然后循环：
     *      - 如果 table[currentIndex] == null：说明遇到一个空槽（从未被占用），因此可以确定键不存在（返回 null）。
     *          * 注意：如果实现了删除（tombstone），遇到 tombstone 时不能立即返回，因为键可能在后面位置存在；但遇到真正的 null（never-used）才可返回。
     *      - 如果 table[currentIndex].key 与 key 相等：找到了，返回 value。
     *      - 否则：根据探测策略计算下一个索引（getNextIndex），step++，继续尝试，直到 step == tableSize（遍历了整个表）后仍未找到，返回 null。
     *
     * 复杂度：
     *  - 平均取决于装载因子 α（元素数/表大小）。当 α 接近 1（表快满）时性能会大幅下降。
     *
     * 关键点：
     *  - 在开放寻址中，一旦遇到一个**从未使用的槽（null）**，你可以安全断定被查找的键不存在（因为插入会停在第一个空槽）。
     *  - 如果系统使用 tombstone 标记，查找需要跳过 tombstone 并继续探测。
     */
    V lookUp(K key) {
        if (key == null) {
            return null;
        }

        int preferredIndex = getPreferredIndex(key);
        int step = 0;
        int currentIndex = preferredIndex;
        int tableSize = table.size();

        while (step < tableSize) {
            Node<K,V> node = table.get(currentIndex);

            if (node == null) {
                // 遇到空位置，说明键不存在
                return null;
            }

            if (key.equals(node.key)) {
                return node.value;
            }

            // 移动到下一个位置
            step++;
            currentIndex = getNextIndex(key, preferredIndex, step) % tableSize;
            if (currentIndex < 0) {
                currentIndex += tableSize; // 确保索引为正
            }
        }

        return null; // 遍历了整个表都没找到
    }

    /**
     * V insert(K key, V value)
     *
     * 插入流程（开放寻址）：
     * 1) 若 key 为 null，返回 null。
     * 2) 计算 preferredIndex，设置 step = 0, currentIndex = preferredIndex。
     * 3) 循环尝试 step < tableSize：
     *      - 若在当前位置找到同键：更新 value，返回旧值（覆盖行为）。
     *      - 若当前位置为 null（空槽，未被占用）：在此位置插入新节点，返回 null（表示无旧值）。
     *      - 否则继续 probe（按指定规则计算下一个索引）。
     * 4) 如果循环结束仍未插入（表满），抛出 RuntimeException("Table is full")。
     *
     * 关键点：
     *  - 插入时必须遵守与查找相同的探测序列，否则查找和插入不一致会导致查找失败。
     *  - 如果实现删除需要 tombstone 支持：插入可以把第一个遇到的 tombstone 位置作为候选插入位置（优于继续探测到真正的 null）。
     *  - 没有实现自动扩容：真实系统通常在装载因子超过阈值（例如 0.5 或 0.7）时扩容并重新哈希。
     */
    V insert(K key, V value) {
        if (key == null) {
            return null;
        }

        int preferredIndex = getPreferredIndex(key);
        int step = 0;
        int currentIndex = preferredIndex;
        int tableSize = table.size();

        // 首先检查键是否已存在
        while (step < tableSize) {
            Node<K,V> node = table.get(currentIndex);

            if (node != null && key.equals(node.key)) {
                // 键已存在，更新值
                V oldValue = node.value;
                node.value = value;
                return oldValue;
            }

            if (node == null) {
                // 找到空位置，插入新节点
                table.set(currentIndex, new Node<>(key, value));
                return null;
            }

            // 移动到下一个位置
            step++;
            currentIndex = getNextIndex(key, preferredIndex, step) % tableSize;
            if (currentIndex < 0) {
                currentIndex += tableSize;
            }
        }

        throw new RuntimeException("Table is full");
    }

    /**
     * getPreferredIndex(K key)
     *
     * 首选索引用 hashCode 映射得到（与链式实现相同）。
     * - 使用 Math.abs 防止负数（注意 Integer.MIN_VALUE 边界）。
     */
    private int getPreferredIndex(K key) {
        return Math.abs(key.hashCode()) % table.size();
    }

    /**
     * getNextIndex(K key, int currentIndex, int step)
     *
     * 核心：根据不同的 probing style 计算“步进”函数（探测序列）。
     *
     * 参数说明（按你的代码实现）：
     * - key：用于在 double hashing 中计算第二哈希值（h2）。
     * - currentIndex：此处传入的是 preferredIndex（代码中传参名稍微有点误导，但逻辑正确） —— 第一次探测时 currentIndex = preferredIndex。
     * - step：当前是第几次探测（当 step=1 表示第一次偏移，step=0 表示首位）。
     *
     * 返回值：下一个索引（未对 tableSize 取模或保证正值，调用处做了 % tableSize 和正值修正）。
     *
     * 各策略解释：
     * - LINEAR:
     *      return (currentIndex + 1) % tableSize;
     *   实现了简单的线性探测（每次 +1），但会出现“primary clustering”（聚集）现象：一旦某个区段被占用，后续键更容易落到该区段，使长度增长。
     *
     * - QUADRATIC:
     *      return (currentIndex + step * step) % tableSize;
     *   二次探测使用 step^2 的偏移，能减轻线性聚集问题。注意二次探测并不总能探测到所有槽位（取决于表大小和系数），但通常能覆盖更多槽位。
     *
     * - DOUBLE_HASHING:
     *      h1 = abs(hash) % tableSize;
     *      h2 = 1 + (abs(hash / tableSize) % (tableSize - 1));
     *      return (h1 + step * h2) % tableSize;
     *
     *   双重哈希使用两个不同的哈希函数（h1 和 h2），第二个哈希函数用于计算步长，通常能产生更好的探测序列并减少聚集。
     *   实现要点：
     *     - h2 应当非零且与 tableSize 互质（通常 h2 取值范围 1..tableSize-1），本实现把 h2 保证在 1..tableSize-1 之间。
     *     - 使用 (hash / tableSize) 的变换来产生第二个哈希值是一种简单方法，但在实际系统中建议使用独立的哈希函数。
     *
     * 额外注意：
     * - 当前代码中 getNextIndex 的第一个参数是 key，第二个参数命名为 currentIndex（但你在调用中传入的是 preferredIndex），由于所有实现内部都使用 preferredIndex/h1 而非传入的 currentIndex 作递推，这里不会导致错误，但命名上略有迷惑。
     * - 为了防止负索引，调用处对返回值做 % tableSize 后还检查 currentIndex < 0 并修正。
     */
    private int getNextIndex(K key, int currentIndex, int step) {
        int tableSize = table.size();

        switch (probingstyle) {
            case LINEAR:
                return (currentIndex + 1) % tableSize;

            case QUADRATIC:
                return (currentIndex + step * step) % tableSize;

            case DOUBLE_HASHING:
                int h1 = Math.abs(key.hashCode()) % tableSize;
                int h2 = 1 + (Math.abs(key.hashCode() / tableSize) % (tableSize - 1));
                return (h1 + step * h2) % tableSize;

            default:
                throw new RuntimeException("Undefined probing style");
        }
    }
}




public class Main {
    public static void check(boolean predicate) {
        if (!predicate) {
            throw new IllegalArgumentException("Check failed");
        }
    }

    public static void testChainedTable() {
        System.out.println("=== 测试链式哈希表 ===");
        int N = 1000;
        int M = 1000;

        Vector<String> keys = new Vector<>();
        Vector<String> values = new Vector<>();

        // 初始化键和值
        for (int i = 0; i < N; i++) {
            keys.add("key#" + i);
            values.add("value#" + i);
        }

        ChainedTable<String, String> table = new ChainedTable<>(N);

        // 插入前M个元素
        for (int i = 0; i < M; i++) {
            String oldValue = table.insert(keys.get(i), values.get(i));
            check(oldValue == null);
        }

        // 测试查找
        for (int i = 0; i < M; i++) {
            String value = table.lookUp(keys.get(i));
            check(value != null);
            check(value.equals(values.get(i)));
        }

        // 测试未插入的键应该返回null
        for (int i = M; i < N; i++) {
            String value = table.lookUp(keys.get(i));
            check(value == null);
        }

        // 测试更新已存在的键
        String oldValue = table.insert(keys.get(0), "new_value");
        check(oldValue != null);
        check(oldValue.equals("value#0"));

        String updatedValue = table.lookUp(keys.get(0));
        check(updatedValue.equals("new_value"));

        System.out.println("链式哈希表测试通过！");
    }

    public static void testProbedTable(ProbedTable.ProbingStyle style) {
        String styleName = "";
        switch (style) {
            case LINEAR:
                styleName = "线性探测";
                break;
            case QUADRATIC:
                styleName = "二次探测";
                break;
            case DOUBLE_HASHING:
                styleName = "双重哈希";
                break;
        }

        System.out.println("=== 测试" + styleName + "哈希表 ===");

        // 对于探测哈希表，表大小应该远大于要插入的元素数量
        // 因为探测方法在负载因子高时性能会急剧下降
        int tableSize = 200;  // 增加表大小
        int testCount = 50;   // 减少测试元素数量

        Vector<String> keys = new Vector<>();
        Vector<String> values = new Vector<>();

        // 初始化键和值
        for (int i = 0; i < testCount; i++) {
            keys.add("key#" + i);
            values.add("value#" + i);
        }

        ProbedTable<String, String> table = new ProbedTable<>(tableSize, style);

        // 插入元素
        for (int i = 0; i < testCount; i++) {
            String oldValue = table.insert(keys.get(i), values.get(i));
            check(oldValue == null);
        }

        // 测试查找
        for (int i = 0; i < testCount; i++) {
            String value = table.lookUp(keys.get(i));
            check(value != null);
            check(value.equals(values.get(i)));
        }

        // 测试未插入的键应该返回null
        for (int i = testCount; i < testCount + 10; i++) {
            String value = table.lookUp("nonexistent#" + i);
            check(value == null);
        }

        // 测试更新已存在的键
        String oldValue = table.insert(keys.get(0), "new_value");
        check(oldValue != null);
        check(oldValue.equals("value#0"));

        String updatedValue = table.lookUp(keys.get(0));
        check(updatedValue.equals("new_value"));

        // 显示负载因子信息
        double loadFactor = (double) testCount / tableSize;
        System.out.println(styleName + "哈希表测试通过！负载因子: " + loadFactor);
    }

    public static void testProbedTableWithCustomSize(ProbedTable.ProbingStyle style, int tableSize, int testCount) {
        String styleName = "";
        switch (style) {
            case LINEAR:
                styleName = "线性探测";
                break;
            case QUADRATIC:
                styleName = "二次探测";
                break;
            case DOUBLE_HASHING:
                styleName = "双重哈希";
                break;
        }

        System.out.println("=== 测试" + styleName + "哈希表 (表大小: " + tableSize + ", 元素数: " + testCount + ") ===");

        Vector<String> keys = new Vector<>();
        Vector<String> values = new Vector<>();

        // 初始化键和值
        for (int i = 0; i < testCount; i++) {
            keys.add("key#" + i);
            values.add("value#" + i);
        }

        ProbedTable<String, String> table = new ProbedTable<>(tableSize, style);

        // 插入元素
        try {
            for (int i = 0; i < testCount; i++) {
                String oldValue = table.insert(keys.get(i), values.get(i));
                check(oldValue == null);
            }

            // 测试查找
            for (int i = 0; i < testCount; i++) {
                String value = table.lookUp(keys.get(i));
                check(value != null);
                check(value.equals(values.get(i)));
            }

            // 测试更新已存在的键
            String oldValue = table.insert(keys.get(0), "new_value");
            check(oldValue != null);
            check(oldValue.equals("value#0"));

            double loadFactor = (double) testCount / tableSize;
            System.out.println(styleName + "哈希表测试通过！负载因子: " + loadFactor);

        } catch (RuntimeException e) {
            System.out.println(styleName + "哈希表测试失败: " + e.getMessage());
            double loadFactor = (double) testCount / tableSize;
            System.out.println("当前负载因子: " + loadFactor + " (可能过高)");
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            System.out.println("\n请选择要测试的哈希表类型：");
            System.out.println("1. 链式哈希表");
            System.out.println("2. 线性探测哈希表 (默认参数)");
            System.out.println("3. 二次探测哈希表 (默认参数)");
            System.out.println("4. 双重哈希表 (默认参数)");
            System.out.println("5. 自定义参数测试探测哈希表");
            System.out.println("6. 测试所有类型 (默认参数)");
            System.out.println("0. 退出");
            System.out.print("请输入选择: ");

            int choice;
            try {
                choice = scanner.nextInt();
            } catch (Exception e) {
                System.out.println("输入无效，请输入数字！");
                scanner.nextLine(); // 清除无效输入
                continue;
            }

            switch (choice) {
                case 1:
                    testChainedTable();
                    break;
                case 2:
                    testProbedTable(ProbedTable.ProbingStyle.LINEAR);
                    break;
                case 3:
                    testProbedTable(ProbedTable.ProbingStyle.QUADRATIC);
                    break;
                case 4:
                    testProbedTable(ProbedTable.ProbingStyle.DOUBLE_HASHING);
                    break;
                case 5:
                    System.out.print("请输入表大小: ");
                    int tableSize = scanner.nextInt();
                    System.out.print("请输入要插入的元素数量: ");
                    int testCount = scanner.nextInt();
                    System.out.println("1. 线性探测");
                    System.out.println("2. 二次探测");
                    System.out.println("3. 双重哈希");
                    System.out.print("请选择探测方式: ");
                    int probeChoice = scanner.nextInt();

                    ProbedTable.ProbingStyle style;
                    switch (probeChoice) {
                        case 1: style = ProbedTable.ProbingStyle.LINEAR; break;
                        case 2: style = ProbedTable.ProbingStyle.QUADRATIC; break;
                        case 3: style = ProbedTable.ProbingStyle.DOUBLE_HASHING; break;
                        default:
                            System.out.println("无效选择，使用线性探测");
                            style = ProbedTable.ProbingStyle.LINEAR;
                    }
                    testProbedTableWithCustomSize(style, tableSize, testCount);
                    break;
                case 6:
                    testChainedTable();
                    testProbedTable(ProbedTable.ProbingStyle.LINEAR);
                    testProbedTable(ProbedTable.ProbingStyle.QUADRATIC);
                    testProbedTable(ProbedTable.ProbingStyle.DOUBLE_HASHING);
                    System.out.println("\n所有哈希表类型测试完成！");
                    break;
                case 0:
                    System.out.println("程序退出。");
                    scanner.close();
                    return;
                default:
                    System.out.println("无效选择，请重新输入！");
            }

            System.out.print("\n是否继续测试？(y/n): ");
            String continueChoice = scanner.next();
            if (!continueChoice.equalsIgnoreCase("y")) {
                System.out.println("程序退出。");
                scanner.close();
                return;
            }
        }
    }
}

数据结构与算法

笔记

This post is licensed under CC BY 4.0 by the author.