重写hashcode，玩儿坏HashMap
缘起
提到HashMap，都知道“线程不安全，并发情况下不能用”，除此之外貌似了解的不是很多。
对，我就是其中一员。
这两天跟两个开发大神学习了一下，并参考了网上的一些文档，浅显整理如下。
关键点
1.HashMap的定位是单线程高性能的 key-value 存储数据结构，多线程请使用ConcurrentHashMap。
2.HashMap性能好坏的关键是避免hash冲突，以及冲突很多的情况下，如何更高效。
前提：完美Hash函数不存在
如果让每个key的hashcode都不一样，那无疑是最高效的，但实际的情况是不可能的，因为你没有无限的内存，这种假设不成立。
所以，Java中实现HashMap的hashcode返回值是整形，根据鸽笼理论，当我们的对象超过整形最大值时，这些对象会发生哈希碰撞。
实现：分桶
除了上面完美Hash函数不存在，通过允许合理的哈希碰撞来节省内存，也是HashMap的考虑，而且很多情况下，Hash值经常集中在几个特定的值上
所以，看HashMap源码：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16默认是分了M=16个桶来进行分桶存储。所以，冲突的概率是1/M。
冲突后的实现：分离链表
下图是HashMap的数据结构图，前面是桶，后面是每个桶的链表结构。
当桶没有出现hash冲突时，hashmap查找元素是很快的。但桶hash冲突后，每个桶就变成了单的链表。
这种情况只能顺序遍历每个节点，直到找到想搜索的节点为止，极端情况，会达到最坏时间复杂度。(见下面：java8优化点)
但这种实现，至少比另一种实现方式：开放寻址的方法要好，理由如下：（摘自网络）
开放寻址使用连续的空间，因此有着缓存效率的提升。因此当数据量较小时，能够放到系统缓存中时，开放寻址会表现出比分离链接更好的性能。
但是当数据量增长时，它的性能就会越差，因为我们无法期待一个大的数组能够得到缓存性能优化。
这也是HashMap使用分离链表来解决哈希冲突的原因。此外，开放寻址还有一个弱点。我们调用remove()方法会十分频繁，当我们删除数据时，一个特定的哈希冲突，可能会干扰总体的性能，而分离链表则没有这样的缺点。”java8优化分离链表：引入红黑树
除了最坏复杂度之外，如果数据很多，hash值不平均，比如集中在某几个特定的值上，使用树会比链表有着更快的性能。
所以，java8里面使用如下策略进行链表or树结构的转换。即：当冲突的元素数=8时，链表变为树；当减少到6时，树切换为链表。
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;补充说明：（摘自网络）
另外，java8里面，HashMap使用Node类替代了Entry类，它们的结构大体相同。
但显著地差别是，Node类具有导出类TreeNode，通过这种继承关系，一个链表很容易被转换成树。冲突还是要解决，动态扩容桶
哈希桶的默认数量是16，最大值是整形最大值。如果桶数量不变，即便上述内容，性能也不会明显的提升，
所以，HashMap使用下面方式进行动态扩容。
当桶数量超过当前值 * DEFAULT_LOAD_FACTOR 时，就自动扩容，然后重新插入所有数据。
例如当桶数到达: 初始桶数16*阀值0.75 = 12时，自动扩容到 16*2 = 32个桶。这样，冲突就立减降低，但重新插入性能也有损耗。 /**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;通过重写hashcode，论证上述内容
测试类如下：
package com.taobao.huachuan;
import java.util.HashMap;
import java.util.Map;
/**
* 对比hash冲突和不冲突
* @author sheshijie
*
*/
public class TestHashMap {
public static void main(String[] args) {
Map<TaoPP1, Integer> m1 =new HashMap<TaoPP1, Integer>();
Long start1 = System.currentTimeMillis();
for(int i = 0 ;i<10000;i++)
{
TaoPP1 tp1 = new TaoPP1();
tp1.setAge(i);
tp1.setValue(i);
m1.put(tp1, i);
}
System.out.println("hashcode不冲突的耗时："+(System.currentTimeMillis()-start1) +" size:" + m1.size());
Map<TaoPP2, Integer> m2 =new HashMap<TaoPP2, Integer>();
Long start2 = System.currentTimeMillis();
for(int i = 0 ;i<10000;i++)
{
TaoPP2 tp2 = new TaoPP2();
tp2.setAge(i);
tp2.setValue(i);
m2.put(tp2, i);
}
System.out.println("hashcode冲突的耗时："+(System.currentTimeMillis()-start2) +" size:" + m2.size());
Long start3 = System.currentTimeMillis();
System.out.println("不冲突寻址 "+m1.get(new TaoPP2())+"耗时："+(System.currentTimeMillis()-start3));
Long start4 = System.currentTimeMillis();
System.out.println("冲突寻址 耗时:"+m2.get(new TaoPP2())+"耗时："+(System.currentTimeMillis()-start4));
}
}
重写hashcode的方法如下：
/**
* 大量hashCode重复
*/
@Override
public int hashCode() {
return (age+value)%16;//反复调整，可以看出差距明显
}实际的测试结果为：
hashcode不冲突的耗时：16 size:10000
hashcode冲突的耗时：867 size:10000果然，差距真的好大。
调整hashCode方法 return (age+value)%1024;
测试结果为：
hashcode不冲突的耗时：31 size:10000
hashcode冲突的耗时：78 size:10000浅显的证明了hashcode冲突的多少，是性能的关键。
而冲突后查找性能更加缓慢，结果如下：
不冲突寻址 null耗时：0
冲突寻址 耗时:null耗时：9我是测试，写错了不要喷，要爱护我
我是测试，写错了不要喷，要爱护我
我是测试，写错了不要喷，要爱护我
重要的事情说三遍！
