文章目录

• • • 1、Cas（比较并交换）
    • 2、AQS（AbstractQueuedSynchronizer）=>抽象队列同步器
    • 3、Volatile：
    • • 3.1、JMM
      • 3.2、As-If-Serial原则
      • 3.3、Happens-Before原则
      • 3.4、volatile原理
      • 3.5、作用
      • 3.6、原子操作
      • 3.7、高速缓存
      • 3.8、MESI状态切换
      • 3.9、伪共享
    • 4、ReentrantLock
    • • 4.1、原理
    • 5、Synchronized
    • • 5.1、原理
      • 5.2、锁升级
      • 5.3、对象布局
    • 6、CountDownLatch=>倒计时器
    • • 6.1、使用
      • 6.2、常用api
      • 6.3、原理
    • 7、CyclicBarrier=>循环栅栏
    • • 7.1、原理
      • 7.2、常用API
      • 7.3、使用
      • 7.2、CountDownLatch和CyclicBarrier的区别
    • 8、Semaphore=>参数代表同时访问的线程,允许多个线程同时访问
    • • 8.1、定义
      • 8.2、使用
      • 8.3、主要API
    • 9、Executors(不建议使用)
    • 10、ThreadPoolExecutor
    • • 10.1、创建
      • 10.2、参数解析
      • 10.3、原理
    • 11、ScheduledThreadPoolExecutor：
    • 12、Exchanger(交换数据)
    • 13、ThreadLocal
    • • 13.1、原理
    • 14、BlockingQueue（生产者消费者模型=》队列（先进先出））
    • • 14.1、ArrayBlockingQueue
      • 14.2、LinkedBlockingQueue
      • 14.3、PriorityBlockingQueue
      • 14.4、DelayQueue
      • 14.5、常用API
    • 15、Automic类
    • • 15.1、相关术语
      • 15.2、常见类
    • 16、Unsafe
    • • 16.1、怎么获取实例
      • 16.2、功能介绍
      • • 16.2.1、内存操作
        • 16.2.2、CAS相关
        • 16.2.3、线程调度
        • 16.2.4、内存屏障
    • 17、Future/FutureTask
    • • 17.1、任务性质类型
      • 17.2、Future(接口)
      • • 17.2.1、定义
        • 17.2.2、常见方法
        • 17.2.3、功能
      • 17.3、FutureTask
    • 18、Fork/Join（大化小，小归大，分而治之）
    • • 18.1、Fork/Join定义
      • 18.2、Fork/Join特性
      • 18.3、工作窃取算法
      • • 18.3.1、定义
        • 18.3.2、例子
        • 18.3.3、Fork/Join中的体现
      • 18.4、ForkJoin的类
      • 18.5、使用场景例子
    • 19、Disruptor(生产者消费者模型)
    • • 19.1、核心设计原理(怎么解决队列速度慢)
      • 19.2、核心组件与作用（8个）
      • 19.3、等待策略（Wait Strategy）
      • 19.4、写数据
    • 20、Hashmap/ConcurrentHashMap
    • • 20.1、说一下 HashMap 的实现原理？
      • 20.2、HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现
      • 20.3、HashMap的put方法的具体流程？
      • 20.4、HashMap的get方法的具体流程？
      • 20.5、HashMap的扩容操作是怎么实现的？
      • 20.6、HashMap是怎么解决哈希冲突的？
      • 20.7、能否使用任何类作为 Map 的 key？
      • 20.8、为什么HashMap中String、Integer这样的包装类适合作为K？
      • 20.9、如果使用Object作为HashMap的Key，应该怎么办呢？
      • 20.10、HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？
      • 20.11、HashMap 的长度为什么是2的幂次方
      • 20.12、HashMap 与 HashTable 有什么区别？
      • 20.13、如何决定使用 HashMap 还是TreeMap？
      • 20.14、HashMap 和 ConcurrentHashMap 的区别
      • 20.15、ConcurrentHashMap 和 Hashtable 的区别？
      • 20.16、ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？
    • 21、ArrayList
    • • 21.1、快速失败机制 “Fail-Fast”
      • 21.2、安全失败 Fail-Safe
      • 21.3、Fail-Fast(快速失败)和Fail-Safe(安全失败)比较
      • 21.4、说一下 ArrayList 的优缺点
      • 21.5、如何实现数组和 List 之间的转换？
      • 21.6、ArrayList 和 LinkedList 的区别是什么？
      • 21.7、ArrayList 和 Vector 的区别是什么？
      • 21.8、插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？
      • 21.9、多线程场景下如何使用ArrayList？
    • 22、CopyOnWriteArrayList
    • 23、TreeMap
    • • 23.1、原理
      • 23.2、红黑树
      • • 23.2.1、性质
        • 23.2.2、插入的时候旋转和颜色变换规则
        • 23.2.3、删除
        • 23.2.4、红黑树的性能分析
    • 24、StampedLock
    • 25、wait()与sleep() 方法的区别。
    • 26、什么时候用线程，什么时候用进程，nginx底层的用到了什么？

1、Cas（比较并交换）

原理：简单来说就两步：每次更新之前先查询一下version，当更新的时候version还一样就可以执行更新，否则失败，

他是基于魔法类unsafe的compareAndSwapObject，compareAndSwapInt，compareAndSwapLong三组api实现的，特别的，unsafe可以申请堆外内存，比如在我们文件上传时，高并发场景下，就可以用unsafe去申请，但是也要记得去释放，不然会出现内存泄露

底层：他的硬件原语就是一个lock_cmpxchg

产生的问题：ABA问题（你的女友跟你分手后，找了好几任，后面再跟你一样，简称换汤不换药，）

解决：version字段（版本号机制），时间戳机制

2、AQS（AbstractQueuedSynchronizer）=>抽象队列同步器

原理：他有一个state变量，当有线程来时先去工作内存中寻找state，看state是否大于1，当大于1时说明当前有线程占有，此时该线程进入CLH同步队列中，当没有线程时，说明此时state状态为0，说明没线程占有锁，此时他要分两种情况：

• 此时是公平锁，他需要去CLH队列中进行把上次的head的next的节点，放到头结点上，并把data数据置为null，然后把state变量置为1，特别的，他有一个可重入的概念，他是当发现进来的线程与正在运行的线程一样时就把我们的state变量加为1，那么这个时候就有个问题了，假设我的state=10，那么我下次怎么把state变为0了，难道要经历10次的释放锁过程吗，不是的，他有一个waitestate这样一个状态，他head的下一个节点会观察他，当他释放了，他后一个节点就把前一个节点的waitestate置为0，这样去释放的！

