J8中HashMap源码解析
在J8中，针对HashMap的源码进行了大量的修改，本文主要针对J8源码结构组成和两者在put方法中的操作及扩容进行源码解析
HashMap源码结构
hash值算法及其作用
通过hash值可以查询key值对应的数组下标值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashmap通过接受一个key值，计算出key值对应的hash值，hashCode()是一个native方法，用来在散列存储结构中根据对象的相关信息映射出的一个值，在hashmap中，通过tab[i = (n - 1) & hash]方式可以计算出数组下标的位置，其中(e.hash &; (oldCap-1)) 得到的是下标位置
hashmap节点类型
hashmap存储数据是由数组+链表+红黑树的结构构成，存储数据的结构是数组，数组的节点存放的则是node类型的基础节点，当链表当结构超过8个后，将会由链表结构转成红黑树结构
在hashmap的链表结构中，采用了node结构来对数据进行保存，Node由hash，value，key，next组成，构成了链表的基本结构在链表转为红黑树的过程中，node节点会被改造成treeNode，treeNode将会被放入到treeBin结构当中
hashmap在多线程情况下出现的问题
1-数据不同步问题
假设有两个线程a和b进行put操作，对于多线程执行任务，本质则是为每个线程分配时间片，当线程a计算了要插入元素的位置k，但是时间片用完，此时轮到线程b，线程b也可能会计算得到a线程要插入元素的位置k，这时候线程b将node插入位置k，结束执行，切换线程a执行插入操作，由于数组tab不是一个受到保护的变量，所以线程a将其node元素同样插入到位置k中，这时线程a的插入则会覆盖线程b的插入，造成数据的丢失
2-造成死循环问题
在java1.8以前，hashmap在进行put操作的扩容时，由于数据迁移问题，会形成一个环链，造成死循环
do {
Entry<K,V> next = e.next; // <--P1-假设线程A执行到这里就被调度挂起了
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
产生环链的原因就是上面的代码产生的，在老版的hashmap中，通过头插法的方式转移链表中的节点元素，假设有线程A和线程B并发的执行扩容操作
- 线程A执行到P1位置的时候被挂起
- 线程B顺利执行，这时候原数组数据转移到扩容后的新数组中,线程B执行完成，新数组取代老数组成为新的table
- 线程A继续执行，此时的next变量指向的是之前的node节点，这时候在后面的执行中，next指向的是之前数组table对应的节点，e仍然为之前老tab的值，在下面的执行代码e.next = newTable[i]可知，此时e.next指向的是线程B的数组，此处发生了误差，由于新的table数据是和之前反过来的，最终将会导致环链的产生
在java1.8的扩容操作中，当前数组中保存的数据位置不变的迁移到新的数法组中，不会造成环链的问题
hashmap源码解析
在hashmap中，我们使用最多的就是put操作，所有我们就关注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;
//步骤1:查看当前数组是否为空(长度是否为0)，如果判断条件为true，则对tab进行初始化
//n为数组长度赋值
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//步骤2:如果hash值在tab数组对应位置的节点为null，则初始化一个node放在对应的位置
//i = (n - 1) & hash可得出hash对应的数组下标
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//步骤3:数组该位置有数据
else {
Node<K,V> e; K k;
//步骤3-1:首先判断该位置的第一个数据是不是当前节点，通过比较key来进行判断，如果是则赋值给节点e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//步骤3-2:如果该节点是红黑树结构的节点，则通过红黑树的方式将该节点插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//步骤3-3:此处说明数据是链表结构
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，则进行值覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//此处的e代表的是已经存在相同key的老节点,由步骤3-1/2可知
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;//对e值进行覆盖
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果新插入的值超过了数组的阈(yu)值，则对数组进行扩容
//此处暴露线程不安全的问题
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
光看源码，感觉好多，实际在思路上就分为两部分
- 根据新传入的参数判断数组中是否已经存在该key，如果存在，则对value进行覆盖，如果没有则进行添加
- 对于新节点的添加，需要根据情况判断是加入到链表结构中还是树结构中
hashmap的扩容操作
当数组长度超过阈值或是进行
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) {
//如果原始数组的长度超过最大，则将阈值设为最大，并不在继续扩容了，并返回数
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果原始数组大于初始化大小且扩大一倍小于最大容量，则原始数组阈值扩大1倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//情景2-初始化行为，此时数组长度为0但是已设定阈值，在HashMap(int initialCapacit)进行put操作时触发
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//对应使用 new HashMap() 初始化后，第一次 put 的时候，设置默认的 阈值和数组长度
else {
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;
//根据newCap创建一个新的数组，如果是初始化数组，到这里就结束了
@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;
//情景1：如果该数组下标只有单个节点，则直接迁移该节点
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//情景2：此处是红黑树类型的迁移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 此处是处理链表的结构
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//链表赋值
do {
next = e.next;
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;
}
hashmap的扩容操作主要思路
- 首先进行数组阈值和容量的扩充
- 如果是扩容操作，则需要进行数据的迁移
对于数据迁移，就是对三种数据结构的转移
节点元素的迁移
链表元素的迁移
红黑树结构的迁移
在数据迁移的代码中，核心代码则是
(e.hash & oldCap)
这行代码的作用则是判断当前节点在数组中方的位置是否需要移动
新版hashmap数据的迁移则是通过对进制高位的判断来决定是否需要对数据进行迁移，需要迁移的则移动到新的结构中，不需要迁移的则维持当前的 位置不动
结论:元素位置在扩容后数组中的位置发生了改变,新的下标位置是原下标位置+原数组长度
链表赋值
对于扩容后的hashmap的数据转移赋值问题，分为两个部分来分析
- 首先是通过(e.hash & oldCap)==0的数据，这类数据则是在扩容后数据在数组中的位置不需要改变的数据，通过loHead,loTail用于保存扩容前链表的首尾节点，
在新创建的tab数组中，值保存首节点lohead节点 - 针对需要变换在数组中位置的元素节点，使用hihead，hitail来表示，原理同上
网友评论