JDK源码分析之——HashMap（JDK1.8）
HashMap原理与数据结构
HashMap是对Map接口的一种非同步的实现，提供了基于哈希表的操作，允许null的Key也允许null的value。HashMap无法保证元素的插入顺序，插入元素的位置跟key的hashcode相关，插入的顺序也可能伴随新元素的插入发生改变（resize）。 HashMap不是同步的。如果多个线程访问一个哈希映射的同时，并至少有一个线程修改Map的结构，它必须同步外部。
数据结构
HashMap底层数据结构本质上是一个数组跟链表的组合，JDK1.8对HashMap的实现做了一些优化。对比一下JDK1.7跟1.8的实现
JDK1.7
使用一个Entry数组存储元素，Entry中保存下一个元素的指针。数组的每个元素上形成一个链表。使用key的hashcode跟数组长度进行逻辑与操作决定元素在数组中的位置，如果同位置有元素，就放到链表最后。如果放入的元素hashcode大量相同，那么get操作的性能会变差，最差的情况下是O(n)。
JDK1.8
使用Node数组来存储数据（其实也是实现的Map.Entry
源码解读
hash函数
static final int hash(Object key) {
int h;
//key为空返回0,
//key的hashcode右移16位再与自己进行异或位运算，无符号右移16位，高16位变成0，高位参加hash运算，减少hash冲突 。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
异或运算：两者相等为0,不等为1。 以上是JDK1.8的hash方法实现。JDK1.7的实现要复杂一些。本质上都是为了最后减少hash冲突。 1、key的hash值进行无符号右移16位再与自己进行异或位运算。右移16位之后，高16位全部置0，低16位被高16位替换。再与自己进行异或之后，高16位都是跟0异或，值不变，低16位与原来的高16位进行异或。这样就对hash值进行了扰动。使得hash更均匀分布。
2、进行hash扰动之后，再用扰动后的hash值跟数组大小length-1进行逻辑与位运算。HashMap的length都是2的n次幂。这样设计的很巧妙，2的n次幂-1刚好保证二进制数每一位都是1，再与hash值进行逻辑与操作时，基本上可以确保只有两个相同的hash值才可能发生碰撞，放到数组的同一个位置上，形成链表。
3、为什么前面要进行hash扰动，因为实际使用的时候，HashMap的大小不会很大，16位二进制都是65536了，所以大部分情况下，如果不进行上面的hash扰动，高16位跟lenght-1与操作后都是0，这样高16位无法影响最终的索引，导致hash冲突的概率增加。扰动之后，高16位也参加了运算，hash值分布更均匀，下标更随机。
put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//判断key的hash值对应的位置是否有元素，没有就直接插入该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//hash对应的索引位置对象的hash值与插入的hash值相等，key也相等，则更新当前对象的值。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果对应索引位置对象是红黑树，则插入到红黑树。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//对应索引位置对象为链表，遍历链表，key以及hash值相等就更新值，没有相等的，就插入链表最后。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表的数量大于8，就变成红黑树结构存储
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//索引位置有值，从第一个元素开始查找
//hash值相等，key相等，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//依次遍历链表元素
if ((e = first.next) != null) {
//节点为红黑树结构，查找红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//节点为链表，依次查找下一个元素，直到找到hash值跟key相等的元素
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//map为空，直接返回null
return null;
}
扩容
当 HashMap 中的元素越来越多的时候，hash 冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对 HashMap 的数组进行扩容，扩容的过程是最消耗性能的，这是因为必须对原数组中的元素重新计算位置，并复制到新的扩容后数组。
HashMap是否需要扩容由threshold决定，大于这个数，就需要扩容了。 threshold = (int)(capacity * loadFactor); loadFactor的默认值为 0.75，当HashMap中元素个数超过threshold的时候，就把数组扩大一倍，然后重新计算每个元素在数组中的位置。
性能
影响HashMap性能的主要有一下因素： 1、hash分布是否均匀，也就是说发生hash冲突的概率高的话，会影响插入跟查询的性能。 2、插入的元素过多，未指定初始化容量的情况下，发生resize也会严重影响性能。 3、loadFactor指定太小的话，会造成空间浪费。指定太大，会影响查询效率。
HashMap的默认无参构造函数会创建一个初始容量为16，负载因子为0.75的HashMap。如果预先知道需要保存大量的数据，应该指定初始容量的大小，使用HashMap(int initialCapacity)来创建HashMap。这样插入数据的过程中，不会发生resize，可以提升性能。
高效的遍历方法
1、只需要获取value值，使用Collection
2、只需要获取所有key值，使用Set
3、需要通过key来获取value遍历，使用Set< Map.Entry< K, V>> entrySet()；虽然通过keySet返回所有key然后再get也可以，但是这种方式不如entrySet高效。