并发编程与线程安全（6）：线程池 Executor&并发拓展

[TOC]

第9章 线程池

new Thread的弊端

• 每次new Thread 新建对象，性能差
• 线程缺乏统一管理，可能无限制的新建线程，相互竞争，可能占用过多的系统资源导致死机或者OOM（out of memory 内存溢出），这种问题的原因不是因为单纯的new一个Thread，而是可能因为程序的bug或者设计上的缺陷导致不断new Thread造成的。
• 缺少更多功能，如更多执行、定期执行、线程中断。

线程池的好处

• 重用存在的线程，减少对象创建、消亡的开销，性能好
• 可有效控制最大并发线程数，提高系统资源利用率，同时可以避免过多资源竞争，避免阻塞。
• 提供定时执行、定期执行、单线程、并发数控制等功能。

ThreadPoolExecutor

参数说明：

ThreadPoolExecutor一共有七个参数，这七个参数配合起来，构成了线程池强大的功能。

• corePoolSize：核心线程数量
• maximumPoolSize：线程最大线程数
• workQueue：阻塞队列，存储等待执行的任务，很重要，会对线程池运行过程产生重大影响

corePoolSize、maximumPoolSize、workQueue 三者关系：如果运行的线程数小于corePoolSize的时候，直接创建新线程来处理任务。即使线程池中的其他线程是空闲的。如果运行中的线程数大于corePoolSize且小于maximumPoolSize时，那么只有当workQueue满的时候才创建新的线程去处理任务(不满时进入workQueue队列)。如果corePoolSize与maximumPoolSize是相同的，那么创建的线程池大小是固定的。这时有新任务提交，当workQueue未满时，就把请求放入workQueue中。等待空线程从workQueue取出任务。如果workQueue此时也满了，那么就使用另外的拒绝策略参数去执行拒绝策略。

workQueue：

当我们提交一个新的任务到线程池，线程池会根据当前池中正在运行的线程数量来决定该任务的处理方式。workQueue处理方式有三种：

1. 直接切换（SynchronusQueue）
2. 无界队列（LinkedBlockingQueue）能够创建的最大线程数为corePoolSize,这时maximumPoolSize就不会起作用了。当线程池中所有的核心线程都是运行状态的时候，新的任务提交就会放入等待队列中。
3. 有界队列（ArrayBlockingQueue）最大maximumPoolSize，能够降低资源消耗，但是这种方式使得线程池对线程调度变的更困难。因为线程池与队列容量都是有限的。所以想让线程池的吞吐率和处理任务达到一个合理的范围，又想使我们的线程调度相对简单，并且还尽可能降低资源的消耗，我们就需要合理的限制这两个数量

分配技巧： [如果想降低资源的消耗包括降低cpu使用率、操作系统资源的消耗、上下文切换的开销等等，可以设置一个较大的队列容量和较小的线程池容量，这样会降低线程池的吞吐量。如果我们提交的任务经常发生阻塞，我们可以调整maximumPoolSize。如果我们的队列容量较小，我们需要把线程池大小设置的大一些，这样cpu的使用率相对来说会高一些。但是如果线程池的容量设置的过大，提高任务的数量过多的时候，并发量

会增加，那么线程之间的调度就是一个需要考虑的问题。这样反而可能会降低处理任务的吞吐量。]

• keepAliveTime：线程没有任务执行时最多保持多久时间终止（当线程中的线程数量大于corePoolSize的时候，如果这时没有新的任务提交核心线程外的线程不会立即销毁，而是等待，直到超过keepAliveTime）

• unit：keepAliveTime的时间单位

• threadFactory：线程工厂，用来创建线程，有一个默认的工场来创建线程，这样新创建出来的线程有相同的优先级，是非守护线程、设置好了名称）

• rejectHandler：当拒绝处理任务时(阻塞队列满)的策略（AbortPolicy默认策略直接抛出异常、CallerRunsPolicy用调用者所在的线程执行任务、DiscardOldestPolicy丢弃队列中最靠前的任务并执行当前任务、DiscardPolicy直接丢弃当前任务）

  

初始化方法：


