背景
散列（hash）是常见的算法思想之一，在很多程序中都会有意无意地使用到。
若给出$N$个正整数，再给出$M$个正整数，问这M个数中的每个数分别是否在$N$个数出现过，其中$N,M\leq10^5$，且所有正整数均不超过$10^5$。
对这个问题，最直接的思路是：对每个欲查询的正整数$x$，遍历$N$个数，看是否有一个数与x相等。这种做法的时间复杂度是$O(NM)$，当$N$和$M$都很大（$10^5$级别）时，显然是无法承受的。
不妨用空间换时间，即设定一个bool型数组hashTable[100010]，其中hashTable[x]==true表示正整数$x$在$n$个正整数中出现过。这样就可以在一开始读入$N$个正整数时就对hashTable进行赋值，于是对于$M$个欲查询的数，就能直接通过hashTable判断出每个数是否出现过。显然这种做法的时间复杂度为$O(M+N)$。
同样的，如果题目要求统计次数而非是否出现，就把数组改成int型，这两个问题的解法都有一个特点，那就是直接把输入的数作为数组的下标来对这个数的性质进行统计（这种做法非常实用，请务必掌握）。这是一个很好的用空间换时间的策略，因为它将查询的复杂度降到了$O(1)$级别。
但这个策略暂时还有一个问题——上面的题目中出现的每个数都不会超过$10^5$，因此直接作为数组下标是可行的，但是如果输入可能是$10^9$大小的整数，或者甚至是一个字符串，就不能将它们直接作为数组下标了。这时可以使用散列。
散列/哈希简介
一般来说，可以精简地将散列定义为“将元素通过一个函数转换为整数，使得该正数可以尽量唯一地代表这个元素”，其中把这个转换函数称为散列函数H，也就是说，如果元素在转换前为key，那么转换后就是一个整数H(key)。
对于key是整数的情况来说，常用的散列函数有直接定址法、平方取中法、除留余数法。
H(key1)==H(key2)，这种情况叫作冲突。常用的解决冲突的方法有线性探查法、平方探查法和链地址法，其中前两种都计算了新的hash值，又称为开放定址法。
在写代码时，这种散列的功能可以用STL中的map代替。
哈希函数、哈希表、哈希地址
根据设定的哈希函数$H(key)$和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集上的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置成哈希地址或散列地址。
冲突、同义词
不同的关键字经哈希函数映像后求得到的哈希地址可能相同，即$key1\neq key2\ and \ H(key1)=H(key2)$，这就是冲突（collision）；具有相同哈希地址的关键字对该哈希函数来说就是同义词（synonym）。
哈希函数选得合适可以减少冲突现象。
一般情况下，哈希函数是一个压缩映像（关键字集合到地址集合的映像，而关键字集合的大小远大于地址集合），因此冲突只能尽可能地少而不能完全避免。
哈希函数的构造方法
常用的构造哈希函数的方法有：
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
处理冲突的方法
处理冲突过程中会有一个地址序列$H_i,i=1,2,\dots,k$，即如果发生冲突，就去找下一个地址。
通常用的处理冲突的方法有下列几种：
- 开放定址法
- 再哈希法
- 链地址法
- 建立一个公共溢出区
开放定址法
其中$H(key)$为哈希函数；$m$是哈希表表长；$d_i$为增量序列，可以有下面3种取法：
- $d_i=1,2,3\dots,m-1$，称为线性探测再散列
- $d_i=1^2,-1^2,2^2,-2^2,3^2,\dots,\pm k^2,(k\leq m/2)$，称为二次探测再散列
- $d_i=伪随机数序列$，称为伪随机探测再散列
字符串hash
一个点$P$的坐标$(x,y)$可以用下面的散列函数进行处理：
$H(P)=x\times Range+y$，这样对数据范围内的任意两个整点$P_1$和$P_2$，$H(P_1)$都不会等于$H(P_2)$。
字符串hash是指将一个字符串$S$转换为一个整数,使得该整数可以尽可能地唯一地代表字符串$S$。本节只讨论将字符串转换为唯一的整数。
假设字符串$S$由大写字母$A \sim Z$构成。在这个假设下，可以把26个大写字母视为$0\sim25$，进而转换为二十六进制，再转换为十进制，可得一唯一整数。只是$S$的长度并不可太长。
在上面的假设下，假如还可以由$a\sim z$组成，可以再把$a\sim z$对应为$26\sim51$，进而转换为五十二进制，再转换为十进制。
作者：@臭咸鱼
转载请注明出处：https://www.cnblogs.com/chouxianyu/
欢迎讨论和交流!