2015年最后一天，写篇文章记录一下我对hash算法的理解以及其在java集合框架中的应用以及其他地方的应用的大概介绍，算是一个比较系统的总结吧。文章参考了网上一些大神的文章（在文章末尾我会把参考文章写上），但是网上的文章很多都没有一个应用场景，读起来虽然知道了原理但是还是用不出来，我会结合平时做项目中遇到的一些问题来说明一些集合框架的具体使用。
--致敬2015
Hash介绍
基本概念
Hash其实就是散列，就是把任意长度的输入，通过散列算法变成固定长度的输出，由于是不定到定长，所以这种变换是一种压缩映射，输出值的值域远远小于输入值的值域，所以不同的输入可能会有相同的输出，这就是Hash碰撞。
解决冲突
- 开放地址法:当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m i=1，2，…，n,其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。
- 再hash法:当发生冲突时再次散列，如果依然冲突的话，可以变为多重散列或者结合其他解决冲突的方法使用。
- 链地址法:在发生冲突的地方，以链表的形式存储（HashMap就是这么做的）
- 建立公共溢出区:建立一个公共溢出区，将冲突的值放在溢出区。
什么是哈希表？
哈希表也叫散列表，是根据关键字而直接进行访问内存存储位置的数据结构。它通过把关键字通过散列函数映射到哈希表中的一个位置来访问记录，以加快查找的速度。存放记录的数组叫做散列表。哈希表就是一种依托于数组的数据结构，只不过增加了一些规则来在数组上存储元素和访问元素。
hash在java中的应用
java对象的equals和hashCode方法
java中Object类默认的equals方法和==一样，是比较两个对象的地址是否相等的，hashCode方法是返回对象的存储地址的（hashCode是一个native方法哦，是通过JNI用其他语言实现的）。
但是一般情况下，我们并不需要去比较两个对象的地址（需要的时候我们完全可以用==），所以我们可以选择重写equals方法来比较对象的内容，在我们的业务逻辑里面，对于一个人物实体类，只要身份证属性相同，就可以认为这两个人相同，所以我们选择覆盖equals方法来比较身份证属性。
重写equals方法后，一定要记得重写hashCode方法，因为如果该对象如果出现在了使用了Hash表结构的java集合框架中的话，会首先比较该对象的hashCode方法，如果相同，再比较equals方法，如果相同，则覆盖之前的对象，不同，则用链表的方式存储这两个对象。试想一下，对于一个身份证信息相同的对象，如果只重写了equals方法，那么这两个在业务逻辑上应该被判断为相同的对象就会被重复存储。
java中对于equals和hashCode有两个约定：
- 当obj1.equals(obj2)为true时，obj1.hashCode() == obj2.hashCode()必须为true
- 当obj1.hashCode() == obj2.hashCode()为false时，obj1.equals(obj2)必须为false
也就是说，hashcode相等，equals可能不相等，但是equals相等代表这两个对象是是一个对象，所以hashCode必须相等。
HashMap
HashMap使用数组加链表的方式实现的，当存在hashCode相同但是equals返回false的两个对象时，会使用链地址法来解决冲突。
HashMap中我们最常用的就是put(K, V)和get(K)。我们都知道，HashMap的K值是唯一的，那如何保证唯一性呢？我们首先想到的是用equals比较，没错，这样可以实现，但随着内部元素的增多，put和get的效率将越来越低，这里的时间复杂度是O(n)，假如有1000个元素，put时需要比较1000次。
实际上，HashMap很少会用到equals方法，因为HashMap通过一个哈希表管理所有元素，当我们调用put存值时，HashMap首先会调用K的hashCode方法，获取哈希码，通过哈希码快速找到某个存放位置，这个位置可以被称之为bucketIndex，通过上面所述hashCode的协定可以知道，如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为true。
所以理论上，hashCode可能存在冲突的情况，有个专业名词叫碰撞，当碰撞发生时，计算出的bucketIndex也是相同的，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是哈希码碰撞时才会执行的方法，所以前面说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在，如果hashCode和equals相等，则使用新V值替换旧V值，（若hashCode相等当equals为false，则链式存储存储解决冲突）并返回旧V值，如果不存在 ，则存放新的键值对<K, V>到bucketIndex位置。
存放元素的过程如下图所示：
HashMap去除一个元素就很简单了，如下代码所示
public V get(Object key) {
// 若为null，调用getForNullKey方法返回相对应的value
if (key == null)
return getForNullKey();
// 根据该 key 的 hashCode 值计算它的 hash 码
int hash = hash(key.hashCode());
// 取出 table 数组中指定索引处的值
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key与查找的key相同，则返回相对应的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
需要注意的是在HashMap中，不是直接用的对象的hashcode作为对象存储地址的，而是再次hash，这么做可以防止重写hashCode方法以后使存储地址非法。内部hash实现如下
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
（>>>是无符号右移）
HashMap内部定义了一个Entity泛型对象来存储每个键值对信息。如下所示：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
}
Entry为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，这是非常重要的，正是由于Entry才构成了table数组的项为链表。
HashSet
知道了HashMap以后，HashSet其实就是HashMap的键的存储。所以就不赘述啦~~
hash在其他地方的应用
- MD5加密是将任意长度的字符串散列成32位的定长字符串（由小写字母和数字组成）。
- SSH中对证书信息进行散列获取证书信息。
- SHA1加密算法也是一种运用散列进行加密的算法。