线程池生命周期：


• running：能接受新提交的任务，也能处理阻塞队列中的任务
• shutdown：不能处理新的任务，但是能继续处理阻塞队列中任务
• stop：不能接收新的任务，也不处理队列中的任务(把当前任务做完)
• tidying：如果所有的任务都已经终止了，这时有效线程数为0
• terminated：最终状态

其他方法：

序号	方法名	描述
1	execute()	提交任务，交给线程池执行
2	submit()	提交任务，能够返回执行结果 execute+Future
3	shutdown()	关闭线程池，等待任务都执行完
4	shutdownNow()	关闭线程池，不等待任务执行完
5	getTaskCount()	线程池已执行和未执行的任务总数
6	getCompleteTaskCount()	已完成的任务数量
7	getPoolSize()	线程池当前的线程数量
8	getActiveCount()	当前线程池中正在执行任务的线程数量

线程池类图


在线程池的类图中，我们最常使用的是最下边的Executors,用它来创建线程池使用线程。那么在上边的类图中，包含了一个Executor框架，它是一个根据一组执行策略的调用调度执行和控制异步任务的框架，目的是提供一种将任务提交与任务如何运行分离开的机制。它包含了三个executor接口：

• Executor:运行新任务的简单接口
• ExecutorService：扩展了Executor，添加了用来管理执行器生命周期和任务生命周期的方法
• ScheduleExcutorService：扩展了ExecutorService，支持Future和定期执行任务

使用Executor创建线程池

使用Executor可以创建四种线程池：

1、Executors.newCachedThreadPool

创建一个可缓存的线程池，如果线程池的长度超过了处理的需要，可以灵活回收空闲线程。如果没有可回收的就新建线程。

java

//源码：
public static ExecutorService newCachedThreadPool() {
    return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                  60L, TimeUnit.SECONDS,
                                  new SynchronousQueue<Runnable>());
}

值得注意的一点是，newCachedThreadPool的返回值是ExecutorService类型，该类型只包含基础的线程池方法，但却不包含线程监控相关方法，因此在使用返回值为ExecutorService的线程池类型创建新线程时要考虑到具体情况。


使用：

java

@Slf4j
public class ThreadPoolExample1 {
    
    public static void main(String[] args) {

        ExecutorService executorService = Executors.newCachedThreadPool();

        for (int i = 0; i < 10; i++) {
            final int index = i;
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    log.info("task:{}", index);
                }
            });
        }
        executorService.shutdown();
    }
}

2、newFixedThreadPool

定长线程池，可以线程现成的最大并发数，超出在队列等待

java

//源码：
public static ExecutorService newFixedThreadPool(int nThreads) {
    return new ThreadPoolExecutor(nThreads, nThreads,
                                  0L, TimeUnit.MILLISECONDS,
                                  new LinkedBlockingQueue<Runnable>());
}

使用

java

@Slf4j
public class ThreadPoolExample2 {

    public static void main(String[] args) {

        ExecutorService executorService = Executors.newFixedThreadPool(3);

        for (int i = 0; i < 10; i++) {
            final int index = i;
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    log.info("task:{}", index);
                }
            });
        }
        executorService.shutdown();
    }
}

3、newSingleThreadExecutor

• 单线程化的线程池，用唯一的一个共用线程执行任务，保证所有任务按指定顺序执行（FIFO、优先级…）

java

//源码
public static ExecutorService newSingleThreadExecutor() {
    return new FinalizableDelegatedExecutorService
        (new ThreadPoolExecutor(1, 1,
                                0L, TimeUnit.MILLISECONDS,
                                new LinkedBlockingQueue<Runnable>()));
}

使用：

java

@Slf4j
public class ThreadPoolExample3 {

    public static void main(String[] args) {

        ExecutorService executorService = Executors.newSingleThreadExecutor();
        
        //会按顺序执行
        for (int i = 0; i < 10; i++) {
            final int index = i;
            executorService.execute(new Runnable() {
                @Override
                public void run() {
                    log.info("task:{}", index);
                }
            });
        }
        executorService.shutdown();
    }
}

4、newScheduledThreadPool