• 此时是非公平锁，跟公平锁差不太多，它主要是有一个vip的概念，就是说，假设我当前已经释放了锁，并且state=0；那么此时我CLH队列的head的下一个节点就要去抢锁了，那么就会有一种情况，我clh的队列的节点去抢锁，但是我此时有一个线程刚好也来抢锁，那么他就会插队，那么会抢到吗，答案是会的，所以公平锁就是如果没有外来线程的话CLH优先，有的话则外来的优先！！

• 特别地：aqs头节点的数据永远为null

  AQS有什么用呢？

  aqs在我们大部分的锁里面底层都是他，它主要是unsafe里面的compareAndSwapObject，compareAndSwapLong，compareAndSwapInt三组Api配合我们的LockSupport.unpark和LockSupport.park去实现的。

  aqs里面有两种队列，一种叫做条件等待队列，一种叫做同步队列，他有什么作用呢，其实我们的blockingQueue生产消费者就是用它两来实现的，具体怎么实现等后面的blockingqueue我再说。

3、Volatile：

首先要了解Volatile需要先去了解JMM，as-if-serial,happens-before三个定义

3.1、JMM

jmm就是说当线程需要去用一个主内存中的变量时，需要把主内存中的变量拷贝到自己的工作内存中去修改，操作完之后再把工作内存中的变量放回去。

3.2、As-If-Serial原则

意思就是说不论你怎么重排序，程序的执行结果必须是不能改变的。

3.3、Happens-Before原则

主要由8大原则

1. 程序顺序原则，见名思意
2. 锁规则，一个加锁对应一个解锁，加锁必须在解锁后面
3. volatile规则，volatile的写先于读，保证可见性
4. 线程启动规则，start（）方法先于一切
5. 传递性，见名思意
6. 线程终止规则，线程的所有操作先于终结
7. 线程中断规则， interrupt()方法中断，Thread.interrupted()方法检查是否中断
8. 对象终结规则，起于构造，终于finalize()

3.4、volatile原理

当线程需要去用一个主内存中的变量时，需要把主内存中的变量拷贝到自己的工作内存中去修改，操作完之后再把工作内存中的变量放回去。但是如果当A线程去读取主内存的值是，B已经修改放入主内存中了，那么此时A修改失败，重新读取，进行修改

3.5、作用

1. 保证变量的可见性

• 主要是通过缓存一致性协议MESI+高速缓存+缓存行锁+总线锁+总线嗅探机制实现的

1. 不保证变量的原子性
2. 禁止指令重排

• 主要是通过内存屏障去实现的，他有四种屏障指令：
  • LoadLoad（读读先后）
  • 写
  • LoadStore（读写先后）
  • StoreStore（写写先后）
  • 读
  • StoreLoad（写读先后）
  • 再具体点就是当第二个是volatile写时，不管第一个是什么样的操作，都不
    能重排序
  • 当第一个操作是volatile读时，不管第二个操作是什么，都不
    能重排序
  • 当第一个操作是volatile写，第二个操作是volatile读时，不能
    重排序。

3.6、原子操作

当线程去读取主内存中的数据时，需要经历8个原子才做

1. lock给要使用的主内存的变量加锁

2. read读取变量

3. load把我的变量copy一份载入工作内存中

4. use把值传递给要使用的执行引擎

5. assign：把执行引擎修改后的值放入工作内存中

6. store：把工作内存的变量值传递给主内存

7. write写入给主内存

8. unlock解锁

3.7、高速缓存

高速缓存中的缓存行有几种？3种

• 速度：l1>l2>l3
• 大小：l3>l2>l1
• 读取按从大到小，也就是说假设线程要读取主内存中的数据，首先先去l3找，有则返回，无则去l2找，有则返回，无则去l1找，最后再去内存中

缓存行大小？

64字节

为什么要有高速缓存？

时间局部性和空间局部性，来解决读取问题

3.8、MESI状态切换

• M修改
• E独占
• S共享
• I无效

3.9、伪共享

多线程条件下，共享同一个缓存行的变量

怎么解决？

@Contendend，需要开启jvm启动时设置 -XX:-RestrictContended

4、ReentrantLock

4.1、原理

默认是非公平锁，要想变成公平锁，需要加个构造方法，参数为true，

1、公平锁：当线程（正常用户）过来时，会去CLH队列中排队，如果当前没有其他节点，只有他自己一个节点，则会加锁，state变为1，如果有其他节点，放入CLH队列中。

2、非公平锁：当线程（VIP）过来时，先尝试去获取锁，获取到直接加锁，不管CLH队列中有没有节点

具体的aqs操作，看aqs相关

5、Synchronized

5.1、原理

• synchronized关键字在使用层面的理解
  • 1、同步实例方法（修饰普通方法），锁当前对象引用
  • 2、同步类方法（static修饰的方法），锁当前类对象
  • 3、同步代码块（synchronized括号里面是对象的class），锁当前的括号里面的对象
• synchronized关键字在字节码中的体现
  • 1、同步实例方法（修饰普通方法），底层是一个ACC_SYNCHRONIZED修饰符
  • 2、同步类方法（static修饰的方法），底层是也是一个ACC_SYNCHRONIZED修饰符
  • 3、同步代码块（synchronized括号里面是对象的class），底层是由一个monitorenter进入和两个monitorexit，monitorexit第1次为同步正常退出释放锁；第2次为发生异步退出释放锁；
• synchronized关键字在JVM中的实现
  • 也就是monitor锁，他就是synchronized的对象锁，底层是由ObjectMonitor实现的，而ObjectMonitor的底层有两个队列：_WaitSet 和 _EntryList，用来保存ObjectWaiter对象列表（ 每个等待锁的线程都会被封装成ObjectWaiter对象 ），_owner指向持有ObjectMonitor对象的线程，当多个线程访问时：
    • 1、首先会进入_EntryList集合，当线程获取到对象的monitor后，进入_Owner区域，并把monitor中的owner变量设置为当前线程，同时把monitor中的计数器count+1；
    • 2、若线程调用wait方法，将释放当前持有的monitor后，owner变量恢复为null，count自减1，同时线程进入WaitSet集合中等待唤醒；
    • 3、若当前线程执行完毕，将释放monitor（锁）并复位count的值，以便其他线程进入获取monitor（锁），同时Monitor对象存在于每个Java对象的对象头Mark Word中（存储的指针的指向），Synchronized锁便是通过这种方式获取锁的
• synchronized关键字在硬件方面的实现
  • 其实底层就是一个lock标志

5.2、锁升级

1、偏向锁

