「数据结构详解·六」哈希表

• 「数据结构详解·一」树的初步
• 「数据结构详解·二」二叉树的初步
• 「数据结构详解·三」栈
• 「数据结构详解·四」队列
• 「数据结构详解·五」链表
• 「数据结构详解·六」哈希表

1. 哈希表的定义和构成

哈希表(Hash table)，又称散列表，非线性结构。这种数据结构用来判断某值出现的情况。
具体可以看一下下面的例题，我们会一边看题一边解释。

2. 例题详解 & 代码实现

2-1. 洛谷 P1059 [NOIP2006 普及组] 明明的随机数

还记得你当时是怎么做的吗？
是不是开一个数组 f[] 记这个数是否出现过？
事实上，这就是一种简单哈希表。

2-2. 洛谷 P3370 【模板】字符串哈希

对于较小的整数，我们可以用数组模拟。
可是对于字符串呢？
有一种做法是，对于每个字符串，我们把其看作一个 $p$（$p$ 一般取 $131$ 或 $13331$）进制数，然后算出其对 $m$（一般 $m$ 取 $2^{64}$）取模的数，存入哈希表中。
我们可以处理字符串的前缀哈希值，然后求出任意子串的哈希值。具体地，令 $H(x)$ 表示字符串 $x$ 的哈希值，则已知 $H(x),H(x+y)$，可以得出 $H(y)=(H(x+y)-H(x)\times p^{|y|})\mathrm{mod}m$。
具体的证明，留给读者自行思考。
读者可能会想，假若两个字符串的哈希值相同怎么办？
这种情况被称为哈希冲突。
我们可以取合适 $p,m$（如大质数），然后取多个 $p_i,m_i$，做多次运算，只有当所有运算得出的哈希值与之前的相等才认为存在过该字符串。
这可以将冲突大大减小。
当然了，为了满足几乎没有冲突，我们还可以用字典树或者 STL set/map。
字典树我们将在以后讲解。这里先讲解简单的 STL set/map。

2-2-1. STL set, multiset, unordered_set

set，顾名思义，就是集合（即元素不重复）。set 的内部是一棵红黑树（我们将在以后讲解，现在只需要知道）。另外，set 内部会自动排序。
定义一个存储值为整型的 set：

set<int,less<int>>s;//升序排序，less可以省去
set<int,greater<int>>s;//降序排序，greater不可省去
1
2

下面是一些主要的函数。
插入元素：

s.insert(x)//元素
s.insert(x,y)//迭代器地址
1
2

删除元素：

s.erase(x);
1

返回元素个数：

s.size()
1

返回元素是否为空：

s.empty()
1

返回 set 中某个元素的个数：

s.count(x)
1

清空 set：

s.clear()
1

返回 set 的第一个元素的迭代器：

s.begin()
1

返回 set 的最后一个元素的迭代器：

s.end()
1

返回 set 的最后一个元素的反迭代器：

s.rbegin()
1

返回 set 的第一个元素的反迭代器：

s.rend()
1

对于本题来说，就是这么写：

#include
using namespace std;

set<string>a;

int main()
{
	int n;
	cin>>n;
	string s;
	while(n--)
	{
		cin>>s;
		a.insert(s);
	}
	cout<<a.size();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在 STL 中，还有 multiset 与 unordered_set。
multiset，就是允许重复元素的集合（你甚至可以把其理解为平衡树）。
unordered_set，就是不允许重复元素，但是不排序的集合。

2-2-2. STL map, multimap, unordered_map

map，即映射，将一个值映射到另一个值。map 内部同样是一棵红黑树。
定义一个 map：

map<int,int>mp;
1

第一个 int 表示原值(key)，第二个 int 表示映射的值(value)。
比如，我们要让 $114514$ 映射为 $1919810$，我们可以这么做：

mp[114514]=1919810;
1

但是，map 同样会去重，所以每次的值会覆盖上一次的值。
对于本题，你就可以这么做：

#include
using namespace std;

map<string,bool>a;

int main()
{
	int n;
	cin>>n;
	string s;
	while(n--)
	{
		cin>>s;
		a[s]=1;
	}
	cout<<a.size();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

map 的函数与 set 类似，而且和 set 一样，有可重复的 multimap 和不排序的 unordered_map。
细心的读者可以发现，map 和 set 内部是树，因此其插入均为 $O(\log n)$ 级别，而 unordered_set 和 unordered_map 内部是哈希表，插入都是 $O(1)$ 级别。

2-2-3. 离散化

对于本题来说，输入的东西是离线状态的，故我们可以使用一种类似一种叫离散化的算法。
离散化，本质上就是将错综复杂的数据映射成简单的数据。
做法是先排序，再去重，最后分配。
举个例子：$114514,3.1415926,-1919810,1.0000001,7.1234,3.1415926,1.0000001,114514,114514$。
排序后：$-1919810,1.0000001,1.0000001,3.1415926,3.1415926,7.1234,114514,114514,114514$。
去重后：$-1919810,1.0000001,3.1415926,7.1234,114514$。
分配给原数据新的值：$5,3,1,2,4,3,2,5,5$。
可以发现，新的值就是去重后各数据的下标。
这道题，我们无需分配新值，只需要到去重即可：

#include
using namespace std;

string a[10005];

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	cout<<unique(a+1,a+n+1)-a-1;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

那如果要分配新值呢？
我们就会使用 lower_bound()。
lower_bound(a+1,a+n+1,x) 表示在 $a_1\sim a_n$（$a$ 有序）中寻找第一个小于等于 $x$ 的数的位置。
实现：

sort(a+1,a+n+1);
m=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;i++)
{
	a[i]=lower_bound(a+1,a+m+1,a[i])-a;
}
1
2
3
4
5
6

2-3. 洛谷 P4305 [JLOI2011]不重复数字

这题很显然就是哈希表模板，我们可以用 unordered_map 实现（map 带 log，在本题中被 hack 数据卡掉了）。
代码：

#include
using namespace std;

unordered_map<int,bool>a;

int read()//快读
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

int main()
{
	int t,n,x;
	t=read();
	while(t--)
	{
		a.clear();//多测初始化清空
		n=read();
		while(n--)
		{
			x=read();
			if(!a[x])//不是重复的数字
			{
				a[x]=true;//标记
				printf("%d ",x);//输出
			}
		}
		puts("");
	}
 	return 0;
}
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

3. 巩固练习

• 洛谷 P3405 [USACO16DEC]Cities and States S
• 洛谷 P2580 于是他错误的点名开始了
• 洛谷 P5250 【深基17.例5】木材仓库
• 洛谷 P5266 【深基17.例6】学籍管理
• 洛谷 P3879 [TJOI2010] 阅读理解