HashMap的数据结构
在java编程中最基本的结构就两种：一个是数组，另一个是模拟指针（引用），所有的数据结构都可以通过这两种类构造，HashMap也不例外。HashMap实际上就是一个数组和链表的结合体（JDK1.8之前）。JDK1.8之后增加了红黑树。（本文图片均来自网络，侵删）
HashMap的主干是Entry数组，每个数组元素Entry存放着一个键值对和同时指向另一个Entry的引用，如果发生哈希冲突，该引用即指向另一个Entry。
上图中横向表示数组，纵排表示数组元素，实际上是一个链表，链表是为了解决哈希冲突（或者哈希碰撞）。
文章一下所有的实例和源码都是基于JDK1.8
HashMap的“扰动函数”
//java8中hash的优化函数
static final int hash(Object key){
int h;
return (key==null)?0:(h=key.hashCode())^(h>>>16);
}
这个叫做“扰动函数”，做了一次16位 右位移 异或 混合运算。
右位异16位正好是32bit的一半，自己的高半区和低半区进行异或，就是为了混合原来哈希码的高位和地位，以此来加大低位的随机性。而且低位掺杂了高位的部分特征，这样高位的信息也被变相的保存下来。
为什么不直接用key.hashCode()访问HashMap的下标。
key.hashCode()调用的是key的类型自带的哈希函数，返回的是int类型的散列值。而2进制32位带符号的int的取值范围是-2147483648到2147483648，差不多40亿的映射空间，只要哈希函数的散列值均匀松散，就很慢出现碰撞。
但问题是40亿的映射空间，内存是放不下的。所有这个散列值是不能直接拿来用的。
java8目前采用的什么方式定位HashMap的下标。
index = hash(Key)&(Length-1)
把key的哈希值和数组长度做取模运算？取模运算的方式固然简单，但Java中的取模运算一般需要用“乘法，整除，减法”等步骤来实现，效率不高。
但是对“2的n次幂“之类的数进行取模有一种效率更高的算法，即hash(Key)&(Length-1), 也就是说可以用与运算来进行取模。
因为hashMap的长度正好取2的整次幂，这样Length-1 之后的二进制都是高位全为0，低位全为1的形式。假设hashMap的长度是16，Length-1的十进制就是15，二进制00000000 00000000 00001111。 与运算的结果就是把散列值的高位全部归零，只保留低4位，用来做下标方位。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101//高位全部归零，只保留末四位
以上两个做与运算，十进制是5，所以index=5，可以说Hash算法最终得到index，完全取决于key的hashcode的最后几位。
为什么HashMap的数组长度要取2的整次幂
1、取2的整次幂，不但结果等同于取模，而且还提高了性能，Length为2的整次幂，hash(Key)&(Length-1) 才等价于hash(Key)%Length。
2、当数组长度为2的n次幂的时候，不同的key算出的index相同的几率较小，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
假设HashMap的长度是10，
hash： 10100101 11000100 00101001
Length-1：& 00000000 00000000 00001001
-----------------------------------------------------
index: 00000000 00000000 00001001
单独看这个结果，并没有什么问题，我们在试几个hash值：
hash： 10100101 11000100 00101111
Length-1：& 00000000 00000000 00001001
-----------------------------------------------------
index: 00000000 00000000 00001001
hash： 10100101 11000100 00101011
Length-1：& 00000000 00000000 00001001
-----------------------------------------------------
index: 00000000 00000000 00001001
hash： 10100101 11000100 00101101
Length-1：& 00000000 00000000 00001001
----------------------------------------------------
index: 00000000 00000000 00001001
运算的结果都1001，也就是说当hashmap的长度为10时。有些index结果的出现几率更大，而有些index结果永远不会出现（比如0111）。这样，显然不符合Hash算法均匀分布的原则。
反观长度为16或者2的整次幂，Length-1的所有二进制都为1，index的值就等同于hash值的后几位的值。只要输入的hashCode本身分部均匀，这种算法（index = hash(Key)&(Length-1)）的结果就是均匀的。
HashMap的put和get方法
1、put(K key,V value)方法
源码如下：
/**
* 添加key-value键值对
*
* @param key 键
* @param value 值
* @return 如果原本存在此key，则返回旧的value值，如果是新增的key-
* value，则返回nulll
*/
public V put(K key, V value) {
//实际调用putVal方法进行添加 key-value 键值对操作
return putVal(hash(key), key, value, false, true);
}
/**
* 根据key 键 的 hashCode 通过 “扰动函数” 生成对应的 hash值
* 经过此操作后，使每一个key对应的hash值生成的更均匀，
* 减少元素之间的碰撞几率（后面详细说明）
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 添加key-value键值对的实际调用方法（重点）
*
* @param hash key 键的hash值
* @param key 键
* @param value 值
* @param onlyIfAbsent 此值如果是true, 则如果此key已存在value，则不执
* 行修改操作
* @param evict 此值如果是false，哈希表是在初始化模式
* @return 返回原本的旧值, 如果是新增，则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 用于记录当前的hash表
Node<K,V>[] tab;
// 用于记录当前的链表结点
Node<K,V> p;
// n用于记录hash表的长度，i用于记录当前操作索引index
int n, i;
// 当前hash表为空
if ((tab = table) == null || (n = tab.length) == 0)
// 初始化hash表，并把初始化后的hash表长度值赋值给n
n = (tab = resize()).length;
// 1）通过 (n - 1) & hash 当前元素的hash值 & hash表长度 - 1
// 2）确定当前元素的存储位置，此运算等价于 当前元素的hash值 % hash表的长度
// 3）计算出的存储位置没有元素存在
if ((p = tab[i = (n - 1) & hash]) == null)
// 4) 则新建一个Node结点，在该位置存储此元素
tab[i] = newNode(hash, key, value, null);
else { // 当前存储位置已经有元素存在了(不考虑是修改的情况的话，就代表发生hash冲突了)
// 用于存放新增结点
Node<K,V> e;
// 用于临时存在某个key值
K k;
// 1)如果当前位置已存在元素的hash值和新增元素的hash值相等
// 2)并且key也相等，则证明是同一个key元素，想执行修改value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 将当前结点引用赋值给e
else if (p instanceof TreeNode) // 如果当前结点是树结点
// 则证明当前位置的链表已变成红黑树结构，则已红黑树结点结构新增元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// 排除上述情况，则证明已发生hash冲突，并hash冲突位置现时的结构是单链表结构
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
// 大于等于8则将链表转换成红黑树
treeifyBin(tab, hash);
break;
}
// 如果链表中已经存在对应的key，则覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 已存在对应key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //如果允许修改，则修改value为新值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 当前存储键值对的数量 大于 阈值 是则扩容
if (++size > threshold)
// 重置hash大小，将旧hash表的数据逐一复制到新的hash表中（后面详细讲解）
resize();
afterNodeInsertion(evict);
// 返回null，则证明是新增操作，而不是修改操作
return null;
}
举个简单的例子：
比如调用 hashMap.put("apple", 0) ，插入一个Key为“apple"的元素。利用哈希函数确定插入的位置index（hash("zhang")），
假定计算的index=2，那么把把这个键值对就存放到2这个位置上，如图
当插入的Entry键值对越来越多时，难免会出现hash冲突的情况，比如下面这种。
这个时候就需要用到上面提到的链表结构了。
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可：
新来的Entry节点插入链表时，使用的是“尾插法”。
p.next = newNode(hash, key, value, null);
p记录当前的链表结点，p结点的next引用指向新新元素结点，将新元素结点放在当前结点的next指向的位置，也就是插入到当前结点的后面位置。
put(K key,V value)方法的整体流程图如下：
1、get(Object key)方法
源码如下：
/**
* 返回指定 key 所映射的 value 值
* 或者 返回 null 如果容器里不存在对应的key
*
* 更确切地讲，如果此映射包含一个满足 (key==null ? k==null :key.equals(k))
* 的从 k 键到 v 值的映射关系，
* 则此方法返回 v；否则返回 null。（最多只能有一个这样的映射关系。）
*
* 返回 null 值并不一定 表明该映射不包含该键的映射关系；
* 也可能该映射将该键显示地映射为 null。可使用containsKey操作来区分这两种情况。
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
// 1.先调用 hash(key)方法计算出 key 的 hash值
// 2.随后调用getNode方法获取对应key所映射的value值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 获取哈希表结点的方法实现
*
* @param hash key 键的hash值
* @param key 键
* @return 返回对应的结点，如果结点不存在，则返回null
*/
final Node<K,V> getNode(int hash, Object key) {
// 用于记录当前的hash表
Node<K,V>[] tab;
// first用于记录对应hash位置的第一个结点，e充当工作结点的作用
Node<K,V> first, e;
// n用于记录hash表的长度
int n;
// 用于临时存放Key
K k;
// 通过 (n - 1) & hash 当前元素的hash值 & hash表长度 - 1
// 判断当前元素的存储位置是否有元素存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//元素存在的情况
// 如果头结点的key的hash值 和 要获取的key的hash值相等
// 并且 头结点的key本身 和要获取的 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) // 如果当前结点是树结点
// 则证明当前位置的链表已变成红黑树结构
// 通过红黑树结点的方式获取对应key结点
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {// 当前位置不是红黑树，则证明是单链表
// 遍历单链表，逐一比较链表结点
// 链表结点的key的hash值 和 要获取的key的hash值相等
// 并且 链表结点的key本身 和要获取的 key 相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 找到对应的结点则返回
return e;
} while ((e = e.next) != null);
}
}
// 通过上述查找均无找到，则返回null
return null;
}
使用get方法根据key来查找value的时候，首先会把输入的key做一次hash映射，得到的hash值和数组长度-1进行与运算，得到index。
由于刚才所说的hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的key是“banana”：
index = hash（“banana”）&(length - 1)
第一步，我们查看的是头节点Entry1，Entry1的key是apple，显然不是我们要找的结果。
第二步，我们查看的是next节点Entry6，Entry1的key是banana，正是我们要找的结果。
HashMap的扩容resize
HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，Key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize。
影响发生Resize的因素有两个：
1、Capacity
HashMap的当前长度。
2、LoadFactor
HashMap负载因子，默认值为0.75f。
衡量HashMap是否进行Resize的条件如下：
HashMap.Size >= Capacity * LoadFactor
HashMap的Resize 经历一下两个步骤：
1.扩容
创建一个新的Entry空数组，长度是原数组的2倍。
2、rehashing
遍历原Entry数组，把所有的Entry重新重新放到新数组。具体的复制过程如下：
1、如果链表只有一个，则进行直接赋值
2、如果是红黑树，......
3、如果链表有多个结点，比较特殊： 它并没有重新计算元素在数组中的位置，而是采用了 原始位置加原数组长度的方法计算得到位置。
是根据(e.hash & oldCap) == 0将原来的链表拆分成两个链表，然后
如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) != 1 则该节点在新表的下标位置 j + oldCap
对(e.hash & oldCap) == 0的理解：
因为oldCap是2的n次幂，所以二进制始终是高位为1，其他位都是0。
比如oldCap=8时，二进制位1000；oldCap=16时，二进制位10000；oldCap=32时，二进制位100000；
下面举个例子来看，e.hash & oldCap 运算结果：
//e.hash=13时，结果为0
oldCap=16 0001 0000
e.hash=13 0000 1101
e.hash & oldCap=0 0000 0000
//e.hash=17时，结果为16(非0)
oldCap=16 0001 0000
e.hash=17 0001 0001
e.hash & oldCap!=0 0001 0000
//e.hash=34时，结果为0
oldCap=16 0001 0000
e.hash=13 0010 0010
e.hash & oldCap=0 0000 0000
//e.hash=50时，结果为16(非0)
oldCap=16 0001 0000
e.hash=13 0011 0010
e.hash & oldCap!=0 0001 0000
也就是说(e.hash & oldCap)，它有两种结果，一个是0，一个是oldCap（非0）。
参考文章：
JAVA容器-自问自答学HashMap
数据结构——浅谈HashMap
漫画：什么是HashMap？
JDK 源码中 HashMap 的 hash 方法原理是什么？
深入理解HashMap(四): 关键源码逐行分析之resize扩容
Java 1.8中HashMap的resize()方法扩容部分的理解
欢迎转载，但是请注明出处
