线程并发--并发容器

80 阅读 0 评论 53 点赞

我是靠谱客的博主震动铅笔，最近开发中收集的这篇文章主要介绍线程并发--并发容器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文作者：黄海燕，叩丁狼高级讲师。原创文章，转载请注明出处。

前言

现在面试问底层和基础问题越来越多了，我分析了一下，主要是现在各种框架出来，技术日新月异层出不穷，所以面试官就偏向于较为基础较为底层的问题，很多的框架其实都是通过基础的技术编写起来的，所以在这个技术膨胀的社会，我们应该以不变应万变。所以今天我们一起讨论以下这几个问题吧！

谈谈你理解的 HashMap，讲讲其中的 get put 过程。
容器不安全会导致哪些问题？
如何解决多线程中容器不安全问题？有没有线程安全的并发容器？
ConcurrentHashMap 是如何实现的？

HashMap原理

在jdk1.7中HashMap 底层是基于数组 + 链表组成的,jdk1.8之后稍微有点改变，因为当 Hash值冲突严重时，在同槽位上形成的链表会变的越来越长，这样在查询时的效率就会越来越低，为了提高查询速度，当同槽位上的链表个数到达一定的时候，链表会转换成为红黑树,为了适应这个变化元素也从Entry改成了Node了。

JDK1.7 中的数据结构图：

JDK1.8 中的数据结构图：

HashMap线程不安全问题

HashMap扩容操作resize方法导致出现环形链表问题

当HashMap执行添加元素操作的时候，如果已有元素的个数大于容量*0.75，HashMap集合就需要进行扩容操作。resize()代码如下：

我们可以看到resize方法是没有加锁的所以在多线程的情况下不安全，并且transfer方法容易出现环形链表问题，导致死循环的发生。transfer()代码如下：

环形链表表示如下：

由于上述的HashMap存在多线程不安全问题，所以我们在多线程的情况下只能通过以下两种方式：

使用Collections类中的synchronizedMap方法使HashMap容器安全
使用ConcurrentHashMap并发容器类
使用同步容器类Hashtable

什么是并发容器？

jdk1.5以后java.util.concurrent包中提供了多种并发类容器来替代同步容器类从而改善性能。同步类容器的状态都是串行化的。他们虽然实现了线程安全，但是严重降低了并发性，在多线程环境时，严重降低了应用的吞吐量。
并发类容器时专门针对并发设计的，使用了锁分段技术，只对操作的位置进行同步操作，但是其他没有操作的位置其他线程仍然可以访问，提高了程序的吞吐量。采用了CAS算法和部分代码使用synchronized锁保证线程安全。

并发容器的分类

ConcurrentHashMap：ConcurrentHashMap实现了HashTable的所有功能，线程安全，但却在检索元素时不需要锁定，因此效率更高。
ConcurrentLinkedQueue：ConcurrentLinkedQueue使用链表作为数据结构，它采用无锁操作，可以任务是高并发环境下性能最好的队列。
CopyOnWriteArrayList：CopyOnWriteArrayList提供高效地读取操作，使用在读多写少的场景。CopyOnWriteArrayList读取操作不用加锁，且是安全的；写操作时，先copy一份原有数据数组，再对复制数据进行写入操作，最后将复制数据替换原有数据，从而保证写操作不影响读操作。
ConcurrentSkipListMap：SkipList（跳表）是一种随机性的数据结构，用于替代红黑树，因为它在高并发的情况下，性能优于红黑树。

错误代码：

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<Integer,String> map = new HashMap<>();
        map.put(66, "B");
        map.put(67, "C");
        map.put(68, "D");
        new PrintThread(map).start();
        new AddThread(map).start();

    }
}

class PrintThread extends Thread{
    private HashMap<Integer,String> map = null;

    public PrintThread(HashMap<Integer,String> map) {
        this.map = map;
    }

    @Override
    public void run() {
        for (Entry<Integer, String> en : map.entrySet()) {
            System.out.println(Thread.currentThread().getName()+"-->"+en.getKey()+":"+en.getValue());
        }
    }
}

class AddThread extends Thread{
    private HashMap<Integer,String> map = null;

    public AddThread(HashMap<Integer,String> map) {
        this.map = map;
    }

    @Override
    public void run() {
        for (int i = 0; i < 50; i++) {
            map.put(i,"A");
        }
    }
}

错误截图：

ConcurrentModificationException：并发修改异常

该异常出现在迭代器遍历的时候，集合进行了添加或者删除操作导致的异常，具体是因为next()方法中含有checkForComodification方法，迭代器代码如下：

①迭代器调用next方法，next方法中调用checkForComodification方法检查modCount和expectedModCount字段是否相等
②modCount表示集合的操作次数，如果添加或者删除，modCount加1
③expectedModCount则是迭代器的操作数，在创建迭代器的时候会将集合的迭代数量赋值给expectedModCount，此时modCount和expectedModCount两个字段的数量是一致的
④当集合添加或者是删除的时候只会添加modCount，导致两个字段不相等，当下一次调用checkForComodification方法是就会出现ConcurrentModificationException并发修改异常

正确代码：

public class ConcurrentHashMapDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<Integer,String> map = new ConcurrentHashMap<>();
        map.put(66, "B");
        map.put(67, "C");
        map.put(68, "D");
        new AddThread1(map).start();
        new PrintThread1(map).start();

    }
}


class PrintThread1 extends Thread{
    private ConcurrentHashMap<Integer,String> map = null;

    public PrintThread1(ConcurrentHashMap<Integer,String> map) {
        this.map = map;
    }

    @Override
    public void run() {
        Set<Entry<Integer,String>> entrySet = map.entrySet();
        for ( Iterator<Entry<Integer,String>> it = entrySet.iterator();it.hasNext();) {
            System.out.println(it.next());
        }
    }
}

class AddThread1 extends Thread{
    private ConcurrentHashMap<Integer,String> map = null;

    public AddThread1(ConcurrentHashMap<Integer,String> map) {
        this.map = map;
    }

    @Override
    public void run() {
        for (int i = 0; i < 50; i++) {
            map.put(i,"65");
        }
    }
}