偏向锁是Java 6之后加入的新锁，它是一种针对加锁操作的优化手段，经过研究发现，在大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，因此为了减少同一线程获取锁(会涉及到一些CAS操作,耗时)的代价而引入偏向锁。偏向锁的核心思想是，如果一个线程获得了锁，那么锁就进入偏向模式，此时Mark Word 的结构也变为偏向锁结构，当这个线程再次请求锁时，无需再做任何同步操作，即获取锁的过程，这样就省去了大量有关锁申请的操作，从而也就提供程序的性能。所以，对于没有锁竞争的场合，偏向锁有很好的优化效果，毕竟极有可能连续多次是同一个线程申请相同的锁。但是对于锁竞争比较激烈的场合，偏向锁就失效了，因为这样场合极有可能每次申请锁的线程都是不相同的，因此这种场合下不应该使用偏向锁，否则会得不偿失，需要注意的是，偏向锁失败后，并不会立即膨胀为重量级锁，而是先升级为轻量级锁。下面我们接着了解轻量级锁。
默认开启偏向锁
开启偏向锁：-XX:+UseBiasedLocking -XX:BiasedLockingStartupDelay=0
关闭偏向锁：-XX:-UseBiasedLocking

2、轻量级锁

倘若偏向锁失败，虚拟机并不会立即升级为重量级锁，它还会尝试使用一种称为轻量级锁的优化手段(1.6之后加入的)，此时Mark Word 的结构也变为轻量级锁的结构。轻量级锁能够提升程序性能的依据是“对绝大部分的锁，在整个同步周期内都不存在竞争”，注意这是经验数据。需要了解的是，轻量级锁所适应的场景是线程交替执行同步块的场合，如果存在同一时间访问同一锁的场合，就会导致轻量级锁膨胀为重量级锁。

3、自旋锁

轻量级锁失败后，虚拟机为了避免线程真实地在操作系统层面挂起，还会进行一项称为自旋锁的优化手段。这是基于在大多数情况下，线程持有锁的时间都不会太长，如果直接挂起操作系统层面的线程可能会得不偿失，毕竟操作系统实现线程之间的切换时需要从用户态转换到核心态，这个状态之间的转换需要相对比较长的时间，时间成本相对较高，因此自旋锁会假设在不久将来，当前的线程可以获得锁，因此虚拟机会让当前想要获取锁的线程做几个空循环(这也是称为自旋的原因)，一般不会太久，可能是50个循环或100循环，在经过若干次循环后，如果得到锁，就顺利进入临界区。如果还不能获得锁，那就会将线程在操作系统层面挂起，这就是自旋锁的优化方式，这种方式确实也是可以提升效率的。最后没办法也就只能升级为重量级锁了。

4、锁消除

消除锁是虚拟机另外一种锁的优化，这种优化更彻底，Java虚拟机在JIT编译时(可以简单理解为当某段代码即将第一次被执行时进行编译，又称即时编译)，通过对运行上下文的扫描，去除不可能存在共享资源竞争的锁，通过这种方式消除没有必要的锁，可以节省毫无意义的请求锁时间，如下StringBuffer的append是一个同步方法，但是在add方法中的StringBuffer属于一个局部变量，并且不会被其他线程所使用，因此StringBuffer不可能存在共享资源竞争的情景，JVM会自动将其锁消除。锁消除的依据是逃逸分析的数据支持。
锁消除，前提是java必须运行在server模式（server模式会比client模式作更多的优化），同时必须开启逃逸分析

:-XX:+DoEscapeAnalysis 开启逃逸分析
-XX:+EliminateLocks 表示开启锁消除。

5、逃逸分析

使用逃逸分析，编译器可以对代码做如下优化：
一、同步省略。如果一个对象被发现只能从一个线程被访问到，那么对于这个对象的操作可以不考虑同步。
二、将堆分配转化为栈分配。如果一个对象在子程序中被分配，要使指向该对象的指针永远不会逃逸，对象可能是栈分配的候选，而不是堆分配。
三、分离对象或标量替换。有的对象可能不需要作为一个连续的内存结构存在也可以被访问到，那么对象的部分（或全部）可以不存储在内存，而是存储在CPU寄存器中。

6、是不是所有的对象和数组都会在堆内存分配空间？

不一定

5.3、对象布局

对象头

比如 hash码，对象所属的年代，对象锁，锁状态标志，偏向锁（线程）ID，偏向时间，数组长度（数组对象）等。Java对象头一般占有2个机器码（在32位虚拟机中，1个机器码等于4字节，也就是32bit，在64位虚拟机中，1个机器码是8个字节，也就是64bit），但是 如果对象是数组类型，则需要3个机器码，因为JVM虚拟机可以通过Java对象的元数据信息确定Java对象的大小，但是无法从数组的元数据来确认数组的大小，所以用一块来记录数组长度

实例数据

存放类的属性数据信息，包括父类的属性信息

对齐填充

由于虚拟机要求 对象起始地址必须是8字节的整数倍。填充数据不是必须存在的，仅仅是为了字节对齐

6、CountDownLatch=>倒计时器

6.1、使用

1、Zookeeper分布式锁

2、Jmeter模拟高并发

6.2、常用api

await()：等待线程池中的任务执行完毕，否则一直等待

countDown()；减一

6.3、原理

new的时候的参数代表着计数器的初始值数量，每执行一个任务计数器减一，直到减为0，菜会让其他线程执行。底层也是AQS实现

7、CyclicBarrier=>循环栅栏

7.1、原理

new的时候代表着要多少才能运行，也就是说假设5，那么此时需要5个同时到来才能运行程序

也就是所谓的中国式过马路，5人凑够数，就过，但是司机必须等到全部过去后才能过。

7.2、常用API

await()：减一

reset()：重置

7.3、使用

多线程计算数据，最后合并计算结果的场景=>银行流水

7.2、CountDownLatch和CyclicBarrier的区别

CountDownLatch允许一个或多个线程等待直到其他线程完成操作 ，只能使用一次。CyclicBarrier强调的是n个线程相互等待，直到完成再执行任务，计数器可以重置，复用，所以叫循环栅栏。

8、Semaphore=>参数代表同时访问的线程,允许多个线程同时访问

8.1、定义

就是信号量，它的作用是控制访问特定资源的线程数目，底层依赖AQS的状态State

8.2、使用

资源访问，服务限流(Hystrix里限流就有基于信号量方式)。

8.3、主要API

acquire()；尝试获取资源

release()；释放资源

9、Executors(不建议使用)

1. newCachedThreadPool创建一个可缓存线程池，如果线程池长度超过处理需
   要，可灵活回收空闲线程，若无可回收，则新建线程。
2. newFixedThreadPool 创建一个定长线程池，可控制线程最大并发数，超出的
   线程会在队列中等待。
3. newScheduledThreadPool 创建一个定长线程池，支持定时及周期性任务执
   行。
4. newSingleThreadExecutor 创建一个单线程化的线程池，它只会用唯一的工作
   线程来执行任务，保证所有任务按照指定顺序(FIFO, LIFO, 优先级)执行。

