哈希即Hash，一般翻译为散列的意思，简单而言其实就是通过一个函数，将一个值映射成另一个更好的值。
这个更好，是一个比较抽象的概念。可以是把一个很大的数，映射到一个小的区间内，以作为数组索引；也可以是将一个非数值型数据，如字符串等映射成一个数值型数据，以实现更好的索引或者判重；又或者将一段很长的信息加密成一段短小的密文，以实现信息的保密传输等等。
x
=
H
(
k
)
x=H(k)
x=H(k)这里的
k
k
k 表示原始值或者哈希键值，
H
H
H 表示映射函数，
x
x
x 表示将哈希键映射后的结果值。
现在给出 n 个数(a[0],a[1],…,a[n-1])，且每个数的大小都是小于等于 1010 的非负数(0<=a[i]<=1010)，现需要统计每个数的出现次数，并从小到大依次输出，且 n 是小于等于 100 的正整数(0<n<=100)。
输入样例：
10
12 116 87 105 12 605 8998 87 12 105
输出样例：
12 3
87 2
105 2
116 1
605 1
8998 1
我想许多人拿到这类题的第一感觉就是，直接利用数组的下标索引标记每个数，然后每次出现 i ，便令 x[i]++ 即可。确实，这样的算法非常灵活地运动了下标，在统计计数地过程中也达到了线性时间复杂度，是最优的算法了，代码如下：
#include <stdio.h>
#define MAX 10000000000
int x[MAX+5] = {0};
int main()
{
int n,a;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
x[a]++;
}
for(int i=0;i<=MAX;i++)
x[i]>0?printf("%d %d\n",i,x[i]):1;
}
然而事实是编译的时候出现了错误:
显然，由于题目中的 a[i] 最大可以到 1010 ，因此这里的计数数组也需要开到这么大，但显然，这个大小早已超出了一般情况下程序所能开出数组的最大大小。
同时，注意到一件事情，虽然 a[i] 的大小很大很大，但是 n 很小很小最大仅到100。这也将说明得到的计数数组 x[] 将特别特别稀疏，毕竟现在是将 100 个数放到 1010 个位子上，从概率上来说平均每个位子仅有 1/108 个数，而最后输出我们只需要将 x[i]>0 的部分进行输出，换句话说，数组 x[] 存在大量的空间冗余。
这时候我们便能考虑到，如果能通过一个映射函数，将这 100 个 0~1010 的数映射到一个更小的区间上，例如 0~200 或者 0~1000 等，这样便能实现空间的压缩，使得计数数组 x[] 所需的空间大小小上几个数量级，同时也让其变得更加密集，以提高空间利用率，另一方面程序也不会因数组过大而报error，这即是哈希的思想。考虑如下一个最简单的哈希映射函数：
H
(
k
)
=
k
m
o
d
m
H(k)=k\ mod\ m
H(k)=k mod m这里 m 相当于要映射到的区间的大小，相当于就是将每一个 x[i] 对 m 进行求模取余，显然这个余数的最大值不会超过 m 。
在这个题目中，只需要保证 m>=100 即可，换句话说，我们需要保证这 100 个数每个数都必须有位子记录。假设令 m=101，那么对于题目的样例而言，便会有如下映射关系：
这样一来每个 a[i] 确实都映射到了一个更小的空间，但我们思考一个问题，如果在上面的基础上，再加入一个数 a[i]=113 ，计算哈希值发现 113%101 = 12，与数 12 的哈希值一样，出现了冲突，换句话说，每一个 a[i] 可以被唯一的映射成一个 0~m 之间的数，但并不能保证每一个 0~m 之间的数，都唯一的对应一个 a[i] ，任何一个满足 i + m × k ( k ∈ N ) i+m×k (k \in N) i+m×k(k∈N) 的数得到的哈希值都将相同，等于 i ，这便出现了所谓的碰撞冲突，既然出现了问题，肯定也会有相应的解决方法，请接着往下看。
哈希冲突是由于不同键值经过哈希函数后产生相同的哈希值而产生的情况，可以说这种情况的发生是必然的。
解决碰撞冲突的思路有两个，其一是为冲突发生的情况下，设置新的规则来应对，比方说，如果出现冲突，那么就从冲突出现位置顺序往后找，直到找到一个空的位子，填上去；或者是隔几个位子跳着跳着找；又或者是在冲突出现的位置链接上一条链表，依次记录相同哈希值元素的出现次数。我们着重介绍下这几种常用的方法。
顾名思义，若出现冲突，则逐个往后或往前搜索，直到找到空的位子。
| Hash(k) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| k | 10 | 98 | 44 | 3 | 1 | 9 |
假设现在又出现一个元素 20 经哈希函数后得到的映射结果也是位置 0 ，而发现该位置已被元素 10 所占据，那么就可以线性向后查找，直到找到第一个空的位置 2 ，然后放上去。(若找到了哈希表结尾，则回到开头继续向后查找，由于保证了哈希表的大小一定比元素总个数多，所以能保证每个元素都能找到自己的位置)
| Hash(k) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| k | 10 | 98 | 20 | 44 | 3 | 1 | 9 |
但这样有一个弊端就是，此时 20 占据了一个本不属于它的位置 2 ，如若下次来了一个本就映射到位置 2 的元素，那么它也只好继续向后探测，换句话说，虽然你解决了一个冲突，但同时又产生了另一个产生冲突的隐患，而且甚至还有可能出现无限冲突的情况。另一方面对于要在表中删除元素的情况，处理起来也不太方便。
这种思想是将所有映射到位置 i 的元素构建一条链表，并将单链表的头指针存在哈希表的第 i 个单元中，这样做的好处是一方面不会出现前面方法的那种解决一个哈希冲突，又带了新冲突隐患的问题，另一方面是在元素的删除上也能很好的处理，只需删除对应节点即可。但缺点也有，就是可能会在某个位置出现一条很长很长的链，增加了时间的开销。
这种方式是选取多个哈希函数，若第 j 个哈希函数出现了冲突，那么选用第 j+1 个哈希函数计算，直至找到不发生冲突的哈希函数。又或者使用同一个哈希函数，以上一轮产生的哈希值作为键值进行再次映射，直至找到可用的位置。
除了以上这些方法外，还有很多类似的方法，如平方探测法等等，这类处理思路都是着重于当冲突发生的时候如何处理，此外，另一种解决冲突的思想便是在冲突发生之前尽可能的减少冲突的发生概率，即设计更好的哈希函数。
显然，冲突的产生其实很大的一部分原因是由于哈希函数设计得不够好，一个更好的哈希函数应该是让不同键值尽量映射到不同的位置，或者说尽可能地做到随机映射。
不难想到，一张更大的哈希表能降低冲突发生的概率，以之前的简单哈希函数为例，极端情况是如果把 m 取得很大到 1010 时，那么显然就不会发生冲突了。一般而言，在经验和习惯上，会将哈希表的大小设置在元素个数的 1~10 倍之间，以实现在较小空间冗余的代价上，减小冲突的发生，提高时间效率。
之前提到的最简单的哈希函数，被称为除留余数法，可以说没有对键值 k 作任何的处理，直接进行了求余数，而如果我们加上些其它的运算，便能够使得映射更加复杂，以达到更随机的映射效果。例如下面的一阶线性映射：
H
(
k
)
=
(
a
×
k
+
b
)
m
o
d
m
(
a
,
m
∈
Z
)
H(k) = (a×k + b)\ mod\ m (a,m \in Z)
H(k)=(a×k+b) mod m(a,m∈Z)从理论上来说， a、b、m取不要太接近2的幂或10的幂的数会更好(同理前面简单取余的哈希函数里的 m 也一样)，冲突率更小，有兴趣的可以上网找找相关证明，这里之间简单说一下如果 m 取偶数，由于一个偶数对偶数取余结果仍然是偶数，这将导致所有的偶数元素只能映射到偶数位置，显然将会导致分布不均匀，容易出现冲突。
再来看看下面的乘法映射。
H
(
k
)
=
(
A
⋅
k
m
o
d
2
w
)
r
s
h
(
w
−
r
)
H(k) = (A·k\ mod\ 2^w)\ rsh\ (w-r)
H(k)=(A⋅k mod 2w) rsh (w−r)其中 m=2r ，w 表示计算机一个字的长度的bit位数，A 为奇数，且 2(w-r) < A < 2w(A不能太接近2w-r和2w)， rsh 指右移运算。
这是一个快速的哈希算法，介于编译器对这些二进制运算的优化，有兴趣的查阅相关资料，这里不做过多说明。
其实在我看来，哈希函数就是乱搞，搞得越乱越随机越好，有兴趣的可以了解一下全域哈希与完全哈希，理论上可以无限接近随机映射，使得在绝大多数情况下不会出现冲突。