哈希表
哈希表，又称散列表，是一种储存键值对的数据结构。
哈希表的基础思想是拿空间换时间，哈希表的期望复杂度是 $O(1)$ 的。
一般来说，对于某 key 值，哈希后得到对应的下标，代表其在哈希表中的位置。
$\texttt{hashtable}[\operatorname{hash}(key)] = \texttt{value}$
哈希表的核心就在于 $\operatorname{hash}$ 函数。
哈希冲突
哈希冲突是哈希表极力避免的情况。由于对 key 值进行哈希，不能保证不同 key 值的哈希一定不同，因此可能出现 $x_1 \neq x_2$ ，使得 $\operatorname{hash}(x_1) = \operatorname{hash}(x_2)$ ，即出现哈希冲突。
如果不考虑哈希冲突，就会出现误判的情况。而要解决哈希冲突，往往会使哈希表复杂度退化。
不同的实现方法，本质上就是用不同方法避免哈希冲突。
桶
可以将桶看做一种特殊的哈希表，存储整数型的键值对。
$\operatorname{hash}(x) = x$
这样能保证在值域范围内不冲突，key 值与其哈希值一一对应，在值域不大时是一种良好的数据结构。
1
2
3
4
|
inline int hash(int x){return x;}
bool ht[maxn];
inline bool find(int x){return ht[hash(x)];}
inline void insert(int x){ht[hash(x)] = true;}
|
单模数哈希表
单模数哈希表是使用广泛、代码简单的一种实现方式。
在值域范围较大，无法承受其空间时，可以对值取模来减少使用空间。
1
2
3
4
5
|
const int mod = 10000103;//usually a prime
bool ht[mod + 100];
inline int hash(int x){return ((x % mod) + mod) % mod;}
inline bool find(int x){return ht[hash(x)];}
inline void insert(int x){ht[hash(x)] = true;}
|
上述代码就是一种简单的实现。
然而这种实现没有考虑哈希冲突，在处理 $x$ 与 $x + mod$ 时就会发生明显的错误。
线性探测法
为了解决单模数哈希表的哈希冲突，有线性探测法。
具体地，当 $key[\operatorname{hash}(x)] \neq x$ 时，检查 $\operatorname{hash}(x) + 1,\operatorname{hash}(x) + 2,\ldots$ 位置的 $key$ 值是否与 $x$ 相等，若相等则读取 $val$ 值。
在最劣情况下，单次操作是 $O(n)$ 复杂度的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
struct LinearAttemptHashTable
{
static const int mod = 10000103;
int keytable[mod + 100], valtable[mod + 100];
LinearAttemptHashTable() { memset(keytable, 0, sizeof(keytable)), memset(valtable, 0, sizeof(valtable)); }
int hash(int x) { return ((x % mod) + mod) % mod; }
int & operator[](int key)
{
int p = hash(key);
while (keytable[p] && keytable[p] != key) p = (p + 1) % mod;
keytable[p] = key;
return valtable[p];
}
int* find(int key)
{
int p = hash(key);
while (keytable[p] && keytable[p] != key) p = (p + 1) % mod;
if(keytable[p] == key) return &valtable[p];
return NULL;
}
};
|
拉链法
拉链法是另一种解决哈希冲突的方法。
在 $\operatorname{hash}(key)$ 冲突时，在 $ht[key]$ 处创建链表，将元素加入链表即可。
在查询时，遍历对应位置的链表。
最劣情况下，单次操作是 $O(n)$ 复杂度的。
然而大部分情况下表现良好。注意需要开链表的话，可以将模数适当调小。
或者用类似建图时的写法，开固定大小的内存池。
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
struct ListHashTable
{
static const int mod = 100103;
std::list<std::pair<int, int> > valtable[mod + 100];
int hash(int x)
{
int res = x % mod;
if (res < 0) res += mod;
return res;
}
int & operator[](int key)
{
int p = hash(key);
for (std::list<std::pair<int, int> >::iterator it = valtable[p].begin(); it != valtable[p].end(); ++it)
if (it->first == key) return it->second;
valtable[p].push_front(std::make_pair(key, 0));
return valtable[p].begin()->second;
}
int* find(int key)
{
int p = hash(key);
for (std::list<std::pair<int, int> >::iterator it = valtable[p].begin(); it != valtable[p].end(); ++it)
if (it->first == key) return &it->second;
return NULL;
}
};
struct BetterListHashTable
{
static const int mod = 1000103;
static const int maxn = 1e6 + 100;
struct node
{
int next, key, val;
} A[maxn + 10];
int head[mod + 100],tot;
int hash(int x)
{
int res = x % mod;
if (res < 0) res += mod;
return res;
}
int & operator [](int key)
{
int pos = hash(key);
for (int p = head[pos]; p; p = A[p].next)
if (A[p].key == key) return A[p].val;
A[++tot].next = head[pos], A[tot].key = key, A[tot].val = 0, head[pos] = tot;
return A[tot].val;
}
int* find(int key)
{
int pos = hash(key);
for(int p = head[pos];p;p=A[p].next)
if(A[p].key == key) return &A[p].val;
return NULL;
}
};
|
重哈希法
该方法名称为本人杜撰的。
上面两种方法虽然简单，而随机数据下也称得上有效，但由于广为人知，容易遇到精心构造的数据。
而这种方法不那么常见，而由于随机性较大，也不那么好卡。
当 $p = \operatorname{hash}(key)$ 位置已占用时， $p := \operatorname{hash}(p)$ ，即重哈希。
而这里的哈希函数发挥空间很大，只要保证 $\operatorname{hash}(\operatorname{hash}(x)) \neq \operatorname{hash}(x)$ 并且让 $\operatorname{hash}(x)^C = \operatorname{hash}(x)$ 的 $C$ 尽量大即可。
可以说，线性探测法是重哈希法的一种特殊实现。
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
|
struct AttemptHashTable
{
static const int mod = 10000103;
int keytable[mod + 100], valtable[mod + 100];
AttemptHashTable() { memset(keytable, 0, sizeof(keytable)), memset(valtable, 0, sizeof(valtable)); }
int hash(int x)
{
int res = (x + 195781) % mod;
if(res < 0) res += mod;
return res;
}
int & operator[](int key)
{
int p = hash(key);
while (keytable[p] && keytable[p] != key) p = hash(p);
keytable[p] = key;
return valtable[p];
}
int* find(int key)
{
int p = hash(key);
while (keytable[p] && keytable[p] != key) p = hash(p);
if(keytable[p] == key) return &valtable[p];
return NULL;
}
};
|
其中哈希函数 $\operatorname{hash}(x) = x + C$ ， $C$ 是质数时，哈希表发挥较好。
$x$ 可以存储到的范围为 $y = x + C \times k_1 + mod \times k_2$ ，其中 $k_1,k_2$ 为整数。
$C \times k_1 + mod \times k_2 = \gcd(C,mod)$ 有解，而 $\gcd(C,mod) = 1$ ，则 $y$ 可以取到整个数组。
多模数哈希
多模数哈希也是一种简单的哈希方法。
当 $\pmod {p_1}$ 意义下有冲突，则更换模数，求出 $\pmod {p_2}$ 意义下的下标。
模数可以使用随机数，能防止被卡。
值得注意的是，在模数较少的情况下，仍可能出现错误。即多个模数意义下的下标都被占用的情况。
可以直接取很多个模数，尽量减小这种可能性。
结语
哈希表的实现千千万万种，最为常用的线性探测法、拉链法在实际应用中都有不错的表现。
以上仅为几种广为人知的、较为简单的哈希表的实现，供各位读者参考。