[TOC]
本文转自其他人的博客。简化了一下，方便备忘。
概述
Hash一般翻译作散列也有直接音译作“哈希”。就是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。
散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。
哈希函数的应用非常广泛，各种校验、签名、密码，都是哈希函数应用的重要场景。
性质
- 确定性：哈希的散列值不同，那么哈希的原始输入也就不同。
- 不确定性：同一个散列值很有可能对应多个不同的原始输入。称为“哈希碰撞”。
实现
哈希函数的实现分为两部分：构造和解决冲突。
构造
哈希函数的构造应该满足以下准则：
- 散列函数的计算简单，快速。
- 散列函数能将关键字集合K均匀地分布在地址集{0,1，…，m-1}上，使冲突最小。
直接定址法
H(key) = key 或 H(key) = a·key + b
直接定址法，不会有哈希冲突。但实际这样使用的情况较少。
相乘取整法
H(key) = (int) ( m * ( key*A - (int)(key*A) ) ) 其中 0 < A < 1
注意：该方法最大的优点是m的选取比除余法要求更低。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取 0.61803……。
平方取中法
取关键字平方后的中间几位为哈希地址。
F(a) = a的中间三位。
H(key) = F(key^2)
除留余数法
H(key) = key MOD p (p ≤ m)
随机数法
H(key) = random (key)
jdk中HashMap的hash构造
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}
哈希冲突的解决
开放地址法
就是在发生冲突后，通过某种探测技术，去依次探查其他单元，直到探查到不冲突为止，将元素添加进去。
假如是在index的位置发生哈希冲突，那么通常有一下几种探测方式：
线性探测法（线性探测再散列）
向后依次探测index+1，index+2…位置，看是否冲突，直到不冲突为止，将元素添加进去。
平方探测法
不探测index的后一个位置，而是探测2i位置，比如探测20位置上时发生冲突，接着探测2^1位置，依此类推，直至冲突解决。
再哈希法：（双散列法）
在发生哈希冲突后，使用另外一个哈希算法产生一个新的地址，直到不发生冲突为止。这个应该很好理解。
再哈希法可以有效的避免堆积现象，但是缺点是不能增加了计算时间和哈希算法的数量，而且不能保证在哈希表未满的情况下，总能找到不冲突的地址。
链地址法（开散列法）
基本思想：
链表法就是在发生冲突的地址处，挂一个单向链表，然后所有在该位置冲突的数据，都插入这个链表中。插入数据的方式有多种，可以从链表的尾部向头部依次插入数据，也可以从头部向尾部依次插入数据，也可以依据某种规则在链表的中间插入数据，总之保证链表中的数据的有序性。Java的HashMap类就是采取链表法的处理方案。
结语
哈希表一旦发生冲突，其性能就会显著下降。因此建立哈希表时必须规避哈希冲突的产生，大多数哈希表的实现都是：第一步，是通过哈希算法将key值转换一个整数以确定数据的存储位置；第二步，检查是否发生哈希冲突，以及确定发生冲突后的处理方案。