定长线程池，支持定时和周期任务执行

java

//源码：
public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize) {
    return new ScheduledThreadPoolExecutor(corePoolSize);
}
public ScheduledThreadPoolExecutor(int corePoolSize) {
    super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,//此处super指的是ThreadPoolExecutor
          new DelayedWorkQueue());
}

使用：

java

@Slf4j
public class ThreadPoolExample4 {

    public static void main(String[] args) {

        ScheduledExecutorService executorService = Executors.newScheduledThreadPool(1);

          //-- 延迟3秒执行
//        executorService.schedule(new Runnable() {
//            @Override
//            public void run() {
//                log.warn("schedule run");
//            }
//        }, 3, TimeUnit.SECONDS);


        //-- 延迟1秒执行，每3秒执行一次
        executorService.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                log.warn("schedule run");
            }
        }, 1, 3, TimeUnit.SECONDS);
//        executorService.shutdown();


        //-- 延迟执行任务的操作，java中还有Timer类同样可以实现
        Timer timer = new Timer();
        timer.schedule(new TimerTask() {
            @Override
            public void run() {
                log.warn("timer run");
            }
        }, new Date(), 5 * 1000);
    }
}

第10章 并发拓展

10-1 死锁

什么是死锁？

通俗的说，死锁就是两个或者多个线程，相互占用对方需要的资源，而都不进行释放，导致彼此之间都相互等待对方释放资源，产生了无限制等待的现象。死锁一旦发生，如果没有外力介入，这种等待将永远存在，从而对程序产生严重影响。
用来描述死锁的问题最有名的场景就是“哲学家就餐问题”。哲学家就餐问题可以这样表述：假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事之一：吃饭或者思考。吃东西的时候他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为只用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐。哲学家从来不交谈，这就跟危险，可能产生死锁，每个哲学家都拿着左手的餐叉永远等右边的餐叉（或者相反）….

死锁产生的必要条件

• 互斥条件：进程对锁分配的资源进行排他性使用
• 请求和保持条件：线程已经保持了一个资源，但是又提出了其他请求，而该资源已被其他线程占用
• 不剥夺条件：在使用时不能被剥夺，只能自己用完释放
• 环路等待条件：资源调用是一个环形的链

死锁示例

java

/**
 * 一个简单的死锁类
 * 当DeadLock类的对象flag==1时（td1），先锁定o1,睡眠500毫秒
 * 而td1在睡眠的时候另一个flag==0的对象（td2）线程启动，先锁定o2,睡眠500毫秒
 * td1睡眠结束后需要锁定o2才能继续执行，而此时o2已被td2锁定；
 * td2睡眠结束后需要锁定o1才能继续执行，而此时o1已被td1锁定；
 * td1、td2相互等待，都需要得到对方锁定的资源才能继续执行，从而死锁。
 */

@Slf4j
public class DeadLock implements Runnable {
    public int flag = 1;
    //静态对象是类的所有对象共享的
    private static Object o1 = new Object(), o2 = new Object();