10、ThreadPoolExecutor

10.1、创建

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler)

• 1
• 2
• 3
• 4
• 5
• 6
• 7

10.2、参数解析

corePoolSize：核心线程数

maximumPoolSize：最大线程数

keepAliveTime：线程存活时间

unit：存活时间单位

workQueue：等待队列

• ArrayBlockingQueue：基于数组结构的有界阻塞队列，按FIFO排序任务；
• LinkedBlockingQuene：基于链表结构的阻塞队列，按FIFO排序任务，吞
  吐量通常要高于ArrayBlockingQuene；
• SynchronousQuene：一个不存储元素的阻塞队列，每个插入操作必须等到
  另一个线程调用移除操作，否则插入操作一直处于阻塞状态，吞吐量通常要高于
  LinkedBlockingQuene；
• priorityBlockingQuene：具有优先级的***阻塞队列；

threadFactory：线程工厂

handler：拒绝策略

• AbortPolicy：直接抛出异常，默认策略；
• CallerRunsPolicy：用调用者所在的线程来执行任务；
• DiscardOldestPolicy：丢弃阻塞队列中靠最前的任务，并执行当前任务；
• DiscardPolicy：直接丢弃任务；

10.3、原理

当线程池中的数目小于核心线程数，则创建线程运行，当线程池数目>=核心线程数，则加入等待队列中，当阻塞队列满了，并且线程数目小于最大线程数，且大于核心线程数，则创建线程去运行，如果大于最大线程数则执行拒绝策略。

11、ScheduledThreadPoolExecutor：

1. 与Timer执行定时任务的比较，相比Timer，ScheduedThreadPoolExecutor有什么优点；
2. ScheduledThreadPoolExecutor继承自ThreadPoolExecutor，所以它也是一个线程池，也有coorPoolSize和workQueue，ScheduledThreadPoolExecutor特殊的地方在于，自己实现了优先工作队列DelayedWorkQueue
3. ScheduedThreadPoolExecutor实现了ScheduledExecutorService，所以就有了任务调度的方法，如schedule，scheduleAtFixedRate和scheduleWithFixedDelay，同时注意他们之间的区别；
   • 内部类ScheduledFutureTask继承自FutureTask，实现了任务的异步执行并且可以获取返回结果。同时也实现了Delayed接口，可以通过getDelay方法获取将要执行的时间间隔；
   • 周期任务的执行其实是调用了FutureTask类中的runAndReset方法，每次执行完不设置结果和状态。
   • DelayedWorkQueue的数据结构，它是一个基于最小堆结构的优先队列，并且每次出队时能够保证取出的任务是当前队列中下次执行时间最小的任务。同时注意一下优先队列中堆的顺序，堆中的顺序并不是绝对的，但要保证子节点的值要比父节点的值要大，这样就不会影响出队的顺序

12、Exchanger(交换数据)

当一个线程运行到exchange()方法时会阻塞，另一个线程运行到exchange()时，二者
交换数据，然后执行后面的程序。

13、ThreadLocal

13.1、原理

ThreadLocal是用来维护本线程的变量的，并不能解决共享变量的并发问题。ThreadLocal是线程将值存入该线程的map中，以ThreadLocal自身作为key，需要用时获得的是该线程之前存的值。如果存入的是共享变量，那取出的也是共享变量，并发问题还是存在的。

12.2、使用场景

数据库连接、Session管理

12.3、ThreadLocal什么时候会出现OOM的情况？为什么？

ThreadLocal变量是维护在Thread内部的，这样的话只要我们的线程不退出，对象的引用就会一直存在。当线程退出时，Thread类会进行一些清理工作，其中就包含ThreadLocalMap的value

ThreadLocal在没有线程池使用的情况下，正常情况下不会存在内存泄露，但是如果使用了线程池的话，就依赖于线程池的实现，如果线程池不销毁线程的话，那么就会存在内存泄露。

14、BlockingQueue（生产者消费者模型=》队列（先进先出））

14.1、ArrayBlockingQueue

1、原理

由数组支持的有界队列，基于ReentrantLock保证线程安全，根据Condition实现队列满时的阻塞

2、使用场景：

在线程池中有比较多的应用，生产者消费者场景

14.2、LinkedBlockingQueue

由链表节点支持的***队列（理论上有界）

14.3、PriorityBlockingQueue

由优先级堆支持的***优先级队列

14.4、DelayQueue

1、原理

由优先级堆支持的、基于时间的调度队列，内部基于***队列PriorityQueue实现，而***
队列基于数组的扩容实现。

由优先级堆支持的、基于时间的调度队列

2、要求

入队的对象必须要实现Delayed接口,而Delayed集成自Comparable接口

3、使用场景

电影票

4、工作原理
队列内部会根据时间优先级进行排序。延迟类线程池周期执行

14.5、常用API

添加元素

检索元素

15、Automic类

15.1、相关术语

1、缓存行 （Cache line）

缓存的最小操作单位

2、比较并交换 Compare and Swap

CAS操作需要输入两个数值，一个旧值（期望操作前的值）和一个新值，在操作期间先生变化，如果没有发生变化，才交换成新值，发生了变化则不交换。

3、CPU流水线 CPU pipeline

CPU流水线的工作方式就象工业生产上的装配流水线，在CPU中由5~6个不同功能的电路单元组成一条指令处
理流水线，然后将一条X86指令分成5~6步后再由这些电路单元分别执行，这样就能实现在一个CPU时钟周期
完成一条指令，因此提高CPU的运算速度。

4、内存顺序冲突

Memory order violation 内存顺序冲突一般是由假共享引起，假共享是指多个CPU同时修改同一个缓存行的不同部分而引起其中一个CPU的操作无效，当出现这个内存顺序冲突时，CPU必须清空

15.2、常见类

基本类：AtomicInteger、AtomicLong、AtomicBoolean；

引用类型：AtomicReference、AtomicReference的ABA实例、AtomicStampedRerence、AtomicMarkableReference；

数组类型：AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray

属性原子修改器（Updater）：AtomicIntegerFieldUpdater、AtomicLongFieldUpdater、AtomicReferenceFieldUpdater

15.3、类的实现

Atomic包里的类基本都是使用Unsafe实现的，Unsafe只提供了三种CAS方法，compareAndSwapObject，
compareAndSwapInt和compareAndSwapLong，再看AtomicBoolean源码，发现其是先把Boolean转换成整型，再使用compareAndSwapInt进行CAS，所以原子更新double也可以用类似的思路来实现。

16、Unsafe

16.1、怎么获取实例

1、 从 getUnsafe 方法的使用限制条件出发，通过Java命令行命令 -Xbootclasspath/a 把调用Unsafe相关方法的类A所在jar包路径追加到默认的bootstrap路径中，使得A被引导类加载器加载，从而通过 Unsafe.getUnsafe 方法安全的获取Unsafe实例。

