哈希表
哈希表¶
哈希表是又称散列表,一种以 "key-value" 形式存储数据的数据结构。所谓以 "key-value" 形式存储数据,是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值,就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组,这种数组的下标可以是很大的整数,浮点数,字符串甚至结构体。
哈希函数¶
要让键值对应到内存中的位置,就要为键值计算索引,也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数,也称散列函数。举个例子,如果键值是一个人的身份证号码,哈希函数就可以是号码的后四位,当然也可以是号码的前四位。生活中常用的“手机尾号”也是一种哈希函数。在实际的应用中,键值可能是更复杂的东西,比如浮点数、字符串、结构体等,这时候就要根据具体情况设计合适的哈希函数。哈希函数应当易于计算,并且尽量使计算出来的索引均匀分布。
在 OI 中,最常见的情况应该是键值为整数的情况。当键值的范围比较小的时候,可以直接把键值作为数组的下标,但当键值的范围比较大,比如以
能为 key 计算索引之后,我们就可以知道每个键值对应的值 value 应该放在哪里了。假设我们用数组 a 存放数据,哈希函数是 f,那键值对 (key, value)
就应该放在 a[f(key)]
上。不论键值是什么类型,范围有多大,f(key)
都是在可接受范围内的整数,可以作为数组的下标。
冲突¶
如果对于任意的键值,哈希函数计算出来的索引都不相同,那只用根据索引把 (key, value)
放到对应的位置就行了。但实际上,常常会出现两个不同的键值,他们用哈希函数计算出来的索引是相同的。这时候就需要一些方法来处理冲突。在 OI 中,最常用的方法是拉链法。
拉链法¶
拉链法也称开散列法(open hashing)。
拉链法是在每个存放数据的地方开一个链表,如果有多个键值索引到同一个地方,只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍,对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是
实现¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | // C++ Version
const int SIZE = 1000000;
const int M = 999997;
struct HashTable {
struct Node {
int next, value, key;
} data[SIZE];
int head[M], size;
int f(int key) { return key % M; }
int get(int key) {
for (int p = head[f(key)]; p; p = data[p].next)
if (data[p].key == key) return data[p].value;
return -1;
}
int modify(int key, int value) {
for (int p = head[f(key)]; p; p = data[p].next)
if (data[p].key == key) return data[p].value = value;
}
int add(int key, int value) {
if (get(key) != -1) return -1;
data[++size] = (Node){head[f(key)], value, key};
head[f(key)] = size;
return value;
}
};
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | # Python Version
M = 999997
SIZE = 1000000
class Node:
def __init__(self, next = None, value = None, key = None):
self.next = next
self.value = value
self.key = key
data = [Node()] * SIZE
head = [0] * M
size = 0
def f(key):
return key % M
def get(key):
p = head[f(key)]
while p:
if data[p].key == key:
return data[p].value
p = data[p].next
return -1
def modify(key, value):
p = head[f(key)]
while p:
if data[p].key == key:
data[p].value = value
return data[p].value
p = data[p].next
def add(key, value):
if get(key) != -1:
return -1
data[size] = Node(head[f(key)], value, key)
size = size + 1
head[f(key)] = size
return value
|
这里再提供一个封装过的模板,可以像 map 一样用,并且较短
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | struct hash_map { // 哈希表模板
struct data {
long long u;
int v, nex;
}; // 前向星结构
data e[SZ << 1]; // SZ 是 const int 表示大小
int h[SZ], cnt;
int hash(long long u) { return u % SZ; }
int& operator[](long long u) {
int hu = hash(u); // 获取头指针
for (int i = h[hu]; i; i = e[i].nex)
if (e[i].u == u) return e[i].v;
return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v;
}
hash_map() {
cnt = 0;
memset(h, 0, sizeof(h));
}
};
|
在这里,hash 函数是针对键值的类型设计的,并且返回一个链表头指针用于查询。在这个模板中我们写了一个键值对类型为 (long long, int)
的 hash 表,并且在查询不存在的键值时返回 -1。函数 hash_map()
用于在定义时初始化。
闭散列法¶
闭散列方法把所有记录直接存储在散列表中,如果发生冲突则根据某种方式继续进行探查。
比如线性探查法:如果在 d
处发生冲突,就依次检查 d + 1
,d + 2
……
实现¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | const int N = 360007; // N 是最大可以存储的元素数量
class Hash {
private:
int keys[N];
int values[N];
public:
Hash() { memset(values, 0, sizeof(values)); }
int& operator[](int n) {
// 返回一个指向对应 Hash[Key] 的引用
// 修改成不为 0 的值 0 时候视为空
int idx = (n % N + N) % N, cnt = 1;
while (keys[idx] != n && values[idx] != 0) {
idx = (idx + cnt * cnt) % N;
cnt += 1;
}
keys[idx] = n;
return values[idx];
}
};
|
例题¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用