精华内容
下载资源
问答
  • 1.TreeSet,基于TreeMap线程不安全的红黑树数据结构。在线程不安全访问时,有可能出现死循环。 ... android p里面RunningTasks.java...

    1.TreeSet,基于TreeMap线程不安全的红黑树数据结构。在线程不安全访问时,有可能出现死循环。

    https://ivoanjo.me/blog/2018/07/21/writing-to-a-java-treemap-concurrently-can-lead-to-an-infinite-loop-during-reads/

    android p里面RunningTasks.java里面使用的TreeSet 就会有这种情况。

    可以用Collections的辅助api来加上同步保护,注意要在set interrate的时候还要加上同步。 

        /**
         * Returns a synchronized (thread-safe) sorted set backed by the specified
         * sorted set.  In order to guarantee serial access, it is critical that
         * <strong>all</strong> access to the backing sorted set is accomplished
         * through the returned sorted set (or its views).<p>
         *
         * It is imperative that the user manually synchronize on the returned
         * sorted set when iterating over it or any of its <tt>subSet</tt>,
         * <tt>headSet</tt>, or <tt>tailSet</tt> views.
         * <pre>
         *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
         *      ...
         *  synchronized (s) {
         *      Iterator i = s.iterator(); // Must be in the synchronized block
         *      while (i.hasNext())
         *          foo(i.next());
         *  }
         * </pre>
         * or:
         * <pre>
         *  SortedSet s = Collections.synchronizedSortedSet(new TreeSet());
         *  SortedSet s2 = s.headSet(foo);
         *      ...
         *  synchronized (s) {  // Note: s, not s2!!!
         *      Iterator i = s2.iterator(); // Must be in the synchronized block
         *      while (i.hasNext())
         *          foo(i.next());
         *  }
         * </pre>
         * Failure to follow this advice may result in non-deterministic behavior.
         *
         * <p>The returned sorted set will be serializable if the specified
         * sorted set is serializable.
         *
         * @param  <T> the class of the objects in the set
         * @param  s the sorted set to be "wrapped" in a synchronized sorted set.
         * @return a synchronized view of the specified sorted set.
         */
        public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s) {
            return new SynchronizedSortedSet<>(s);
        }

     2.ArrayList

    ArrayList考虑到线程安全的话可以直接换用Vector,或者也用Collections的api添加synchronized同步锁。

        /**
         * Returns a synchronized (thread-safe) list backed by the specified
         * list.  In order to guarantee serial access, it is critical that
         * <strong>all</strong> access to the backing list is accomplished
         * through the returned list.<p>
         *
         * It is imperative that the user manually synchronize on the returned
         * list when iterating over it:
         * <pre>
         *  List list = Collections.synchronizedList(new ArrayList());
         *      ...
         *  synchronized (list) {
         *      Iterator i = list.iterator(); // Must be in synchronized block
         *      while (i.hasNext())
         *          foo(i.next());
         *  }
         * </pre>
         * Failure to follow this advice may result in non-deterministic behavior.
         *
         * <p>The returned list will be serializable if the specified list is
         * serializable.
         *
         * @param  <T> the class of the objects in the list
         * @param  list the list to be "wrapped" in a synchronized list.
         * @return a synchronized view of the specified list.
         */
        public static <T> List<T> synchronizedList(List<T> list) {
            return (list instanceof RandomAccess ?
                    new SynchronizedRandomAccessList<>(list) :
                    new SynchronizedList<>(list));
        }

     

    展开全文
  • HashMap HashMap 是一个散列表,它存储的内容是键值对(key-...由于Hashtable是个古老的Map实现类(从Hashtable的命名规范就可以看出,t没有大写,并不是我写错了),需要方法比较繁琐,符合Map接口的规范。但是H...

    HashMap

    HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。
    既然要介绍HashMap,那么就顺带介绍HashTable,两者进行比对。HashMap和Hashtable都是Map接口的经典实现类。由于Hashtable是个古老的Map实现类(从Hashtable的命名规范就可以看出,t没有大写,并不是我写错了),需要方法比较繁琐,不符合Map接口的规范。但是Hashtable也具有HashMap不具有的优点。下面我们进行两者之间的比对。

     

    HashMap与Hashtable的区别

    1.Hashtable是一个线程安全的Map实现,但HashMap是线程不安全的实现,所以HashMap比Hashtable的性能好一些;但如果有多个线程访问同一个Map对象时,使用Hashtable实现类会更好。

    2.Hashtable不允许使用null作为key和value,如果试图把null值放进Hashtable中,将会引发NullPointerException异常;但是HashMap可以使用null作为key或value。

     

    排序方式:

    HashMap  LinkedHashmap不支持重新排序,  hashmap 元素无序,linkedHashMap 元素按照插入顺序排序,

     如果需要元素有序该使用 TreeMap,参考treeset 的排序方式。

    HashMap判断key与value相等的标准

    前面文章中,我们针对其他集合都分析了判断集合元素相等的标准。针对HashMap也不例外,不同的是有两个元素:key与value需要分别介绍判断相等的标准。

    key判断相等的标准

    类似于HashSet,HashMap与Hashtable判断两个key相等的标准是:两个key通过equals()方法比较返回true,两个key的hashCode值也相等,则认为两个key是相等的。

    注意:用作key的对象必须实现了hashCode()方法和equals()方法。并且最好两者返回的结果一致,即如果equals()返回true,hashCode()值相等。

    value判断相等的标准

    HashMap与Hashtable判断两个value相等的标准是:只要两个对象通过equals()方法比较返回true即可。

    注意:HashMap中key所组成的集合元素不能重复,value所组成的集合元素可以重复。

    下面程序示范了HashMap判断key与value相等的标准。

    public class A {
        public int count;
    
        public A(int count) {
            this.count = count;
        }
        //根据count值来计算hashCode值
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + count;
            return result;
        }
        //根据count值来判断两个对象是否相等
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            A other = (A) obj;
            if (count != other.count)
                return false;
            return true;
        }
        
    
    }
    
    public class B {
        public int count;
        public B(int count) {
            this.count = count;
        }
         //根据count值来判断两个对象是否相等
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            B other = (B) obj;
            if (count != other.count)
                return false;
            return true;
        }
    
    }
    
    public class HashMapTest {
        public static void main(String[] args){
            HashMap map = new HashMap();
            map.put(new A(1000), "集合Set");
            map.put(new A(2000), "集合List");
            map.put(new A(3000), new B(1000));
           //仅仅equals()比较为true,但认为是相同的value
            boolean isContainValue = map.containsValue(new B(1000));
            System.out.println(isContainValue);
          //虽然是不同的对象,但是equals()和hashCode()返回结果都相等
            boolean isContainKey = map.containsKey(new A(1000));
            System.out.println(isContainKey);
          //equals()和hashCode()返回结果不满足key相等的条件
            System.out.println(map.containsKey(new A(4000)));
        }
        
    }
    

    输出结果:

    true
    true
    false

    注意:如果是加入HashMap的key是个可变对象,在加入到集合后又修改key的成员变量的值,可能导致hashCode()值以及equal()的比较结果发生变化,无法访问到该key。一般情况下不要修改。

     

    LinkedHashMap实现类

    HashSet有一个LinkedHashSet子类,HashMap也有一个LinkedHashMap子类;LinkedHashMap使用双向链表来维护key-value对的次序。
    LinkedHashMap需要维护元素的插入顺序,因此性能略低于HashMap的性能;但是因为它以链表来维护内部顺序,所以在迭代访问Map里的全部元素时有较好的性能。迭代输出LinkedHashMap的元素时,将会按照添加key-value对的顺序输出。
    本质上来讲,LinkedHashMap=散列表+循环双向链表

    TreeMap

    TreeMap是SortedMap接口的实现类。TreeMap 是一个有序的key-value集合,它是通过红黑树实现的,每个key-value对即作为红黑树的一个节点。

    TreeMap排序方式

    TreeMap有两种排序方式,和TreeSet一样。

    自然排序:TreeMap的所有key必须实现Comparable接口,而且所有的key应该是同一个类的对象,否则会抛出ClassCastException异常。

    定制排序:创建TreeMap时,传入一个Comparator对象,该对象负责对TreeMap中的所有key进行排序。

    TreeMap中判断两个元素key、value相等的标准

    类似于TreeSet中判断两个元素相等的标准,TreeMap中判断两个key相等的标准是:两个key通过compareTo()方法返回0,TreeMap即认为这两个key是相等的。

    TreeMap中判断两个value相等的标准是:两个value通过equals()方法比较返回true。

    注意:如果使用自定义类作为TreeMap的key,且想让TreeMap良好地工作,则重写该类的equals()方法和compareTo()方法时应保持一致的返回结果:两个key通过equals()方法比较返回true时,它们通过compareTo()方法比较应该返回0。如果两个方法的返回结果不一致,TreeMap与Map接口的规则就会冲突。

    除此之外,与TreeSet类似,TreeMap根据排序特性,也添加了一部分新的方法,与TreeSet中的一致。可以参考前面的文章。

     

    Map实现类的性能分析及适用场景

    HashMap与Hashtable实现机制几乎一样,但是HashMap比Hashtable性能更好些。
    LinkedHashMap比HashMap慢一点,因为它需要维护一个双向链表。
    TreeMap比HashMap与Hashtable慢(尤其在插入、删除key-value时更慢),因为TreeMap底层采用红黑树来管理键值对。
     

    适用场景:
    一般的应用场景,尽可能多考虑使用HashMap,因为其为快速查询设计的。
    如果需要特定的排序时,考虑使用TreeMap。
    如果仅仅需要插入的顺序时,考虑使用LinkedHashMap。

    展开全文
  • 为什么HashMap是线程不安全的 一、Map概述 我们都知道HashMap是线程不安全的,但是HashMap的使用频率在所有map中确实属于比较高的。因为它可以满足我们大多数的场景了。 Map类继承图 上面展示了java中Map的继承图,...

    为什么HashMap是线程不安全的

    一、Map概述
    我们都知道HashMap是线程不安全的,但是HashMap的使用频率在所有map中确实属于比较高的。因为它可以满足我们大多数的场景了。
    在这里插入图片描述

    Map类继承图
    上面展示了java中Map的继承图,Map是一个接口,我们常用的实现类有HashMap、LinkedHashMap、TreeMap,HashTable。HashMap根据key的hashCode值来保存value,需要注意的是,HashMap不保证遍历的顺序和插入的顺序是一致的。HashMap允许有一条记录的key为null,但是对值是否为null不做要求。HashTable类是线程安全的,它使用synchronize来做线程安全,全局只有一把锁,在线程竞争比较激烈的情况下hashtable的效率是比较低下的。因为当一个线程访问hashtable的同步方法时,其他线程再次尝试访问的时候,会进入阻塞或者轮询状态,比如当线程1使用put进行元素添加的时候,线程2不但不能使用put来添加元素,而且不能使用get获取元素。所以,竞争会越来越激烈。相比之下,ConcurrentHashMap使用了分段锁技术来提高了并发度,不在同一段的数据互相不影响,多个线程对多个不同的段的操作是不会相互影响的。每个段使用一把锁。所以在需要线程安全的业务场景下,推荐使用ConcurrentHashMap,而HashTable不建议在新的代码中使用,如果需要线程安全,则使用ConcurrentHashMap,否则使用HashMap就足够了。
    LinkedHashMap属于HashMap的子类,与HashMap的区别在于LinkedHashMap保存了记录插入的顺序。TreeMap实现了SortedMap接口,TreeMap有能力对插入的记录根据key排序,默认按照升序排序,也可以自定义比较强,在使用TreeMap的时候,key应当实现Comparable。

    二、HashMap的实现

    java7和java8在实现HashMap上有所区别,当然java8的效率要更好一些,主要是java8的HashMap在java7的基础上增加了红黑树这种数据结构,使得在桶里面查找数据的复杂度从O(n)降到O(logn),当然还有一些其他的优化,比如resize的优化等。
    介于java8的HashMap较为复杂,本文将基于java7的HashMap实现来说明,主要的实现部分还是一致的,java8的实现上主要是做了一些优化,内容还是没有变化的,依然是线程不安全的。
    HashMap的实现使用了一个数组,每个数组项里面有一个链表的方式来实现,因为HashMap使用key的hashCode来寻找存储位置,不同的key可能具有相同的hashCode,这时候就出现哈希冲突了,也叫做哈希碰撞,为了解决哈希冲突,有开放地址方法,以及链地址方法。HashMap的实现上选取了链地址方法,也就是将哈希值一样的entry保存在同一个数组项里面,可以把一个数组项当做一个桶,桶里面装的entry的key的hashCode是一样的。
    在这里插入图片描述
    HashMap的结构模型(java8)
    上面的图片展示了我们的描述,其中有一个非常重要的数据结构Node,这就是实际保存我们的key-value对的数据结构,下面是这个数据结构的主要内容:

    finalint hash;
    finalK key;
    V value;
    Node<K,V> next;
    

    一个Node就是一个链表节点,也就是我们插入的一条记录,明白了HashMap使用链地址方法来解决哈希冲突之后,我们就不难理解上面的数据结构,hash字段用来定位桶的索引位置,key和value就是我们的数据内容,需要注意的是,我们的key是final的,也就是不允许更改,这也好理解,因为HashMap使用key的hashCode来寻找桶的索引位置,一旦key被改变了,那么key的hashCode很可能就会改变了,所以随意改变key会使得我们丢失记录(无法找到记录)。next字段指向链表的下一个节点。
    HashMap的初始桶的数量为16,loadFact为0.75,当桶里面的数据记录超过阈值的时候,HashMap将会进行扩容则操作,每次都会变为原来大小的2倍,直到设定的最大值之后就无法再resize了。
    下面对HashMap的实现做简单的介绍,具体实现还得看代码,对于java8中的HashMap实现,还需要能理解红黑树这种数据结构。
    1、根据key的hashCode来决定应该将该记录放在哪个桶里面,无论是插入、查找还是删除,这都是第一步,计算桶的位置。因为HashMap的length总是2的n次幂,所以可以使用下面的方法来做模运算:

    h&(length-1)
    

    h是key的hashCode值,计算好hashCode之后,使用上面的方法来对桶的数量取模,将这个数据记录落到某一个桶里面。当然取模是java7中的做法,java8进行了优化,做得更加巧妙,因为我们的length总是2的n次幂,所以在一次resize之后,当前位置的记录要么保持当前位置不变,要么就向前移动length就可以了。所以java8中的HashMap的resize不需要重新计算hashCode。我们可以通过观察java7中的计算方法来抽象出算法,然后进行优化,具体的细节看代码就可以了。
    2、HashMap的put方法
    在这里插入图片描述
    HashMap的put方法处理逻辑(java8)
    上图展示了java8中put方法的处理逻辑,比java7多了红黑树部分,以及在一些细节上的优化,put逻辑和java7中是一致的。

    3、resize机制

    HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组,然后将原先的记录逐个重新映射到新的桶里面,然后将原先的桶逐个置为null使得引用失效。后面会讲到,HashMap之所以线程不安全,就是resize这里出的问题。

    三、为什么HashMap线程不安全

    上面说到,HashMap会进行resize操作,在resize操作的时候会造成线程不安全。下面将举两个可能出现线程不安全的地方。

    1、put的时候导致的多线程数据不一致。
    这个问题比较好想象,比如有两个线程A和B,首先A希望插入一个key-value对到HashMap中,首先计算记录所要落到的桶的索引坐标,然后获取到该桶里面的链表头结点,此时线程A的时间片用完了,而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面,假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的,那么当线程B成功插入之后,线程A再次被调度运行时,它依然持有过期的链表头但是它对此一无所知,以至于它认为它应该这样做,如此一来就覆盖了线程B插入的记录,这样线程B插入的记录就凭空消失了,造成了数据不一致的行为。

    2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环(cpu100%),具体分析如下:
    下面的代码是resize的核心内容:
    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;  
            } 
        }  
    }  
    

    这个方法的功能是将原来的记录重新计算在新桶的位置,然后迁移过去。
    多线程HashMap的resize

    我们假设有两个线程同时需要执行resize操作,我们原来的桶数量为2,记录数为3,需要resize桶到4,原来的记录分别为:[3,A],[7,B],[5,C],在原来的map里面,我们发现这三个entry都落到了第二个桶里面。
    假设线程thread1执行到了transfer方法的Entry next = e.next这一句,然后时间片用完了,此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作,需要注意的是,此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行,此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上,然后再处理[7,B],而[7,B]被链接到了[3,A]的后面,处理完[7,B]之后,就需要处理[7,B]的next了啊,而通过thread2的resize之后,[7,B]的next变为了[3,A],此时,[3,A]和[7,B]形成了环形链表,在get的时候,如果get的key的桶索引和[3,A]和[7,B]一样,那么就会陷入死循环。

    如果在取链表的时候从头开始取(现在是从尾部开始取)的话,则可以保证节点之间的顺序,那样就不存在这样的问题了。

    综合上面两点,可以说明HashMap是线程不安全的。

    展开全文
  • 介于java8的HashMap较为复杂,本文将基于java7的HashMap实现来说明,主要的实现部分还是一致的,java8的实现上主要是做了一些优化,内容还是没有变化的,依然是线程不安全的。 HashMap的实现使用了一个数组,每个...

    阅读:
    HashMap多线程操作下的问题总结
    https://blog.csdn.net/dongxurr123/article/details/77829038

    一、Map概述

    我们都知道HashMap是线程不安全的,但是HashMap的使用频率在所有map中确实属于比较高的。因为它可以满足我们大多数的场景了。


    Map类继承图

    上面展示了java中Map的继承图,Map是一个接口,我们常用的实现类有HashMap、LinkedHashMap、TreeMap,HashTable。HashMap根据key的hashCode值来保存value,需要注意的是,HashMap不保证遍历的顺序和插入的顺序是一致的。HashMap允许有一条记录的key为null,但是对值是否为null不做要求。HashTable类是线程安全的,它使用synchronize来做线程安全,全局只有一把锁,在线程竞争比较激烈的情况下hashtable的效率是比较低下的。因为当一个线程访问hashtable的同步方法时,其他线程再次尝试访问的时候,会进入阻塞或者轮询状态,比如当线程1使用put进行元素添加的时候,线程2不但不能使用put来添加元素,而且不能使用get获取元素。所以,竞争会越来越激烈。相比之下,ConcurrentHashMap使用了分段锁技术来提高了并发度,不在同一段的数据互相不影响,多个线程对多个不同的段的操作是不会相互影响的。每个段使用一把锁。所以在需要线程安全的业务场景下,推荐使用ConcurrentHashMap,而HashTable不建议在新的代码中使用,如果需要线程安全,则使用ConcurrentHashMap,否则使用HashMap就足够了。

    LinkedHashMap属于HashMap的子类,与HashMap的区别在于LinkedHashMap保存了记录插入的顺序。TreeMap实现了SortedMap接口,TreeMap有能力对插入的记录根据key排序,默认按照升序排序,也可以自定义比较强,在使用TreeMap的时候,key应当实现Comparable。

    二、HashMap的实现

    java7和java8在实现HashMap上有所区别,当然java8的效率要更好一些,主要是java8的HashMap在java7的基础上增加了红黑树这种数据结构,使得在桶里面查找数据的复杂度从O(n)降到O(logn),当然还有一些其他的优化,比如resize的优化等。
    介于java8的HashMap较为复杂,本文将基于java7的HashMap实现来说明,主要的实现部分还是一致的,java8的实现上主要是做了一些优化,内容还是没有变化的,依然是线程不安全的。
    HashMap的实现使用了一个数组,每个数组项里面有一个链表的方式来实现,因为HashMap使用key的hashCode来寻找存储位置,不同的key可能具有相同的hashCode,这时候就出现哈希冲突了,也叫做哈希碰撞,为了解决哈希冲突,有开放地址方法,以及链地址方法。HashMap的实现上选取了链地址方法,也就是将哈希值一样的entry保存在同一个数组项里面,可以把一个数组项当做一个桶,桶里面装的entry的key的hashCode是一样的。

    HashMap的结构模型(java8)

    上面的图片展示了我们的描述,其中有一个非常重要的数据结构Node<K,V>,这就是实际保存我们的key-value对的数据结构,下面是这个数据结构的主要内容:

            final int hash;    
            final K key;
            V value;
            Node<K,V> next;   
    

    一个Node就是一个链表节点,也就是我们插入的一条记录,明白了HashMap使用链地址方法来解决哈希冲突之后,我们就不难理解上面的数据结构,hash字段用来定位桶的索引位置,key和value就是我们的数据内容,需要注意的是,我们的key是final的,也就是不允许更改,这也好理解,因为HashMap使用key的hashCode来寻找桶的索引位置,一旦key被改变了,那么key的hashCode很可能就会改变了,所以随意改变key会使得我们丢失记录(无法找到记录)。next字段指向链表的下一个节点。

    HashMap的初始桶的数量为16,loadFact为0.75,当桶里面的数据记录超过阈值的时候,HashMap将会进行扩容则操作,每次都会变为原来大小的2倍,直到设定的最大值之后就无法再resize了。

    下面对HashMap的实现做简单的介绍,具体实现还得看代码,对于java8中的HashMap实现,还需要能理解红黑树这种数据结构。

    1、根据key的hashCode来决定应该将该记录放在哪个桶里面,无论是插入、查找还是删除,这都是第一步,计算桶的位置。因为HashMap的length总是2的n次幂,所以可以使用下面的方法来做模运算:

    h&(length-1)
    

    h是key的hashCode值,计算好hashCode之后,使用上面的方法来对桶的数量取模,将这个数据记录落到某一个桶里面。当然取模是java7中的做法,java8进行了优化,做得更加巧妙,因为我们的length总是2的n次幂,所以在一次resize之后,当前位置的记录要么保持当前位置不变,要么就向前移动length就可以了。所以java8中的HashMap的resize不需要重新计算hashCode。我们可以通过观察java7中的计算方法来抽象出算法,然后进行优化,具体的细节看代码就可以了。

    2、HashMap的put方法

    HashMap的put方法处理逻辑(java8)

    上图展示了java8中put方法的处理逻辑,比java7多了红黑树部分,以及在一些细节上的优化,put逻辑和java7中是一致的。

    3、resize机制

    HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组,然后将原先的记录逐个重新映射到新的桶里面,然后将原先的桶逐个置为null使得引用失效。后面会讲到,HashMap之所以线程不安全,就是resize这里出的问题。

    三、为什么HashMap线程不安全

    上面说到,HashMap会进行resize操作,在resize操作的时候会造成线程不安全。下面将举两个可能出现线程不安全的地方。

    1、put的时候导致的多线程数据不一致。
    这个问题比较好想象,比如有两个线程A和B,首先A希望插入一个key-value对到HashMap中,首先计算记录所要落到的桶的索引坐标,然后获取到该桶里面的链表头结点,此时线程A的时间片用完了,而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面,假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的,那么当线程B成功插入之后,线程A再次被调度运行时,它依然持有过期的链表头但是它对此一无所知,以至于它认为它应该这样做,如此一来就覆盖了线程B插入的记录,这样线程B插入的记录就凭空消失了,造成了数据不一致的行为。

    2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环(cpu100%),具体分析如下:

    下面的代码是resize的核心内容:

    void transfer(Entry[] newTable, boolean rehash) {  
            int newCapacity = newTable.length;  
            for (Entry<K,V> e : table) {  
    
            <span class="hljs-keyword">while</span>(<span class="hljs-keyword">null</span> != e) {  
                Entry&lt;K,V&gt; next = e.next;           
                <span class="hljs-keyword">if</span> (rehash) {  
                    e.hash = <span class="hljs-keyword">null</span> == e.key ? <span class="hljs-number">0</span> : hash(e.key);  
                }  
                <span class="hljs-keyword">int</span> i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } 
        }  
    }  
    

    这个方法的功能是将原来的记录重新计算在新桶的位置,然后迁移过去。

    多线程HashMap的resize

    我们假设有两个线程同时需要执行resize操作,我们原来的桶数量为2,记录数为3,需要resize桶到4,原来的记录分别为:[3,A],[7,B],[5,C],在原来的map里面,我们发现这三个entry都落到了第二个桶里面。
    假设线程thread1执行到了transfer方法的Entry next = e.next这一句,然后时间片用完了,此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作,需要注意的是,此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行,此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上,然后再处理[7,B],而[7,B]被链接到了[3,A]的后面,处理完[7,B]之后,就需要处理[7,B]的next了啊,而通过thread2的resize之后,[7,B]的next变为了[3,A],此时,[3,A]和[7,B]形成了环形链表,在get的时候,如果get的key的桶索引和[3,A]和[7,B]一样,那么就会陷入死循环。

    如果在取链表的时候从头开始取(现在是从尾部开始取)的话,则可以保证节点之间的顺序,那样就不存在这样的问题了。

    综合上面两点,可以说明HashMap是线程不安全的。

    展开全文
  • 1、线程安全 1.1 可变 1.2 绝对线程安全 1.3 相对线程安全 1.4 线程兼容 1.5 线程对立 1.6 线程安全的实现方法 1.6.1 互斥同步 线程执行互斥代码的过程 ① 实现互斥同步的方法--synchronized关键字 ...
  • HashMap中k的值没有顺序,常用来做统计。 LinkedHashMap吧。它内部有一个链表,保持Key插入的顺序。迭代的时候,也是按照插入...Hashtable与 HashMap类似,它继承自Dictionary类、不同的是:它允许记录的键或者...
  • 我们都知道HashMap是线程不安全的,但是HashMap的使用频率在所有map中确实属于比较高的。因为它可以满足我们大多数的场景了。 Map类继承图 上面展示了java中Map的继承图,Map是一个接口,我们常用的实现类有HashMap...
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    本人从事Java开发已多年,平时有记录问题解决方案和总结知识点的习惯,整理了一些有关Java的知识体系,这不是最终版,会定期的更新。也算是记录自己在从事编程工作的成长足迹,通过博客可以促进博主与阅读者的共同...
  • HashMap为什么存在线程不安全呢?

    千次阅读 2020-05-15 22:30:51
    关注Java后端技术栈“回复“面试”获取最新资料本文主要探讨下HashMap 在多线程环境下容易出现哪些问题,深层次理解其中的HashMap。我们都知道HashMap是线程不安全的,但是...
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    本套Java面试题大全,全的能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java Development Kit 的简称,java 开发工具包,提供了 java 的开发环境和运行环境。 JRE:Java Runtime Environ...
  • 线程安全代表集合会在多线程场景下使用。 假设使用map.get(key1)时返回为null。 会有两种可能:1.key1存在,所以返回为null; 2.key1对应的值为null。 对于单线程的HashMap,可以通过contains(key1)来检查是哪种...
  • HashMap在并发场景中不是线程安全的。比如A希望插入一个key-value对到HashMap中,当获取到对应的链表结点位置时,此时线程A的时间片用完了,而此时线程B被调度得以执行,可能线程B占用了A计算得到的位置,插入了数值...
  • 这里写自定义目录标题HashMap为什么线程不安全新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左...
  • 1. HashMap中k的值没有顺序,常用来做统计。 2.LinkedHashMap吧。它内部有一个链表,保持Key插入的顺序。迭代的时候,也是按照插入顺序...4.Hashtable与 HashMap类似,它继承自Dictionary类、不同的是:它允许记...
  • 1. HashMap中k的值没有顺序,常用来做统计。 2.LinkedHashMap吧。它内部有一个链表,保持Key插入的顺序。迭代的时候,也是按照插入顺序...4.Hashtable与 HashMap类似,它继承自Dictionary类、不同的是:它允许记...
  • 2020最新Java常见面试题及答案

    万次阅读 多人点赞 2019-10-26 15:53:35
    面试题包括以下十九个模块:Java 基础、容器、多线程、反射、对象拷贝、Java Web 模块、异常、网络、设计模式、Spring/Spring MVC、Spring Boot/Spring Cloud、Hibernate、Mybatis、RabbitMQ、Kafka、Zookeeper、...
  • HashMap为什么在多线程操作下不安全 一、Map概述 我们都知道HashMap是线程不安全的,但是HashMap的使用频率在所有map中确实属于比较高的。因为它可以满足我们大多数的场景了。 Map类继承图 上面展示了java中Map的...
  • 文章目录线程安全策略线程安全策略种类可变对象线程封闭同步容器并发容器CopyOnWriteArrayListCopyOnWriteArraysetConcurrentSkipListSetConcurrentHashMapConcurrentSkipListMap安全发布对象 线程安全策略 线程...
  • HashMap和LinkedHashMap的区别 LinkedHashMap是继承于HashMap,是基于HashMap和双向链表来实现的。 HashMap无序;LinkedHashMap有序,可分为插入顺序和访问顺序两种。...LinkedHashMap是线程不安全的。 使用
  • 的Key值实现散列hashCode(),分布是散列的、均匀的,支持排序;数据结构主要是桶(数组),链表或红黑树。适用于在Map中插入、删除和定位元素。 拓展 1、HashMap 和 TreeMap 的实现 HashMap: 基
  • 什么是线程安全的数据结构? 简单的说就是不同线程可以访问同一份数据时,它们对这份数据的访问是无序、随机的,是可控的。比如说你的房间谁都可以进来,但是你确定他们谁先来谁后来或者可能同时来。你想让整件...
  • Java集合面试题

    万次阅读 多人点赞 2019-06-25 14:46:19
    Java 平台提供这个接口任何直接的实现。 Set ,是一个能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。 List ,是一个有序集合,可以包含重复元素。你可以通过它的索引来...
  • TreeMap

    2020-08-24 21:05:58
    TreeMap 是 SortedMap 的子类,所以它具有排序功能。
  • ArrayList与LinkedList的区别和适用场景 Arraylist: 优点:ArrayList是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。 缺点:因为地址连续,...
  • 一、可变对象 可变对象需要满足的条件 (1)对象创建以后其状态就能修改 (2)对象所有域都是final类型 (3)对象是正确创建的(在对象创建期间,this引用没有溢出) 对于可变对象,可以参见JDK中的String...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,318
精华内容 6,527
关键字:

treemap线程不安全的场景