简介

哈希表 由 哈希函数 和 链表 组成，相当于「超级数组」。

• 数组的下标可以是超大整数、浮点数、字符串等具有哈希值的类型；
• 无需担心数组下标越界（除非你 使用数组模拟链表）。

问题

医院的排队系统需要记录每个病人对应的问诊顺序。

病人 ID	$114514$	$2333$	$2147483647$	$404$
问诊顺序	$1$	$2$	$3$	$4$

若直接用病人 ID 作为数组下标（如 $p[2147483647]=3$），需要创建长度超过 20 亿的数组，造成灾难性的空间浪费。

构造

名词约定

• 键（key）：指代每个对象的标识符（如 问题 中的病人 ID）；
• 值（value）：指代需要存储的对象信息（如问诊顺序）；
• 键值对（key value pair）：由一对键和值组成的结构体。

每组病人信息都可用一个键值对描述。

---

哈希表 内部存储的是 键值对。哈希表通过如下方式构造：

1. 设计哈希函数

设计哈希函数 $\mathrm{getHash}(x)$，将所有「键」映射到 $[0,M)$ 范围内的整数中（$M$ 通常很小）。

对于不同类型的「键」，有不同的方法设计 哈希函数。

2. 初始化链表头数组

申请长度为 $M$ 的指针数组 $\mathrm{head}$。$\mathrm{head}[i]$ 表示第 $i$ 个链表的头部，并初始化每个链表。

链表中存储的元素类型是「键值对」。

3. 插入所有键值对

对于每个键值对 $(\mathrm{key},\mathrm{val})$：

1. 计算 $v=\mathrm{getHash}(\mathrm{key})$；
2. 将 $(\mathrm{key},\mathrm{val})$ 插入到 $\mathrm{head}[v]$ 开头的链表中。

---

对于 问题，可以设计 $\mathrm{getHash}(x)=xmod5$，将大范围的 ID 映射到 $\{0,1,2,3,4\}$ 范围内的整数。依此开一个大小为 $5$ 的 $\mathrm{head}$ 数组。哈希表的结构如下：

@LR;
nodesep=0.15;
node [@s=box]
head4 [@n="$\mathrm{head}[4]$"];
n41  [@n="$(114514,1)$"];
n42  [@n="$(404,4)$"];
tail4 [@n="$\mathrm{tail}$"];
head4 -> n41 -> n42 -> tail4;
head3 [@n="$\mathrm{head}[3]$"];
n3   [@n="$(2333,2)$"];
tail3 [@n="$\mathrm{tail}$"];
head3 -> n3 -> tail3;
head2 [@n="$\mathrm{head}[2]$"];
n2   [@n="$(2147483647,3)$"];
tail2 [@n="$\mathrm{tail}$"];
head2 -> n2 -> tail2;
head1 [@n="$\mathrm{head}[1]$"];
tail1 [@n="$\mathrm{tail}$"];
head1 -> tail1;
head0 [@n="$\mathrm{head}[0]$"];
tail0 [@n="$\mathrm{tail}$"];
head0 -> tail0;

---

查询 ID 为 $114514$ 的病人的问诊顺序时：

1. 首先计算 $\mathrm{getHash}(114514)=4$，因此该病人的信息存在 $\mathrm{head}[4]$ 开头的链表中；
2. 遍历 $\mathrm{head}[4]$ 开头的链表，得到 $(114514,1)$，说明该病人的问诊顺序是 $1$。

经过封装后的哈希表可以实现类似数组的用法。

哈希函数

对于不同类型的键值，$\mathrm{getHash}(x)$ 有多种构造方式：

取模法

当 $x$ 是整型时，构造

$$\mathrm{getHash}(x)=xmodp$$

其中 $p$ 通常取质数（如 $999997$）。取模法是最常见的方法。

乘积取整法

当 $x$ 是浮点型时，构造

$$\mathrm{getHash}(x)=\lfloor A\cdot x\rfloor modp$$

其中 $p$ 通常取质数，$A$ 通常取区间 $(0,1)$ 中的无理数（如 ${\displaystyle \frac{\sqrt{5}-1}{2}}$）。

数位分析法

当 $x$ 是字符串或其它序列时，构造

$$\mathrm{getHash}(x)=(x[0]+x[1]\cdot b+x[2]\cdot b^2+x[3]\cdot b^3+\cdots )modp$$

详见 字符串哈希。

模板

采用 使用数组模拟链表 的方式。

static struct hash_map {
    #define MOD (999997) 

    struct node {
        int key, val;
        int next;
    } edge[MOD];

    int head[MOD], cnt;
    int getHash(int x) { return x % MOD; }

    int& operator[](int key) {
        int h = getHash(key);
        for (int p = head[h]; p; p = edge[p].next)
            if (edge[p].key == key)
                return edge[p].val;
        edge[++ cnt] = (node){0, head[h], key}, head[h] = cnt;
        return edge[cnt].val;
    }

    hash_map() {
        cnt = 0;
        memset(head, 0, sizeof head);
    }
}