HashMap源码分析
2018-11-23 本文已影响0人
melodylzl
概述
本文源码针对Java8的HashMap。HashMap内部是由数组+链表或红黑树的结构实现的。HashMap默认初始化数组大小为16，负载因子是0.75,初始阀值12，每当数组元素的数量超过阀值后会扩容，每次扩容为旧空间大小的一倍，阀值也是增大一倍。
put()
put()先判断要放入的值是否会哈希冲突，如果不哈希冲突，则直接在hash到的位置插入。
如果发生冲突，判断是是链表还是红黑树，链表的话是直接插入到链尾，如果插入后链表长度大于8，会将链表转化为红黑树（哈希数组长度>=64）或者进行扩容;如果是红黑树，则按红黑树插入节点的规则来处理。
存放好值后，会判断哈希数组的大小是否超过阀值，超过的话进行扩容处理。
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;
if ((p = tab[i = (n - 1) & hash]) == null)
/** 若hash所在的位置为空，则创建新节点并插入到该位置 */
tab[i] = newNode(hash, key, value, null);
else {
/** 若hash所在的位置不为空，则处理冲突 */
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/** 如果原有节点的hash值和要插入的节点的hash值一致，先记录原有节点，
* 具体是覆盖还是不处理下面代码进行 */
e = p;
else if (p instanceof TreeNode)
/** 树结构节点的处理 */
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
/** 链表结构节点的处理 */
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
/** 如果插入后的链表长度大于8，则将链表转化为红黑树，也有可能是扩容哈希数组 */
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;
/** onlyIfAbsent为false时或oldValue为空时会覆盖旧值
* 意思如果onlyIfAbsend为true，但原来的oldValue为空时，oldValue还是会被覆盖为新值
* 就是只要oldValue为空，不管onlyIfAbsend的值如何，oldValue会被覆盖成新值*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
/** 如果size自增后大于阀值，进行扩容处理 */
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize()
扩容方法，每次扩容的大小都是前面大小的一倍。扩容后是需要重新hash确定每个元素的位置。
如果当前元素不是链表或红黑树，直接存放到新的hash位置；
如果是链表，则把链表拆分成低位链表和高位链表，低位链表还是在原来的位置，高位链表则存放到新位置上；
如果是红黑树，也需要拆分成低位和高位链表，不同的是会根据拆分后的链表长度是否小于等于6，则会将对应的树结构退化为链表。
/**调整存储空间大小 */
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
/**如果旧数组容量比最大容量（2^30）还大，则扩容阀值设为Integer.MAX_VALUE(2^31 - 1) */
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
/**直接返回旧数组 */
return oldTab;
}
/** 扩容一倍后的新容量小于最大容量且原来旧数组容量是大于初始容量(16)，则新阀值=旧阀值*2 */
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
/** 如果旧数组容量非正数，且旧阀值大于0，则新容量=旧阀值 */
newCap = oldThr;
else { // zero initial threshold signifies using defaults
/** 如果旧数组容量和旧阀值都为0，则新容量=16，新阀值=16*0.75=12; */
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
/**下面代码是创建新扩充容量长度的数组，并且把旧数组的值移动到新数组*/
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
/**如果当前节点没有下一个链表节点，则在新数组中重新hash找到对应的位置存放 */
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
/**如果当前节点是一颗红黑树的根节点，则按红黑树的规则存放进新数组 */
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
/**如果当前节点有下一个链表节点，是一个单向链表的头节点 */
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
/**这个循环是找出两个链表，满足(e.hash & oldCap) == 0这个条件的放到lo低位链表中，
* 不满足的，放到hi高位链表中，lo链表在新数组中的位置和旧数组一样，而hi链表在新数组中的位置
* = 旧数组中的位置j + 旧数组的容量oldcap */
do {
next = e.next;
/**这个条件的含义是若节点的哈希值和旧长度相与运算后还是0，说明该哈希值小于旧表的长度，则在新表中即使重新哈希，位置也是和旧表一样 */
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
get()
获取元素的流程相对简单，根据hash和key值查找数组，如果根据hash值找到的元素的key值不相等，则从当前元素所在的链表或者红黑树中去查找。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
/** 表不为空且长度大于0并且hash所在的位置不为空的情况下，才会继续判断下述情况 */
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);
/** 从链表中找 */
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Java8的HashMap相对于Java7的优化或区别
1、Java8的HashMap在链表长度大于或等于8时，会将链表转化为红黑树结构，提高了查询的效率；
2、Java8的HashMap存入元素发生冲突时，是将元素插入到链表，而Java7是插入到链头；同时在扩容时，Java7是把链表拆分成两个倒置，而Java8是将链表拆分成低位和高位链表，低位链表在旧位置，高位链表在新位置；这个处理避免了Java7在多线程中出现链表循环引用的情况；
3、Java8的哈希算法和Java7不一样。
HashMap是否线程安全
HashMap不是线程安全的，有线程安全的容器替代ConcurrentHashMap。ConcurrentHashMap是通过CAS+synchronized来实现线程同步的。
