Hash表

哈希 散列 Hash
注意本条目不是Hash函数
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

提出问题

设想一个简单的问题，输入$n$个数字$a_i$，每次询问一个数字$x$是否出现。

一个用Hash思想的方法就是选取一个质数$p$，计算$a_i \bmod p$的结果。

但是这样有一个问题，假设取模结果相同怎么办，可以使用开链Hash和闭链Hash。

处理冲突

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：

开链Hash

即如果出现重复，用一个链表挂在外面。
查找的话只需要遍历一遍所有Hash值相同的元素。

闭链Hash(开放定址法)

即如果出现重复，继续向下一个位置填充。
当然查找的话要一直向后查找到第一个空位。

几乎没有人使用。

算法比赛中的Hash表

Hash表使用的人数少之又少，因为可行的替代方法非常多，
比如说排序二分，map，unordered_map，
只有在极少数情况在意常数的时候，才会使用Hash表。

一般使用开链Hash，用链表实现，代码简单。

输入n个数字，问有多少个不同数字/输入每个数字的时候，回答之前是否出现过
set s;
for (int i = 1; i <= n; i++)
{
cin >> x;
s.insert(x);
}
问题：set会越来越大，导致越来越慢

int mod = rand();
set s[10007];
for (int i = 1; i <= n; i++)
{
cin >> x;
s[x % 10007].insert(x);
}
在随机情况下每个set都不会太大，效率大大提高。
Hash(x) = (x % 10007) Hash函数

1. 相同的数字Hash之后必须相同
2. 不同的数字Hash之后尽量不同
3. 计算的要快
4. 范围不能太大

大部分写法中，并不会使用set，而会使用vector，链表
%10007之后一定会有相同的，怎么处理

sha1 2**256

1. 不可逆
2. 唯一方法一个一个试

问题：找一个字符串以今天日期为开始，Hash的最后10位是0
如果认为Hash是随机的话，那么如果一个人找到了Hash最后10位是0的字符串
可以认为他计算了1024次

时间复杂度

一般认为是$O(1)$，实际情况受较多因素影响。

参考题目

P4305 [JLOI2011]不重复数字

https://www.luogu.com.cn/problem/P4305

题目描述

给定 $n$ 个数，要求把其中重复的去掉，只保留第一次出现的数。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个数，表示给定的数。

输出格式

对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。

样例 #1

样例输入 #1

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

样例输出 #1

1 2 18 3 19 6 5 4
1 2 3 4 5 6

提示

对于 $30\%$ 的数据，$n \le 100$，给出的数 $\in [0, 100]$。

对于 $60\%$ 的数据，$n \le 10^4$，给出的数 $\in [0, 10^4]$。

对于 $100\%$ 的数据，$1 \le T\le 50$，$1 \le n \le 5 \times 10^4$，给出的数在 $32$ 位有符号整数范围内。

参考代码

#include <bits/stdc++.h>
using namespace std;
inline 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 t, n, x;
int main()
{
	t = read();
	for (int tt = 0; tt < t; tt++)
	{
		unordered_set<int> s;
		n = read();
		for (int i = 0; i < n; i++)
		{
			x = read();
			if (s.insert(x).second)
			{
				printf("%d ", x);
			}
		}
		printf("\n");
	}
	return 0;
}

题解

set暴力，
unordered_set
unordered_map
没有有序的性质了（不能lower_bound upper_bound）
不需要指定
出题人能不能造一个数据，让unordered_set超时？
能

P1097 [NOIP2007 提高组] 统计数字

https://www.luogu.com.cn/problem/P1097

题目背景

警告：数据可能存在加强

题目描述

某次科研调查时得到了$n$个自然数，每个数均不超过$1500000000(1.5 \times 10^9)$。已知不相同的数不超过$10000$个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入格式

共$n+1$行。

第一行是整数$n$，表示自然数的个数；

第$2$至$n+1$每行一个自然数。

输出格式

共$m$行（$m$为$n$个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出$2$个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例 #1

样例输入 #1

8
2
4
2
4
5
100
2
100

样例输出 #1

2 3
4 2
5 1
100 2

提示

$40\%$的数据满足：$1 \le n \le 1000$

$80\%$的数据满足：$1 \le n \le 50000$

$100\%$的数据满足：$1 \le n \le 200000$，每个数均不超过$1500 000 000(1.5 \times 109)$

NOIP 2007 提高第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int n, x;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		g[x]++;
	}
	for (map<int, int>::iterator i = g.begin(); i != g.end(); i++) {
		printf("%d %d\n", i->first, i->second);
	}
	return 0;
}

题解

1. map
2. 排序

Luogu P4305

参考资料

https://en.wikipedia.org/wiki/Hash_table