看到这个题目一般脑海里面都是 HashMap是啥?怎么用(zhuang bi)?用了有什么好处?可惜我并不打算讲这些，只会对一些小问题进行说明。
在阅读HashMap的源码时，我们会遇到很多问题，导致其很难理解，本文就是对这些问题进行扫盲的。
一 数据结构之其实我只是个数组
1 HashMap的核心数据结构是什么?
各位看了源码就应该知道其实HashMap操作的对象就是Node<K,V>[] table(一个Node对象的数组)
而Node对象的源码如下:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
....//省略若干代码
}
该对象的Node<K,V> next，是数据结构链表的写法(一般都是用对象来实现链表)，所以本质上是一个数组，数组里面每个node都可能是个链表。
二 源码中的第一只老虎之Hash
每当我满怀信心的点开HashMap的源码时，总会被一个叫hash(key)的拦路虎拦下，而且不管从put还是get进去，第一句就是它，让我每次都脸上笑嘻嘻，心理...
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到上面的代码，我的内心是愉(jue)快(wang)的。既然要对它下手，首先心里面肯定要问几个问题的，比如这是什么鬼？我为什么要读这个？我脑子是不是有问题?
等对自己灵魂进行拷问后，便得开始一步一步下手了。
(1). 首先key.hashCode()，就是从native方法获取哈希值，这一般取决于jvm，这里就不详细介绍了。你只需要知道它会返回int值，而int值最大位数是32位就行。
(2). 接下来(h = key.hashCode()) ^ (h >>> 16)，要了解这一句，首先要从几个小问题入手。
2.1 为什么不用&与 |或而要用^异或呢?
举个例子大家就能明白，stackoverflow
与 &
A 0011
B 0101
0001 //与操作所得
或 |
A 0011
B 0101
0111 //或操作所得
异或 ^
A 0011
B 0101
0110 //异或操作所得
从上面可知，与操作会使结果偏向于0，而或操作会使结果偏向于1，只有异或能使0和1均匀分布，打散其趋势。
而如果想要减少hash算法的碰撞的话，肯定是需要更加分散的值。
2.2 什么情况下容易发生碰撞?
2.2.1 数组下标算法
我们取table数组下标的方法是i = (n - 1) & hash，一个table默认的长度是16位，所以最后的公式相当于(15)0x1111 & hash ，生效的是低4位，很容易发生碰撞。
而扩容一倍后(扩容都是2的幂次方)，(31)0x11111 & hash，还是容易发生碰撞。从中我们可以发现，hashMap在长度较短时是很容易发生碰撞的。
2.2.2 低位散列分布
所以HashMap会对哈希值的低16位进行异或操作，让其低16位更加散列分布，减少碰撞。
上面两个问题搞懂，就可以理解(h = key.hashCode()) ^ (h >>> 16)这句代码的意思了。
三 你再碰撞，我就用红黑树
3.1 多次碰撞会发生什么?
我们知道每当发生了碰撞，HashMap就会生成链表来存数据，而链表查询效率是很低的。
当多次碰撞后链表就会越来越长，查询效率就会越来越低，这显然是不能忍受的。
虽然前面通过对低16位的异或来降低碰撞，但是还是可能出现多次碰撞的情况。
3.2 如何避免多次碰撞?
其实不用担心，在JDK1.8里面HashMap使用了红黑树来代替链表，提高了查询效率。
//TREEIFY_THRESHOLD = 8
//如果数量大于TREEIFY_THRESHOLD则使用红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
四 扩容
4.1 什么时候会扩容?
当table数组里面内容达到一定时(DEFAULT_LOAD_FACTOR=0.75f)，碰撞率会越来越高，这时就会对其进行扩容resize()。
4.1 扩容原理是什么?
扩容原理也很简单，喜新厌旧，就是用新的数组把旧的数组替换了，步骤也就2个。
-
newCap = oldCap << 1通过移位算法来使新数组的容量扩充一倍(2的幂次方)。 - 重新计算hash将旧数组的内容放入新的数组里。
可以看出这样成本十分高，所以应该尽量减少扩容行为。
结语
HashMap的知识点就总(chui)结(niu)完毕，还有比如红黑树等细节的地方，当然还是得读者自己去探寻(我也不会...)
如有不对之处还望大家海涵，望大家指出。
