Skip to content

哈希表

2021-04-16

简介

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

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

问题

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

病人 ID11451423332147483647404
问诊顺序1234

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

构造

名词约定

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

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


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

1. 设计哈希函数

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

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

2. 初始化链表头数组

申请长度为 M 的指针数组 headhead[i] 表示第 i 个链表的头部,并初始化每个链表。

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

3. 插入所有键值对

对于每个键值对 (key,val)

  1. 计算 v=getHash(key)
  2. (key,val) 插入到 head[v] 开头的链表中。

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


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

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

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

哈希函数

对于不同类型的键值,getHash(x) 有多种构造方式:

取模法

x 是整型时,构造

getHash(x)=xmodp

其中 p 通常取质数(如 999997)。取模法是最常见的方法。

乘积取整法

x 是浮点型时,构造

getHash(x)=Axmodp

其中 p 通常取质数,A 通常取区间 (0,1) 中的无理数(如 512)。

数位分析法

x 是字符串或其它序列时,构造

getHash(x)=(x[0]+x[1]b+x[2]b2+x[3]b3+)modp

详见 字符串哈希

模板

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

cpp
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);
    }
}