哈希表

简介 #

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

数组的下标¹可以是整数，浮点数，字符串等.
不用定义数组的长度.

问题 #

医院的排队系统需要记录每个病人对应的问诊顺序.此处假设每个病人的名称都是数字.

名称	$32$	$26$	$75$	$4$
问诊顺序	$1$	$2$	$3$	$4$

$p[i]$ 表示「名称为 $i$ 的病人的问诊顺序」.查询问诊顺序的时间复杂度为 $O(1)$.

int p[];

void update(int i, int x) { // 记录病人 i 的问诊顺序为 x
    p[i] = x;
}

int query(int i) { // 查询病人 i 的问诊顺序
    return p[i];
}

然而总有某些病人不按套路取名.

名称	$114514$	$2333$	$2147483647$	$404$
问诊顺序	$1$	$2$	$3$	$4$

要存储 $p[2147483647]=3$，得先开一个长度为 $2147483647$ 的数组.这明显不现实.

构造 #

开一个如此丑陋的数组，会浪费超过 $99\%$ 的空间.毕竟只用到了其中的四个元素.有没有办法使数组只占很少空间？

设计哈希函数 $getHash()$，用 $p[getHash(i)]$ 表示病人 $i$ 的问诊顺序.对于本例，有：

$$ getHash(i)=i\%5 $$

这样数组就只要开到 $p[5]$.但这么做会导致其它问题：病人 $114514$ 和病人 $404$ 的问诊顺序会同时存入 $p[4]$，因为 $getHash(114514)=getHash(404)=4$.于是我们可以将 $getHash()$ 相同的病人放在同一个链表里.

查询病人 $i$ 的问诊顺序时，只需在 $getHash(i)$ 开头的链表中找到该病人.

哈希函数 #

$getHash()$ 有多种构造方式：

取模法

$$ getHash(x)=x\%p $$

其中 $p$ 为质数（如 $999997$）.
乘积取整法

$$ getHash(x)=\lfloor A\cdot x\rfloor\%p $$

其中 $p$ 为质数，$A$ 为区间 $(0,1)$ 中的无理数（如 $\frac{\sqrt{5}-1}{2}$）.
数位分析法

$$ getHash(s)=(s[0]+s[1]\cdot b+s[2]\cdot b^2+s[3]\cdot b^3+\cdots)\%p $$

其中 $s$ 为字符串，$b,p$ 为质数.详见哈希函数.

模板 #

static struct hash_map {
    #define MOD (999997) 

    struct node {
        int val, next, key;
    } 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);
    }
}

中括号里的数称之为「下标」，例如 $a[14]$ 的下标为 $14$. ↩︎