java ­Xbootclasspath/a:${path} // 其中path为调用Unsafe相关方法的类所在jar包路径
2、通过反射获取单例对象theUnsafe。

16.2、功能介绍

16.2.1、内存操作

​ 使用堆外内存的原因：

1. 对垃圾回收停顿的改善。由于堆外内存是直接受操作系统管理而不是JVM，所以当我们使用堆外内存时，即可保持较小的堆内内存规模。从而在GC时减少回收停顿对于应用的影响。
2. 提升程序I/O操作的性能。通常在I/O通信过程中，会存在堆内内存到堆外内存的
   数据拷贝操作，对于需要频繁进行内存间数据拷贝且生命周期较短的暂存数据，都建
   议存储到堆外内存。

典型应用

DirectByteBuffer是Java用于实现堆外内存的一个重要类，通常用在通信过程中做缓冲池，如在Netty、MINA等NIO框架中应用广泛。DirectByteBuffer对于堆外内存的创建、使用、销毁等逻辑均由Unsafe提供的堆外内存API来实现。下图为DirectByteBuffer构造函数，创建DirectByteBuffer的时候，通过Unsafe.allocateMemory分配内存、Unsafe.setMemory进行内存初始化，而后构建Cleaner对象用于跟踪DirectByteBuffer对象的垃圾回收，以实现当DirectByteBuffer被垃圾回收时，分配的堆外内存一起被释放。

16.2.2、CAS相关

典型应用

AtomicInteger的实现中，静态字段valueOffset即为字段value的内存偏移地址，valueOffset的值在AtomicInteger初始化时，在静态代码块中通过Unsafe的objectFieldOffset方法获取。在AtomicInteger中提供的线程安全方法中，通过字段valueOffset的值可以定位到AtomicInteger对象中value的内存地址，从而可以根据CAS实现对value字段的原子操作。

16.2.3、线程调度

典型应用

Java锁和同步器框架的核心类AbstractQueuedSynchronizer，就是通过调用LockSupport.park() 和 LockSupport.unpark() 实现线程的阻塞和唤醒的，而LockSupport的park、unpark方法实际是调用Unsafe的park、unpark方式来实现。

16.2.4、内存屏障

典型应用

在Java 8中引入了一种锁的新机制——StampedLock，它可以看成是读写锁的一个改进版本。StampedLock提供了一种乐观读锁的实现，这种乐观读锁类似于无锁的操作，完全不会阻塞写线程获取写锁，从而缓解读多写少时写线程“饥饿”现象。由于StampedLock提供的乐观读锁不阻塞写线程获取读锁，当线程共享变量从主内存load到线程工作内存时，会存在数据不一致问题，所以当使用StampedLock的乐观读锁时，需要遵
从如下图用例中使用的模式来确保数据的一致性。

17、Future/FutureTask

17.1、任务性质类型

1、CPU密集型（CPU-bound）

​ CPU密集型也叫计算密集型，指的是系统的硬盘、内存性能相对CPU要好很多，此时，系统运作大部分的状况是CPU Loading100%，CPU要读/写I/O(硬盘/内存)，I/O在很短的时间就可以完成，而CPU还有许多运算要处理，CPU Loading很高。
​ 在多重程序系统中，大部份时间用来做计算、逻辑判断等CPU动作的程序称之CPU bound。例如一个计算圆周率至小数点一千位以下的程序，在执行的过程当中绝大部份时间用在三角函数和开根号的计算，便是属于CPU bound的程序。
​ CPU bound的程序一般而言CPU占用率相当高。这可能是因为任务本身不太需要访问I/O设备，也可能是因为程序是多线程实现因此屏蔽掉了等待I/O的时间。

​ 线程数一般设置为：
线程数 = CPU核数+1 (现代CPU支持超线程)
2、IO密集型（I/O bound）

​ IO密集型指的是系统的CPU性能相对硬盘、内存要好很多，此时，系统运作，大部分的状况是CPU在等I/O (硬盘/内存) 的读/写操作，此时CPU Loading并不高。

​ I/O bound的程序一般在达到性能极限时，CPU占用率仍然较低。这可能是因为任务本身需要大量I/O操作，而pipeline做得不是很好，没有充分利用处理器能力。

​ 线程数一般设置为：
​ 线程数 = （（线程等待时间+线程CPU时间）/线程CPU时间 ）* CPU数目

17.2、Future(接口)

17.2.1、定义

‘Future就是对于具体的Runnable或者Callable任务的执行结果进行取消、查询是否完成、获取结果等操作。必要时可以通过==get()==方法获取执行结果，该方法会阻塞直到任务返回结果。

17.2.2、常见方法

cancel（）
方法用来取消任务，如果取消任务成功则返回true，如果取消任务失败则返回false。参数mayInterruptIfRunning表示是否允许取消正在执行却没有执行完毕的任务，如果设置true，则表示可以取消正在执行过程中的任务。如果任务已经完成，则无论mayInterruptIfRunning为true还是false，此方法肯定返回false，即如果取消已经完成的任务会返回false；如果任务正在执行，若mayInterruptIfRunning设置为true，则返回true，若mayInterruptIfRunning设置为false，则返回false；如果任务还没有执行，则无论mayInterruptIfRunning为true还是false，肯定返回true。

isCancelled（）
方法表示任务是否被取消成功，如果在任务正常完成前被取消成功，则返回 true。

isDone（）
方法表示任务是否已经完成，若任务完成，则返回true；

get()
方法用来获取执行结果，这个方法会产生阻塞，会一直等到任务执行完毕才返回；

get(long timeout, TimeUnit unit)
用来获取执行结果，如果在指定时间内，还没获取到结果，就直接返回null。
也就是说Future提供了三种功能：

17.2.3、功能

1）判断任务是否完成；
2）能够中断任务；
3）能够获取任务执行结果。
因为Future只是一个接口，所以是无法直接用来创建对象使用的，因此就有了下面的FutureTask。

17.3、FutureTask

FutureTask是Future接口的一个唯一实现类。
FutureTask实现了Runnable，因此它既可以通过Thread包装来直接执行，也可以提交给ExecuteService来执行。
FutureTask实现了Futrue可以直接通过get()函数获取执行结果，该函数会阻塞，直到结果返回。

18、Fork/Join（大化小，小归大，分而治之）

18.1、Fork/Join定义

Fork/Join 框架是 Java7 提供了的一个用于并行执行任务的框架， 是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。
Fork 就是把一个大任务切分为若干子任务并行的执行，Join 就是合并这些子任务的执行结果，最后得到这个大任务的结果。比如计算1+2+…＋10000，可以分割成 10 个子任务，每个子任务分别对 1000 个数进行求和，最终汇总这 10 个子任务的结果。

