put方法,JDK1.8
通过put方法查看HashMap内部结构 基本上都知道是数组+链表+红黑树
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以得出,在插入的时候先进行了一个hash算法,求key的hash值.该算法的意义是为了让一个key的hashcode的高位和低位进行运行,更好的打散
// 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对应的数组位置 这也是为什么hashMap如果要扩容是2^x 的原因,只有这样才能更好的散列,
// 如果不是2^x ,二进制必然有0的存在 0&n=0 该位置必然为0 造成了有的数组位置肯定是没有值的
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果此处数组位置不存在值,就创建新节点存入
tab[i] = newNode(hash, key, value, null);
else {
// 此处有值
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 同样的key 替换值
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( >=9) 会进行判断
1.如果map的数组长度少于64 那么就扩容
2.如果map的数组长度大于64那么将此链表转成红黑树
**/
treeifyBin(tab, hash);
break;
}
//在列表中找找对应的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)
// 当map中个数大于 数组总长度的3/4(可以代码设置)的时候,数组进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
JDK 7 中大家都知道hashMap在高并发情况下会发生死锁,原理如下:
/**
下面的代码块是jdk1.7中resize()的核心方法也是造成死锁的方法
*/
// 节点不为null rehash key值然后添加到新数组位置
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历老数组 然后将数字每个节点rehash后重新添加到新数组里面
for (Entry<K,V> e : table) {
while(null != e) {
// 临时节点存放 e的下一节点 ps:位置1
Entry<K,V> next = e.next;
// 进行rehash操作,算出坐标
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 通过新坐标找到新数组位置
int i = indexFor(e.hash, newCapacity);
// 采用头插法,插入到 新数组次该位置的链表(可能为null或者单节点)的头部
e.next = newTable[i];
// 然后将e节点替换新数组里面的此位置的节点
newTable[i] = e;
// 将上面存储的原本e的下一节点置为e 重复进行上述操作
e = next;
}
}
jdk7中采用的是头插入法,这样效率是很高,但是多线程下可能操作死锁,
假设 老数组里面有链表 key(4)->key(20),两个的rehash值也一样
线程A:线程A执行到位置1,被中断了,但是此时的 e = key(4)
线程B:线程B统一执行resize方法,没被中断迅速将 key(4)和key(20)转移到新数组的位置,假设位置为10
,此时newTable[10]应该是 key(20)->key(4)的结构.
然后线程A再次获取资源执行操作,造成的操作就是newTable[10]应该是 key(4)->key(20)->key(4),造成链表环,查找的时候造成思索
//接下来我们看1.8中如何解决这样的问题:
基础知识:
HashMap,查找位置采用的hash算法 (n - 1) & hash(n=tab.length,hash如上图hash算法获取的值)
hash值为24246,24486对应数组位置
加入老数组长度等于16
1111 --n-1=15
& 101111010110110 --hash = 24246
= 0110 --计算得到的位置6,和取模算法功能一样,效率要高很多
1111 --n-1=15
& 101111110100110 --hash = 24486
= 0110 --计算得到的位置6,和取模算法功能一样,效率要高很多
现在resize长度为16<1 = 32
11111 --n-1 =31
& 101111010110110 --hash = 24486
= 10110 --计算得到的位置22
11111 --n-1=31
& 101111110100110 --hash = 24486
= 0110 --计算得到的位置6
有上面可知,每次rehash 得到的值变化无异于hash高位多了1位,只存在两种情况,要不是1要不是0,统一位置的链表中的每个节点那么每次rehash
后的位置要不不变,要不就是在 newTab[j + oldCap](j=老数组的坐标,oldCap = 老数组的长度)
等同于下面算法hash & oldCap
10000 --oldCap=16
& 101111010110110 --hash = 24486
= 10000 --位置变化 新位置
10000 --oldCap=16
& 101111110100110 --hash = 24486
= 00000 --位置不变
{ // preserve order
// 位置不变的临时头节点
Node<K,V> loHead = null, loTail = null;
//位置在 newTab[j + oldCap]的临时头节点
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;
}
}
可以得知1.8中采用的两个临时节点,是整个一块移动替换,不存在上述形成链表环的问题
网友评论