    @Override
    public void run() {
        log.info("flag:{}", flag);
        if (flag == 1) {
            synchronized (o1) {
                try {
                    Thread.sleep(500);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                synchronized (o2) {
                    log.info("1");
                }
            }
        }
        if (flag == 0) {
            synchronized (o2) {
                try {
                    Thread.sleep(500);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                synchronized (o1) {
                    log.info("0");
                }
            }
        }
    }

    public static void main(String[] args) {
        DeadLock td1 = new DeadLock();
        DeadLock td2 = new DeadLock();
        td1.flag = 1;
        td2.flag = 0;
        //td1,td2都处于可执行状态，但JVM线程调度先执行哪个线程是不确定的。
        //td2的run()可能在td1的run()之前运行
        new Thread(td1).start();
        new Thread(td2).start();
    }
}

10-2 并发最佳实践

1. 使用本地变量(方法内、局部变量)

   应该总是使用本地变量，而不是创建一个类或实例变量，通常情况下，开发人员使用对象实例作为变量可以节省内存并可以重用，因为他们认为每次在方法中创建本地变量会消耗很多内存。

   ​

2. 使用不可变类

   不可变类比如String Integer等一旦创建，不再改变，不可变类可以降低代码中需要的同步数量。

3. 最小化锁的作用域范围

   任何在锁中的代码将不能被并发执行，如果你有5%代码在锁中，那么根据Amdahl’s law，你的应用程序就不可能提高超过20倍，因为锁中这些代码只能顺序执行，降低锁的涵括范围，上锁和解锁之间的代码越少越好。

4. 使用线程池的Excutor，而不是直接new Thread执行

   创建一个线程的代价是昂贵的，如果你要得到一个可伸缩的Java应用，你需要使用线程池，使用线程池管理线程。JDK提供了各种ThreadPool线程池和Executor。

5. 宁可使用同步而不要使用线程的wait notify

   从Java 1.5以后增加了需要同步工具如CycicBariier, CountDownLatch 和 Sempahore，你应当优先使用这些同步工具，而不是去思考如何使用线程的wait和notify，通过BlockingQueue实现生产-消费的设计比使用线程的wait和notify要好得多，也可以使用CountDownLatch实现多个线程的等待。

6. 使用BlockingQueue实现生产-消费模式

   大部分并发问题都可以使用producer-consumer生产-消费设计实现，而BlockingQueue是最好的实现方式，堵塞的队列不只是可以处理单个生产单个消费，也可以处理多个生产和消费。

7. 使用并发集合Collection而不是加了同步锁的集合

   Java提供了 ConcurrentHashMap CopyOnWriteArrayList 和 CopyOnWriteArraySet以及BlockingQueue Deque and BlockingDeque五大并发集合，宁可使用这些集合，也不用使用Collections.synchronizedList之类加了同步锁的集合， CopyOnWriteArrayList 适合读多写少的场合，ConcurrentHashMap更是经常使用的并发集合

8. 使用Semaphore创建有界

   为了建立可靠的稳定的系统，对于数据库 文件系统和socket等资源必须有界bound，Semaphore是一个可以限制这些资源开销的选择，如果某个资源不可以，使用Semaphore可以最低代价堵塞线程等待

9. 宁可使用同步代码块，也不使用加同步的方法

   使用synchronized 同步代码块只会锁定一个对象，而不会将当前整个方法锁定；如果更改共同的变量或类的字段，首先选择原子性变量，然后使用volatile。如果你需要互斥锁，可以考虑使用ReentrantLock

10. 避免使用静态变量

    静态变量在并发执行环境会制造很多问题，如果你必须使用静态变量，让它称为final 常量，如果用来保存集合Collection，那么考虑使用只读集合。

10-3 Spring与线程安全

参考：https://www.cnblogs.com/xiangkejin/p/9276736.html

Spring对每个bean提供了一个scope属性来表示该bean的作用域。它是bean的生命周期。

• singleton：默认的scope，每个scope为singleton的bean都会被定义为一个单例对象，该对象的生命周期是与Spring IOC容器一致的（但在第一次被注入时才会创建）。
• prototype：bean被定义为在每次注入时都会创建一个新的对象。
• request：bean被定义为在每个HTTP请求中创建一个单例对象，也就是说在单个请求中都会复用这一个单例对象。
• session：bean被定义为在一个session的生命周期内创建一个单例对象。
• application：bean被定义为在ServletContext的生命周期中复用一个单例对象。
• websocket：bean被定义为在websocket的生命周期中复用一个单例对象。

无状态对象和有状态对象：

有状态就是有数据存储功能。有状态对象(Stateful Bean)，就是有实例变量的对象，可以保存数据，是非线程安全的。
无状态就是一次操作，不能保存数据。无状态对象(Stateless Bean)，就是没有实例变量的对象.不能保存数据，是不变类，不会因为多个线程的交替调度而破坏自身状态导致线程安全问题。

1. 无状态的Bean适合用单例模式，这样可以共享实例，提高性能。有状态的Bean，多线程环境下不安全，那么适合用Prototype原型模式。
2. 默认情况下，从Spring bean工厂所取得的实例为singleton（scope属性为singleton）,容器只存在一个共享的bean实例。
3. 那么scope选择的原则就很容易了：有状态的bean都使用prototype作用域，而对无状态的bean则应该使用singleton作用域。
4. 如Service层、Dao层用默认singleton就行
5. 有人可能会认为，我使用request作用域不就可以避免每个请求之间的安全问题了吗？这是完全错误的，因为Controller默认是单例的，一个HTTP请求是会被多个线程执行的，这就又回到了线程的安全问题。

解决方案：

1. 不要在bean中声明任何有状态的实例变量或类变量

2. 如果必须如此，那么就使用ThreadLocal把变量变为线程私有的

3. 如果bean的实例变量或类变量需要在多个线程之间共享，那么就只能使用synchronized、lock、CAS等这些实现线程同步的方法了

4. 在spring配置文件Controller中声明 scope=”prototype”，每次都创建新的controller( 不建议，这样开销很大)

   ​

10-4 HashMap与ConcurrentHashMap解析

参考：https://blog.csdn.net/u010853261/article/details/54312932

HashMap的线程不安全原因

原因一：死循环

原因在于HashMap在多线程情况下，执行resize()进行扩容时容易造成死循环。
扩容思路为：它要创建一个大小为原来两倍的数组，保证新的容量仍为2的N次方，从而保证上述寻址方式仍然适用。扩容后将原来的数组从新插入到新的数组中。这个过程称为reHash。

【单线程下的reHash】


• 扩容前：我们的HashMap初始容量为2，加载因子为1，需要向其中存入3个key，分别为5、9、11，放入第三个元素11的时候就涉及到了扩容。
• 第一步：先创建一个二倍大小的数组，接下来把原来数组中的元素reHash到新的数组中，5插入新的数组，没有问题。
• 第二步：将9插入到新的数组中，经过Hash计算，插入到5的后面。
• 第三步：将11经过Hash插入到index为3的数组节点中。

单线程reHash完全没有问题。

【多线程下的reHash】


假设有两个线程同时需要执行resize操作，此时线程1准备处理5，将下一个元素指向9，然后时间片用完了。而线程2被调度执行完了整个resize操作。


此时线程1重新被调度运行，thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[5,A]迁移到新的数组（自己扩容的数组）上。


然后将[9,B] (线程1在被抢cpu前的next指向)移到新的数组，而线程2处理时将9后面新增了5，因此线程1发现处理完9后，要继续处理9的next(也就是5)


于是5被挂在线程1的数组1下面，5后面连的9，又因为9后面连的5（线程2干的），所以死循环了。

原因二：fast-fail

使用迭代器（Iterator）的过程中，如果HashMap在“结构上”被修改了（增加元素导致扩容？），就会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。结构上的更改指的是删除或者插入一个元素，这样会影响到map的结构。

解决办法：可以使用Collections的synchronizedMap方法构造一个同步的map，或者直接使用线程安全的ConcurrentHashMap来保证不会出现fail-fast策略。

ConcurrentHashMap：红黑树？

---

Java7 HashMap

Hash表

Java中的数据存储方式有两种结构，一种是数组，另一种就是链表，前者的特点是连续空间，寻址迅速，但是在增删元素的时候会有较大幅度的移动，所以数组的特点是查询速度快，增删较慢。

而链表由于空间不连续，寻址困难，增删元素只需修改指针，所以链表的特点是查询速度慢、增删快。

那么有没有一种数据结构来综合一下数组和链表以便发挥他们各自的优势？答案就是哈希表。

HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。

Entry 包含四个属性：key, value, hash 值和用于单向链表的 next。

capacity : 当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。

loadFactor：负载因子，默认为 0.75。

threshold：扩容的阈值，等于 capacity * loadFactor

HashMap的长度为什么要是2的n次方？

为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同。参考：https://blog.csdn.net/sidihuo/article/details/78489820

put 过程分析

数组初始化：

在第一个元素插入 HashMap 的时候做一次数组的初始化，就是先确定初始的数组大小，并计算数组扩容的阈值。

1. 求 key 的 hash 值

   int hash = hash(key);

2. 找到对应的数组下标

   int i = indexFor(hash, table.length);

3. 放入链表头部

数组扩容

在插入新值的时候，如果当前的 size 已经达到了阈值，并且要插入的数组位置上已经有元素，那么就会触发扩容，扩容后，数组大小为原来的 2 倍。

get 过程分析

1. 根据 key 计算 hash 值。
2. 找到相应的数组下标：hash & (length – 1)。
3. 遍历该数组位置处的链表，直到找到相等(==或equals)的 key。

Java7 ConcurrentHashMap

——基于分段锁的ConcurrentHashMap


• Java7里面的ConcurrentHashMap的底层结构仍然是数组和链表，与HashMap不同的是ConcurrentHashMap的最外层不是一个大的数组，而是一个Segment数组。每个Segment包含一个与HashMap结构差不多的链表数组。
• 当我们读取某个Key的时候它先取出key的Hash值，并将Hash值的高sshift位与Segment的个数取模，决定key属于哪个Segment。接着像HashMap一样操作Segment。
• 为了保证不同的Hash值保存到不同的Segment中，ConcurrentHashMap对Hash值也做了专门的优化。
• Segment继承自J.U.C里的ReetrantLock，所以可以很方便的对Segment进行上锁。即分段锁。理论上最大并发数是和segment的个数是想等的。

初始化

• initialCapacity：初始容量，这个值指的是整个 ConcurrentHashMap 的初始容量，实际操作的时候需要平均分给每个 Segment。
• loadFactor：负载因子，之前我们说了，Segment 数组不可以扩容，所以这个负载因子是给每个 Segment 内部使用的。扩容是 segment 数组某个位置内部的数组 HashEntry<k,v>[] 进行扩容，扩容后，容量为原来的 2 倍。

put 过程分析

1. 计算 key 的 hash 值
2. 根据 hash 值找到 Segment 数组中的位置
3. 再利用 hash 值，求应该放置的segment 内部的数组下标
4. 添加到头部

get 过程分析

1. 计算 hash 值，找到 segment 数组中的具体位置，或我们前面用的“槽”
2. 槽中也是一个数组，根据 hash 找到数组中具体的位置
3. 到这里是链表了，顺着链表进行查找即可

Java8 HashMap

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。

关于红黑树：红黑树的关键性质: 从根到叶子最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。红黑树它是复杂而高效的，其检索效率O(lg n)。参考自：https://blog.csdn.net/u010853261/article/details/54312932

• 根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。
• Java 8为进一步提高并发性，摒弃了分段锁的方案(同时刻并发数等于Segment数组大小)，而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N))）。
• java8也是通过计算key的hash值和数组长度值进行取模确定该key在数组中的索引。但是java8引入红黑树，即使hash冲突比较高，寻址效率也会是比较高的。

• Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。
• 我们根据数组元素中，第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树的。

get 过程分析

1. 计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)
2. 判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步
3. 判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步
4. 遍历链表，直到找到相等(==或equals)的 key

Java8 ConcurrentHashMap


同步方式

• 对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。
• 对于读操作，由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个Node实例（Java 7中每个元素是一个HashEntry），它的Key值和hash值都由final修饰，不可变更，无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰，可见性也有保障

对比

HashMap和ConcurrentHashMap对比：

• HashMap非线程安全、ConcurrentHashMap线程安全
• HashMap允许Key与Value为空，ConcurrentHashMap不允许
• HashMap不允许通过迭代器遍历的同时修改，ConcurrentHashMap允许。并且更新可见

HashMap和HashTable的对比：

（1）HashMap是非线程安全的，HashTable是线程安全的。

（2）HashMap的键和值都允许有null存在，而HashTable则都不行。

（3）因为线程安全、哈希效率的问题，HashMap效率比HashTable的要高。

HashTable和ConcurrentHashMap对比：

HashTable里使用的是synchronized关键字，这其实是对对象加锁，锁住的都是对象整体，当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。ConcurrentHashMap相对于HashTable的syn关键字锁的粒度更精细了一些（对大数组的元素加锁？），并发性能更好。

10-5 多线程并发与线程安全总结


附1:J.U.C脑图