18.2、Fork/Join特性

1. ForkJoinPool 不是为了替代 ExecutorService，而是它的补充，在某些应用场景下性能比 ExecutorService 更好。
2. ForkJoinPool 主要用于实现“分而治之”的算法，特别是分治之后递归调用的函数，例如 quick sort 等。
3. ForkJoinPool 最适合的是计算密集型的任务，如果存在 I/O，线程间同步，sleep() 等会造成线程长时间阻塞的情况时，最好配合使用 ManagedBlocker。

18.3、工作窃取算法

18.3.1、定义

某个线程从其他队列里窃取任务来执行。

18.3.2、例子

我们需要做一个比较大的任务，我们可以把这个任务分割为若干互不依赖的子任务，为了减少线程间的竞争，于是把这些子任务分别放到不同的队列里，并为每个队列创建一个单独的线程来执行队列里的任务，线程和队列一一对应，比如A线程负责处理A队列里的任务。
但是有的线程会先把自己队列里的任务干完，而其他线程对应的队列里还有任务等待处理。干完活的线程与其等着，不如去帮其他线程干活，于是它就去其他线程的队列里窃取一个任务来执行。而在这时它们会访问同一个队列，所以为了减少窃取任务线程和被窃取任务线程之间的竞争，通常会使用双端队列，被窃取任务线程永远从双端队列的头部拿任务执行，而窃取任务的线程永远从双端队列的尾部拿任务执行。
工作窃取算法的优点是充分利用线程进行并行计算，并减少了线程间的竞争，其缺点是在某些情况下还是存在竞争，比如双端队列里只有一个任务时。并且消耗了更多的系统资源，比如创建多个线程和多个双端队列

18.3.3、Fork/Join中的体现

1. ForkJoinPool 的每个工作线程都维护着一个工作队列（WorkQueue），这是一个双端队列（Deque），里面存放的对象是任务（ForkJoinTask）。
2. 每个工作线程在运行中产生新的任务（通常是因为调用了 fork()）时，会放入工作队列的队尾，并且工作线程在处理自己的工作队列时，使用的是 LIFO 方式，也就是说每次从队尾取出任务来执行。
3. 每个工作线程在处理自己的工作队列同时，会尝试窃取一个任务（或是来自于刚刚提交到 pool 的任务，或是来自于其他工作线程的工作队列），窃取的任务位于其他线程的工作队列的队首，也就是说工作线程在窃取其他工作线程的任务时，使用的是 FIFO方式。
4. 在遇到 join() 时，如果需要 join 的任务尚未完成，则会先处理其他任务，并等待其完成。
5. 在既没有自己的任务，也没有可以窃取的任务时，进入休眠。

18.4、ForkJoin的类

ForkJoinTask：我们要使用 ForkJoin 框架，必须首先创建一个 ForkJoin 任务。它提供在任务中执行 fork() 和 join() 操作的机制，通常情况下我们不需要直接继承 ForkJoinTask 类，而只需要继承它的子类，Fork/Join 框架提供了以下两个子类：

RecursiveAction：用于没有返回结果的任务。(比如写数据到磁盘，然后就退出了。 一个RecursiveAction可以把自己的工作分割成更小的几块， 这样它们可以由独立的线程或者CPU执行。 我们可以通过继承来实现一个RecursiveAction)

RecursiveTask ：用于有返回结果的任务。(可以将自己的工作分割为若干更小任务，并将这些子任务的执行合并到一个集体结果。可以有几个水平的分割和合并)

CountedCompleter： 在任务完成执行后会触发执行一个自定义的钩子函数

ForkJoinPool ：ForkJoinTask 需要通过 ForkJoinPool 来执行，任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务。

18.5、使用场景例子

定义fork/join任务，随机生成2000w条数据在数组当中，然后求和

19、Disruptor(生产者消费者模型)

19.1、核心设计原理(怎么解决队列速度慢)

框架使用RingBuffer来作为队列的数据结构，RingBuffer就是一个可自定义大小的环形数组。除数组外还有一个序列号(sequence)，用以指向下一个可用的元素，供生产者与消费者使用。

1、环形数组结构： 为了避免垃圾回收，采用数组而非链表。同时，数组对处理器的缓存机制更加友好（CPU加载空间局部性原则）。

2、元素位置定位： 数组长度2^n，通过位运算，加快定位的速度。下标采取递增的形式。不用担心index溢出的问题。index是long类型，即使100万QPS的处理速度，也需要30万年才能用完。

3、无锁设计： 每个生产者或者消费者线程，会先申请可以操作的元素在数组中的位置，申请到之后，直接在该位置写入或者读取数据.

19.2、核心组件与作用（8个）

• RingBuffer——Disruptor底层数据结构实现，核心类，是线程间交换数据的中转地；
• Sequencer——序号管理器，生产同步的实现者，负责消费者/生产者各自序号、序号栅栏的管理和协调,Sequencer有单生产者,多生产者两种不同的模式,里面实现了各种同步的算法；
• Sequence——序号，声明一个序号，用于跟踪ringbuffer中任务的变化和消费者的消费情况，disruptor里面大部分的并发代码都是通过对Sequence的值同步修改实现的,而非锁,这是disruptor高性能的一个主要原因；
• SequenceBarrier——序号栅栏，管理和协调生产者的游标序号和各个消费者的序号，确保生产者不会覆盖消费者未来得及处理的消息，确保存在依赖的消费者之间能够按照正确的顺序处理， Sequence Barrier是由Sequencer创建的,并被Processor持有；
• EventProcessor——事件处理器，监听RingBuffer的事件，并消费可用事件，从RingBuffer读取的事件会交由实际的生产者实现类来消费；它会一直侦听下一个可用的号，直到该序号对应的事件已经准备好。
• EventHandler——业务处理器，是实际消费者的接口，完成具体的业务逻辑实现，第三方实现该接口；代表着消费者。
• Producer——生产者接口，第三方线程充当该角色，producer向RingBuffer写入事件。
• Wait Strategy：Wait Strategy决定了一个消费者怎么等待生产者将事件（Event）放入Disruptor中。

19.3、等待策略（Wait Strategy）

1、BlockingWaitStrategy

Disruptor的默认策略是BlockingWaitStrategy。在BlockingWaitStrategy内部是使用锁和condition来控制线程的唤醒。 BlockingWaitStrategy是最低效的策略，但其对CPU的消耗最小并且在各种不同部署环境中能提供更加一致的性能表现。

2、SleepingWaitStrategy

