【Java】HashMap线程不安全

image description

【Java】HashMap线程不安全

前言 大家都知道HashMap不安全,HashTable是安全的,HashTable安全是因为加了synchronized锁,那今天来看下HashMap为何不安全

jdk1.7中的HashMap 看源码

/**
 * Transfers all entries from current table to newTable. 
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {

        while(null != e) {
            //(关键代码)
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        } // while  

    }
}

解释一下上面一段代码

1、当前Entry的个数大于负载因子*table的容量时,会对table进行扩容

2、在对table进行扩容到newTable后,需要将原来数据转移到newTable中,注意10-12行代码,这里可以看出在转移元素的过程中,使用的是头插法,也就是链表的顺序会翻转,这里也是形成死循环的关键点

假设一开始这样 假设这里的定址就是key % 数组容量取余,3,7,5对2取余都是1 

这时候需要扩容,假设线程A和线程B同时扩容

线程 A在下面的代码的第某行挂起(已标注)

/**
 * Transfers all entries from current table to newTable. 
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {

        while(null != e) {
            //(关键代码)
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;// 线程A挂起
            e = next;
        } // while  

    }
}

此时的e就是3,next是7,3的next指向newTable[3],当前newTable[3]是null ,相当于3和7断开 此时线程B顺利的完成扩容

还是简单取余,7,3对4取余都是3,5对4取余是1

这里要注意 由于线程B已经执行完毕,根据Java内存模型,现在newTable和table中的Entry都是主存中最新值:7.next=3,3.next=null

此时切换回线程A

e=3,next=7,newTable[3]=null

继续执行

newTable[i] = e; // newTable[3] = 3
e = next;    // e = 7

继续循环,此时7对4取余还是3,但是现在newTable[3]有值了,是3,很快又被新的e覆盖了,这就是传说中的头插法

e=7
next=e.next ----> next=3【从主存中取值】
e.next=newTable[3] ----> e.next=3【从主存中取值】
newTable[3]=e ----> newTable[3]=7
e=next ----> e=3

再次进行循环 

e=3
next=e.next ----> next=null
e.next=newTable[3] ----> e.next=7 即:3.next=7
newTable[3]=e ----> newTable[3]=3
e=next ----> e=null

可能很容易绕晕,记住一点e就是当前的entry,也就是键值对

为啥会出现这种情况?

因为原来正常扩容的时候,按照3->7->5的顺序,7.next = 5,而由于多线程的存在,这种顺序被打乱了,7.next = 3(线程B的干涉下),就导致了死循环

还有一种情况是扩容导致的数据丢失

假设初始时 线程A如下图所示代码处挂起

/**
 * Transfers all entries from current table to newTable. 
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {

        while(null != e) {
            //(关键代码)
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e; //线程A挂起
            e = next;
        } // while  

    }
}

此时线程A运行结果如下

e.next = newTable[i]; // 7.next = newTable[3]

此时线程B完成扩容操作 此时内存中记录的5.next = null,而原来正常操作下5.next = 3

此时切换到线程A,在线程A挂起时:e=7,next=5,newTable[3]=null。

执行newtable[i]=e,就将7放在了newtable[3]的位置,此时next=5。接着进行下一次循环:

e=5
next=e.next ----> next=null,从主存中取值
e.next=newTable[1] ----> e.next=5,从主存中取值
newTable[1]=e ----> newTable[1]=5
e=next ----> e=null
将5放置在table[1]位置,此时e=null循环结束,3元素丢失,并形成环形链表。并在后续操作hashmap时造成死循环。

jdk1.8中HashMap 在jdk1.8中对HashMap进行了优化,在发生hash碰撞,不再采用头插法方式,而是直接插入链表尾部,因此不会出现环形链表的情况,但是在多线程的情况下仍然不安全,这里我们看jdk1.8中HashMap的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;
        if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
            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))))
                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
                            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;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

这是jdk1.8中HashMap中put操作的主函数, 注意第6行代码,如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作,刚好这两条不同的数据hash值一样,并且该位置数据为null,所以这线程A、B都会进入第6行代码中。

假设一种情况,线程A进入后还未进行数据插入时挂起,而线程B正常执行,从而正常插入数据,然后线程A获取CPU时间片,此时线程A不用再进行hash判断了,问题出现:线程A会把线程B插入的数据给覆盖,发生线程不安全。

总结 首先HashMap是线程不安全的,其主要体现:

在jdk1.7中,在多线程环境下,扩容时会造成环形链或数据丢失。 在jdk1.8中,在多线程环境下,会发生数据覆盖的情况。

    ArithmeticJia         0         50084         Java         502    

David Ramon

ArithmeticJia

www.guanacossj.com

Life is Short,You need Python

Related Posts

You may like these post too

image description

Leetcode【231】Power

##写在最前面: Given an integer, write a function to determine if it is a power of two. Example 1: Input: 1 Output: true Explanation: 20 = 1 Ex

image description

leetcode【53】最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 来源:力扣(LeetCode)

Comments on this post

0 comments

Leave a comment

it’s easy to post a comment

image description
image description
image description
image description
image description
image description
image description
image description
image description

Copyright © 2019.Company name All rights reserved.苏ICP备19007197号