JDK1.8HashMap源码解析
数据结构
JDK1.8中的HashMap采用了数组加链表加红黑树的数据结构，就像这样：
每当插入一个元素的时候，就会对这个元素的键的Hash值按此时的数组长度取模，然后装入对应的位置。比如一个hash值为14的元素插入一个table长度为16的hashmap中，14对16取模是14，于是就装入14这个位置。不同的元素取模之后发生碰撞，比如30对16取模也等于14，这样也需要放入14的位置，于是就会在这个桶中形成链表。随着碰撞和扩容的不断发生，一旦链表长度超过8，并且数组长度超过64，链表就会被树化成为红黑树结构。
重点成员变量
HashMap中有三个重要的成员变量，他们之间有这样的关系：threshold=capacity*loadFactor threshold是一个阈值，每当表中元素超过这个值时，Hashmap就会扩容。capacity是hashmap此时的容量，默认是16。loadFactor叫做负载因子，默认是0.75，也就是说容量超过3/4就需要扩容。 除了这三个还有table，表示的是这个hashmap的结点数组。
新元素的插入
- 计算元素的位置。hash&(n-1)就是新元素的位置，n代表的是table长度。
- 查看对应位置是否有元素
- 如果没有，直接插入；如果有，进行hash碰撞的处理
- hash碰撞三种情况，一是碰撞的元素与要插入的元素hash值和key都相等，直接进行value的更新；二是结点类型是树结点直接，进行树结点的增加或更新；三是普通结点，只是hash碰撞，key不相同，于是增长链表。
- 插入之后，会进行hashmap大小的判断，如果元素数量超过了threshold，则会进行resize()扩容（后面有对这个方法的介绍）。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果table为空就resize()扩容，返回table长度给n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果选定的数组坐标处没有元素，直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果这个位置已经有元素，则进入else
else {
Node<K,V> e; K k;
//如果链表第一个元素或树的根的key与要插入的数元素重复，覆盖旧值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是tree，则调用putTreeVal
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果只是hash冲突，并且是链表，则进入esle
else {
//遍历链表，找到合适的处理方式 1插入新节点 2覆盖旧值
for (int binCount = 0; ; ++binCount) {
//在链表尾部插入新节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度大于等于八，变为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果链表中有一个节点key和新插入的key重复，则跳出循环。此时的e指向这个key重复的节点
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;
}获取value
- 通过hash值计算出位置，如果hash值相同，并且key相同，则返回vaule
- 否则进行下一个元素的比较（链表的下一个结点，或在红黑树中进行查找）
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) {
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);
do {//链表中查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}resize()方法
这个方法会将table扩容为原来的二倍，然后将扩容之前的table中的内容转移到新table之中。
转移的过程
在转移的过程中会进行结点类型的判断，如果是树结点，那么会进行树节点的修剪操作（修剪操作主要就是将一颗树分成两棵树分别挂到table[j]和table[j+oldCap]，如果树结点小于6，则转换为链表）；如果是普通结点，就会进行链表的“裁剪”，主要内容就是将一个链表分为两个链表，table容量已经成为了原来的两倍，原来table[j]处的链表上的元素将会分别挂到table[j]和table[j+oldCap]上。其实上边树节点的修剪操作跟这个普通结点的操作相比只是操作结点类型不同，操作完成的效果是一样的，树节点是一棵树变成两棵树，普通结点是一个链表变为两个链表。并且拆出的部分不管是树还是链表都挂到了table[j]和table[j+oldCap]，这是为什么？
为甚
我们对table尽行了扩容，正常来说我们应该使用hash&(newCap-1)重新计算每一个结点的位置。但hashmap实现中并没有这么做，我们上边说到将树分为两棵树，将链表分为两个链表，这两者分类方法都是一样的，其实就是对结点进行了一个判断：如果这个结点hash&oldCap==0为真那么他位置不变，仍然住到table[j]里，如果为假，那么它将住到table[j+oldCap]里。还是要问为什么这么判断呢？那么我们举个例子：如果oldCap=16,newCap=32,hash=14,那么hash&(newCap-1)=14,hash&(oldCap-1) 也等于14，此时hash&(oldCap)=0；如果hash=30那么hash&(newCap-1) = 30,并且hash&（oldCap+14）也是30，当然了此时hash&oldCap!=0。扩容之前，hash值为14和30的结点都在table[14]这个桶里，扩容之后，14依然留在了table[14]，而30分到了table[30]。用二进制表示更能够看清楚这个过程，大家可以用下边的表进行一下位与操作：
但如果table还没有初始化，就会进行初始化。进行初始化之后，就不会进行扩容的操作了，而且因为oldtable=null，所以也不会进行新旧table的内容复制。
提问时间
问：put过程中的resize方法在调用transfer方法的时候导致的死锁怎么不讲讲啊？偷懒哈！ 答：请你打开JDK1.8HashMap源码看一下，如果能找到transfer方法算我输。1.8中resize方法并不会产生死锁，但多线程下使用会产生数据丢失等问题。比如线程A和线程B同时进行resize，线程A先完成之后进行了数据的插入，此时线程B的resize才刚刚返回，这种情况线程A进行的数据更新就会丢失。
完整注释源码文档请公众号（Vegout）回复JDK1.8HashMap获取