SleepingWaitStrategy 的性能表现跟 BlockingWaitStrategy 差不多，对 CPU 的消耗也类似，但其对生产者线程的影响最小， 通过使用LockSupport.parkNanos(1)来实现循环等待。一般来说Linux系统会暂停一个线程约60µs，这样做的好处是，生产线程不需要 采取任何其他行动就可以增加适当的计数器，也不需要花费时间信号通知条件变量。但是，在生产者线程和使用者线程之间移动事件的平均 延迟会更高。它在不需要低延迟并且对生产线程的影响较小的情况最好。一个常见的用例是异步日志记录。

3、YieldingWaitStrategy

YieldingWaitStrategy是可以使用在低延迟系统的策略之一。YieldingWaitStrategy将自旋以等待序列增加到适当的值。 在循环体内，将调用Thread.yield（），以允许其他排队的线程运行。在要求极高性能且事件处理线数小于 CPU 逻辑核心数的场景中， 推荐使用此策略；例如，CPU开启超线程的特性。

4、BusySpinWaitStrategy

性能最好，适合用于低延迟的系统。在要求极高性能且事件处理线程数小于CPU逻辑核心数的场景中，推荐使用此策略；例如，CPU开启超线程的特性。

19.4、写数据

单线程写数据的流程：

1. 申请写入m个元素；
2. 若是有m个元素可以入，则返回最大的序列号。这儿主要判断是否会覆盖未读的元
   素；
3. 若是返回的正确，则生产者开始写入元素。

20、Hashmap/ConcurrentHashMap

20.1、说一下 HashMap 的实现原理？

• HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
• HashMap的数据结构： 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
• HashMap 基于 Hash 算法实现的

1. 当我们往Hashmap中put元素时，利用key的hashCode重新hash计算
   出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个
之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

20.2、HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

1. 1.8用了红黑树
2. 1.7插入的时候用了头插法，1.8插入的时候用了尾插法
3. 1.7会rehash，1.8没有这份代码逻辑
4. 1.8的hash算法时高低16位做异或运算，1.7的时候会进行4次无符号右移，5个与运算（具体原因：JDK7的Hash算法⽐JDK8中的更复杂，Hash算法越复杂，⽣成的hashcode则更散列，那么hashmap中的元素则更散列，更散列则hashmap的查询性能更好，JDK7中没有红⿊树，所以只能优化Hash算法使得元素更散列，⽽JDK8中增加了红⿊树，查询性能得到了保障，所以可以简化⼀下Hash算法，毕竟Hash算法越复杂就越消耗CPU）
5. JDK8中扩容的条件和JDK7中不⼀样，除开判断size是否⼤于阈值之外，JDK7中还判断了tab[i]是否为空，不为空的时候才会进⾏扩容，⽽JDK8中则没有该条件了
6. JDK8中还多了⼀个API：putIfAbsent(key,value)
7. JDK7和JDK8扩容过程中转移元素的逻辑不⼀样，JDK7是每次转移⼀个元素，JDK8是先算出来当前位置上哪些元素在新数组的低位上，哪些在新数组的⾼位上，然后在⼀次性转移

20.3、HashMap的put方法的具体流程？

1. 根据key生成hashcode
2. 判断当前HashMap对象中的数组是否为空，如果为空则初始化该数组
3. 1.7的时候会进行4次无符号右移，5个与运算，1.8会进行高16位和低16位进行逻辑与运算，算出hashcode基于当前数组对应的数组下标i
4. 判断数组的第i个位置的元素（tab[i]）是否为空
   a. 如果为空，则将key，value封装为Node对象赋值给tab[i]
   b. 如果不为空：
   i. 如果put⽅法传⼊进来的key等于tab[i].key，那么证明存在相同的key
   ii. 如果不等于tab[i].key，则：
   1. 如果tab[i]的类型是TreeNode，则表示数组的第i位置上是⼀颗红⿊树，那么将key和value插⼊到红⿊树中，并且在插⼊之前会判断在红⿊树中是否存在相同的key
   2. 如果tab[i]的类型不是TreeNode，则表示数组的第i位置上是⼀个链表，那么遍历链表寻找是否存在相同的key，并且在遍历的过程中会对链表中的结点数进⾏计数，当遍历到最后⼀个结点时，会将key,value封装为Node插⼊到链表的尾部，同时判断在插⼊新结点之前的链表结点个数是不是⼤于等于8，且数组的长度大于64，如果是，则将链表改为红⿊树。
   iii. 如果上述步骤中发现存在相同的key，则根据onlyIfAbsent标记来判断是否需要更新value值，然后返回oldValue
5. modCount++
6. HashMap的元素个数size加1
7. 如果size⼤于扩容的阈值，则进⾏扩容

20.4、HashMap的get方法的具体流程？

1. 根据key⽣成hashcode
2. 如果数组为空，则直接返回空
3. 如果数组不为空，则利⽤hashcode和数组⻓度通过逻辑与操作算出key所对应的数组下标i
4. 如果数组的第i个位置上没有元素，则直接返回空
5. 如果数组的第1个位上的元素的key等于get⽅法所传进来的key，则返回该元素，并获取该元素的value
6. 如果不等于则判断该元素还有没有下⼀个元素，如果没有，返回空
7. 如果有则判断该元素的类型是链表结点还是红⿊树结点
   a. 如果是链表则遍历链表
   b. 如果是红⿊树则遍历红⿊树
8. 找到即返回元素，没找到的则返回空

20.5、HashMap的扩容操作是怎么实现的？

①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
②.每次扩展的时候，都是扩展2倍；
③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

20.6、HashMap是怎么解决哈希冲突的？

1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平
   均；
3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

20.7、能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

• 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。
• 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
• 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。
• 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode()和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

20.8、为什么HashMap中String、Integer这样的包装类适合作为K？

String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

1. 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
2. 内部已重写了 equals() 、 hashCode() 等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；

20.9、如果使用Object作为HashMap的Key，应该怎么办呢？

重写 hashCode() 和 equals() 方法

1. 重写 hashCode() 是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
2. 重写 equals() 方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)

20.10、HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

hashCode() 方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过 hashCode() 计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
所以：

1. HashMap自己实现了自己的 hash() 方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
2. 在保证数组长度为2的幂次方的时候，使用 hash() 运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题；

20.11、HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap的长度为什么是2的幂次方。

那为什么是两次扰动呢？

• 这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

20.12、HashMap 与 HashTable 有什么区别？

1. 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
6. 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

20.13、如何决定使用 HashMap 还是TreeMap？

对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。

20.14、HashMap 和 ConcurrentHashMap 的区别

1. ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）
2. HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

20.15、ConcurrentHashMap 和 Hashtable 的区别？

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

• 底层数据结构 ： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
• 实现线程安全的方式（重要） ：
  ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用Node 数组+链表+红黑树的数据结构来实现，并发控制使用synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
  ②Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：
HashTable:

JDK1.7的ConcurrentHashMap：

JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：

ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。

20.16、ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？

JDK1.7
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

1. 该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；
2. Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。

JDK1.8
在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS+ Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
结构如下：

附加源码，有需要的可以看看
插入元素过程（建议去看看源码）：
如果相应位置的Node还没有初始化，则调用CAS插入相应的数据；

1. 如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；
2. 如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；

21、ArrayList

21.1、快速失败机制 “Fail-Fast”

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

解决办法：

1. 在遍历过程中，所有涉及到改变modCount值得地方全部加上synchronized。
2. 使用CopyOnWriteArrayList来替换ArrayList

21.2、安全失败 Fail-Safe

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

21.3、Fail-Fast(快速失败)和Fail-Safe(安全失败)比较

Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常。

21.4、说一下 ArrayList 的优缺点

优点：

• ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了RandomAccess 接口，因此查找的时候非常快。
• ArrayList 在顺序添加一个元素的时候非常方便。

缺点:

• 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
• 插入元素的时候，也需要做一次元素复制操作，缺点同上

ArrayList 比较适合顺序添加、随机访问的场景

21.5、如何实现数组和 List 之间的转换？

• 数组转 List：使用 Arrays. asList(array) 进行转换。
• List 转数组：使用 List 自带的 toArray() 方法。

21.6、ArrayList 和 LinkedList 的区别是什么？

• 数据结构实现：ArrayList 是动态数组的数据结构实现，而LinkedList 是双向链表的数据结构实现。
• 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为
  LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
• 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
• 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
• 线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

补充：数据结构基础之双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

21.7、ArrayList 和 Vector 的区别是什么？

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合

• 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而ArrayList 是非线程安全的。
• 性能：ArrayList 在性能方面要优于 Vector。
• 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在Vector 扩容每次会增加 1 倍，而ArrayList 只会增加 50%。

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

21.8、插入数据时，ArrayList、LinkedList、Vector谁速度较快？阐述 ArrayList、Vector、LinkedList 的存储性能和特性？

• ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。
• Vector 中的方法由于加了 synchronized 修饰，因此 Vector是线程安全容器，但性能上较ArrayList差。
• LinkedList 使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但插入数据时只需要记录当前项的前后项即可，所以 LinkedList插入速度较快。

21.9、多线程场景下如何使用ArrayList？

1、Collections.synchronizedList
2、Vector
3、CopyOnWriteArrayList

• 1
• 2
• 3

22、CopyOnWriteArrayList

主要体现就是一个不需要加同步锁的无锁ArrayList，他的底层就是采用COW机制实现的，

读时直接读，写时需要复制一份再在复制的那一份中进行写操作，保证了线程安全。

23、TreeMap

23.1、原理

底层是由红黑树实现的map，自定义排序Comparator

23.2、红黑树

23.2.1、性质

1.每个结点不是红色就是黑色
2.不可能有连在一起的红色结点（黑色的就可以），每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据
3.根结点都是黑色 root
4.每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

23.2.2、插入的时候旋转和颜色变换规则

1.变颜色的情况：当前结点的父亲是红色，且它的祖父结点的另一个子结点
也是红色。（叔叔结点）：
（1）把父节点设为黑色
（2）把叔叔也设为黑色
（3）把祖父也就是父亲的父亲设为红色（爷爷）
（4）把指针定义到祖父结点(爷爷)设为当前要操作的.
2.左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋
以父结点作为左旋。指针变换到父亲结点
3.右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。右旋
（1）把父结点变为黑色
（2）把祖父结点变为红色 （爷爷）
（3）以祖父结点旋转（爷爷）

23.2.3、删除

分情况

1、删除节点只有一个子节点：（直接删除此节点，然后将孩子节点代替父亲节点）

（1）如果删除的节点是红色的，直接删除就行，不会影响；

（2）如果删除节点是黑色的，那么就要考虑孩子节点了(只有一个孩子节点，考虑红黑树平衡条件，根据性质4这个孩子节点肯定是红色的，不然左右孩子的黑色路径数就不对了)，所以，直接将孩子节点代替父亲节点后，将这这个节点变成黑色。

2.删除节点没有子节点：（直接删除节点）

（1）如果删除的节点是红色的，那么直接删除

（2）如果删除的节点是黑色的。那这个就要重新来搞平衡了

3.删除节点有两个子节点：（找到这个节点的后继节点，然后将后继节点代替这个节点）这样其实就转换成情况1或者2了。

针对情况2进行分析：

（1）待删除节点是黑色的，它的兄弟节点是红色的，根据性质4 父节点必须为黑色，否则有一边的孩子结点就多了一个黑色了。操作：交换兄弟和父亲节点的颜色，以父节点左旋，重新设置兄弟节点。

（2） 待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。操作：兄弟结点变为红色，指针指向父节点继续处理。

（3） 待删除的兄弟节点是黑色的节点，且兄弟节点的左子树是红色的，右子树是黑色的。操作：兄弟节点变红，兄弟节点的左节点变黑，以兄弟节点右旋。

（4）待删除的节点的兄弟节点是黑色的节点，兄弟节点的右节点为红色，左节点为任意颜色的。操作：交换父节点和兄弟节点的颜色，兄弟节点的右节点设为黑色，以父节点左旋。

23.2.4、红黑树的性能分析

插入 近似：nlogn
查找 logn
删除：近似logn

24、StampedLock

StampedLock提供了一种乐观读锁的实现，这种乐观读锁类似于无锁的操作，完
全不会阻塞写线程获取写锁，从而缓解读多写少时写线程“饥饿”现象。由于
StampedLock提供的乐观读锁不阻塞写线程获取读锁，当线程共享变量从主内存load到线
程工作内存时，会存在数据不一致问题，所以当使用StampedLock的乐观读锁时，需要遵
从如下图用例中使用的模式来确保数据的一致性.

25、wait()与sleep() 方法的区别。

1、wait()是Object的方法；sleep()是Thread的方法

2、wait()释放持有的锁，sleep()不释放

3、wait()方法必须放在同步控制方法和同步代码块中使用；sleep()方法则可以放在任何地方使用

4、sleep()方法必须捕获异常，wait()不需要捕获异常

26、什么时候用线程，什么时候用进程，nginx底层的用到了什么？

1、需要频繁创建销毁的优先使用线程；因为对进程来说创建和销毁一个进程代价是很大的。

2、线程的切换速度快，所以在需要大量计算，切换频繁时用线程，还有耗时的操作使用线程可提高应用程序的响应，

3、因为对CPU系统的效率使用上线程更占优，所以可能要发展到多机分布的用进程，多核分布用线程；

4、并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求；

5、需要更稳定安全时，适合选择进程；需要速度时，选择线程更好。

特别的，nginx底层是用的是进程，一个master进程和多个worker进程。