Appearance
简介
- 数组的下标可以是超大整数、浮点数、字符串等具有哈希值的类型;
- 无需担心数组下标越界(除非你 使用数组模拟链表)。
问题
医院的排队系统需要记录每个病人对应的问诊顺序。
病人 ID | ||||
---|---|---|---|---|
问诊顺序 |
若直接用病人 ID 作为数组下标(如
构造
名词约定
- 键(key):指代每个对象的标识符(如 问题 中的病人 ID);
- 值(value):指代需要存储的对象信息(如问诊顺序);
- 键值对(key value pair):由一对键和值组成的结构体。
每组病人信息都可用一个键值对描述。
哈希表 内部存储的是 键值对。哈希表通过如下方式构造:
1. 设计哈希函数
设计哈希函数
对于不同类型的「键」,有不同的方法设计 哈希函数。
2. 初始化链表头数组
申请长度为
链表中存储的元素类型是「键值对」。
3. 插入所有键值对
对于每个键值对
- 计算
; - 将
插入到 开头的链表中。
对于 问题,可以设计
查询 ID 为
- 首先计算
,因此该病人的信息存在 开头的链表中; - 遍历
开头的链表,得到 ,说明该病人的问诊顺序是 。
经过封装后的哈希表可以实现类似数组的用法。
哈希函数
对于不同类型的键值,
取模法
当
其中
乘积取整法
当
其中
数位分析法
当
详见 字符串哈希。
模板
采用 使用数组模拟链表 的方式。
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);
}
}