Java成神之路

java集合

fxz大约 56 分钟interview

java集合

1.说说 List, Set, Queue, Map 四者的区别？

  • List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
  • Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
  • Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
  • Map(用 key 来搜索的专家): 使用键值对（key-value）存储，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

2.介绍一下集合框架底层数据结构？

先来看一下 Collection 接口下面的集合。

List

  • ArrayList： Object[] 数组
  • Vector：Object[] 数组
  • LinkedList： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set

  • HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素
  • LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
  • TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)

Queue

  • PriorityQueue: Object[] 数组来实现二叉堆
  • ArrayQueue: Object[] 数组 + 双指针

再来看看 Map 接口下面的集合。

Map

  • HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
  • LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
  • Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
  • TreeMap： 红黑树（自平衡的排序二叉树）

3.为什么要使用集合？

	当我们需要保存一组类型相同的数据的时候，我们应该是用一个容器来保存，这个容器就是数组，但是，使用数组存储对象具有一定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的，于是，就出现了“集合”，集合同样也是用来存储多个数据的。

	数组的缺点是一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。 但是集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。

4.ArrayList 和 Vector 的区别?

  • ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 ；
  • Vector 是 List 的古老实现类，底层使用Object[ ] 存储，线程安全的。

5.ArrayList 与 LinkedList 区别?

  1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  2. 底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
  3. 插入和删除是否受元素位置的影响：
    • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
    • LinkedList 采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！

6.聊一聊ArrayList的扩容机制？

	**以无参数构造方法创建 `ArrayList` 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。**

  1. Arrlist扩容是原来的数组长度1.5倍。

  2. 数组进行扩容时，会将老数据中得元素重新拷贝一份道新的数组中，每次数组容量得增长大于时原用量得1.5倍。

7.comparable 和 Comparator 有什么区别？

  • comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
  • comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

8.比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

  • HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
  • HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
  • 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景。

9.Queue 与 Deque 的区别？

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类。

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

10.ArrayDeque 与 LinkedList 的区别？

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能。

  • ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
  • ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
  • ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

11.说一说 PriorityQueue？

PriorityQueue 与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：

  • PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
  • PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
  • PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
  • PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

12.HashMap 和 Hashtable 的区别？

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

13.HashMap 和 HashSet 区别？

HashSet 底层就是基于 HashMap 实现的。

HashMapHashSet
实现了 Map 接口实现 Set 接口
存储键值对仅存储对象
调用 put()向 map 中添加元素调用 add()方法向 Set 中添加元素
HashMap 使用键（Key）计算 hashcodeHashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以equals()方法用来判断对象的相等性

14.HashMap 和 TreeMap 区别？

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

15.说说HashMap 的底层实现？

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK1.8 之后相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

  • loadFactor 加载因子

    loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

    loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

    给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

  • put方法

      HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。
  
  **对 putVal 方法添加元素的分析如下：**

  1. 如果定位到的数组位置没有元素 就直接插入。

  2. 如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

我们再来对比一下 JDK1.7 put 方法的代码

对于 put 方法的分析如下：

  • ① 如果定位到的数组位置没有元素 就直接插入。
  • ② 如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的 key 比较，如果 key 相同就直接覆盖，不同就采用头插法插入元素

16.HashMap 的长度为什么是 2 的幂次方？

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

17.ConcurrentHashMap 和 Hashtable 的区别?

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

  • 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
  • 实现线程安全的方式（重要）： ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 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：

18.ConcurrentHashMap底层数据结构分析？

  1. ConcurrentHashMap 1.7

    1. 存储结构

下图存在两个笔误 : Segmeng -> Segment ; HashEntity -> HashEntry

Java 7 中 ConcurrentHashMap 的存储结构如上图，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

Java 7 中：

ConcurrnetHashMap 的初始化逻辑。

  1. 必要参数校验。
  2. 校验并发级别 concurrencyLevel 大小，如果大于最大值，重置为最大值。无参构造默认值是 16.
  3. 寻找并发级别 concurrencyLevel 之上最近的 2 的幂次方值，作为初始化容量大小，默认是 16。
  4. 记录 segmentShift 偏移量，这个值为【容量 = 2 的N次方】中的 N，在后面 Put 时计算位置时会用到。默认是 32 - sshift = 28.
  5. 记录 segmentMask，默认是 ssize - 1 = 16 -1 = 15.
  6. 初始化 segments[0]，默认大小为 2，负载因子 0.75，扩容阀值是 2*0.75=1.5，插入第二个值时才会进行扩容。

ConcurrentHashMap 在 put 一个数据时的处理流程，下面梳理下具体流程。

  1. 计算要 put 的 key 的位置，获取指定位置的 Segment。

  2. 如果指定位置的 Segment 为空，则初始化这个 Segment。

    初始化 Segment 流程：

    1. 检查计算得到的位置的 Segment 是否为null.
    2. 为 null 继续初始化，使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。
    3. 再次检查计算得到的指定位置的 Segment 是否为null.
    4. 使用创建的 HashEntry 数组初始化这个 Segment.
    5. 自旋判断计算得到的指定位置的 Segment 是否为null，使用 CAS 在这个位置赋值为 Segment.

  3. Segment.put 插入 key,value 值。

ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置

到这里就很简单了，get 方法只需要两步即可。

  1. 计算得到 key 的存放位置。
  2. 遍历指定位置查找相同 key 的 value 值。

Jdk1.8

Java7 中 ConcurrentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。

Java8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java7 中的 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。

19.谈谈ConcurrentHashMap的扩容机制？

1.7版本

  1. 1.7版本的ConcurrentHashMap是基于Segment分段实现的

  2. 每个Segment相对于⼀个⼩型的HashMap

  3. 每个Segment内部会进⾏扩容，和HashMap的扩容逻辑类似

  4. 先⽣成新的数组，然后转移元素到新数组中

  5. 扩容的判断也是每个Segment内部单独判断的，判断是否超过阈值

1.8版本

  1. 1.8版本的ConcurrentHashMap不再基于Segment实现

  2. 当某个线程进⾏put时，如果发现ConcurrentHashMap正在进⾏扩容那么该线程⼀起进⾏扩容

  3. 如果某个线程put时，发现没有正在进⾏扩容，则将key-value添加到ConcurrentHashMap中，然后判断是否超过阈值，超过了则进⾏扩容

  4. ConcurrentHashMap是⽀持多个线程同时扩容的

  5. 扩容之前也先⽣成⼀个新的数组

  6. 在转移元素时，先将原数组分组，将每组分给不同的线程来进⾏元素的转移，每个线程负责⼀组或 多组的元素转移⼯作

20.Jdk1.7到Jdk1.8 HashMap 发⽣了什么变化(底层)?

  1. 1.7中底层是数组+链表，1.8中底层是数组+链表+红⿊树，加红⿊树的⽬的是提⾼HashMap插⼊和查询整体效率

  2. 1.7中链表插⼊使⽤的是头插法，1.8中链表插⼊使⽤的是尾插法，因为1.8中插⼊key和value时需要判断链表元素个数，所以需要遍历链表统计链表元素个数，所以正好就直接使⽤尾插法

  3. 1.7中哈希算法⽐较复杂，存在各种右移与异或运算，1.8中进⾏了简化，因为复杂的哈希算法的⽬的 就是提⾼散列性，来提供HashMap的整体效率，⽽1.8中新增了红⿊树，所以可以适当的简化哈希 算法，节省CPU资源。

21.说⼀下HashMap的Put⽅法

先说HashMap的Put⽅法的⼤体流程：

  1. 根据Key通过哈希算法与与运算得出数组下标

  2. 如果数组下标位置元素为空，则将key和value封装为Entry对象（JDK1.7中是Entry对象，JDK1.8中是Node对象）并放⼊该位置

  3. 如果数组下标位置元素不为空，则要分情况讨论

a. 如果是JDK1.7，则先判断是否需要扩容，如果要扩容就进⾏扩容，如果不⽤扩容就⽣成Entry对象，并使⽤头插法添加到当前位置的链表中

b. 如果是JDK1.8，则会先判断当前位置上的Node的类型，看是红⿊树Node，还是链表Node

ⅰ. 如果是红⿊树Node，则将key和value封装为⼀个红⿊树节点并添加到红⿊树中去，在这个 过程中会判断红⿊树中是否存在当前key，如果存在则更新value

ⅱ. 如果此位置上的Node对象是链表节点，则将key和value封装为⼀个链表Node并通过尾插 法插⼊到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会 判断是否存在当前key，如果存在则更新value，当遍历完链表后，将新链表Node插⼊到链 表中，插⼊到链表后，会看当前链表的节点个数，如果⼤于等于8，那么则会将该链表转 成红⿊树

ⅲ. 将key和value封装为Node插⼊到链表或红⿊树中后，再判断是否需要进⾏扩容，如果需要 就扩容，如果不需要就结束PUT⽅法

22.HashMap的扩容机制原理

1.7版本

  1. 先⽣成新数组
  2. 遍历⽼数组中的每个位置上的链表上的每个元素
  3. 取每个元素的key，并基于新数组⻓度，计算出每个元素在新数组中的下标
  4. 将元素添加到新数组中去
  5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

1.8版本

  1. 先⽣成新数组

  2. 遍历⽼数组中的每个位置上的链表或红⿊树

  3. 如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去

  4. 如果是红⿊树，则先遍历红⿊树，先计算出红⿊树中每个元素对应在新数组中的下标位置

     a. 统计每个下标位置的元素个数

 b. 如果该位置下的元素个数超过了8，则⽣成⼀个新的红⿊树，并将根节点的添加到新数组的对应位置

 c. 如果该位置下的元素个数没有超过8，那么则⽣成⼀个链表，并将链表的头节点添加到新数组的对应位置

  5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

23.CopyOnWriteArrayList的底层原理是怎样的

  1. ⾸先CopyOnWriteArrayList内部也是⽤过数组来实现的，在向CopyOnWriteArrayList添加元素时，会复制⼀个新的数组，写操作在新数组上进⾏，读操作在原数组上进⾏ 。

  2. 并且，写操作会加锁，防⽌出现并发写⼊丢失数据的问题。

  3. 写操作结束之后会把原数组指向新数组。

  4. CopyOnWriteArrayList允许在写操作时来读取数据，⼤⼤提⾼了读的性能，因此适合读多写少的应 ⽤场景，但是CopyOnWriteArrayList会⽐较占内存，同时可能读到的数据不是实时最新的数据，所 以不适合实时性要求很⾼的场景。

24.fail-safe 机制与 fail-fast 机制分别有什 么作用?

fail-safe 和 fail-fast， 是多线程并发操作集合时的一种失败处理机制。

Fail-fast：表示快速失败， 在集合遍历过程中，一旦发现容器中的数据被修改了， 会立刻抛出 ConcurrentModificationException (并发修改)异常，从而导致遍历失败，像这种情况（贴下面这个图）。

定义一个 Map 集合，使用 Iterator 迭代器进行数据遍历，在遍历过程中，对集 合数据做变更时，就会发生 fail-fast 。

java.util 包下的集合类都是快速失败机制的,常见的的使用 器有 HashMap 和 ArrayList 等。

Fail-safe， 表示失败安全，也就是在这种机制下，出现集合元素的修改，不会抛 出 ConcurrentModificationException。

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

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

比如这种情况（贴下面这个图），定义了一个 CopyOnWriteArrayList， 在对这 个集合遍历过程中，对集合元素做修改后，不会抛出异常，但同时也不会打印出 增加的元素。

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

常 见 的 的 使 用 fail-safe 方 式 遍 历 的 容 器 有 ConcerrentHashMap 和 CopyOnWriteArrayList 等。

25.什么叫做阻塞队列的有界和无界

阻塞队列，是一种特殊的队列，它在普通队列的基础上提供了两个附加功能

当队列为空的时候，获取队列中元素的消费者线程会被阻塞，同时唤醒生产者线程。

当队列满了的时候，向队列中添加元素的生产者线程被阻塞，同时唤醒消费者线程。

其中，阻塞队列中能够容纳的元素个数，通常情况下是有界的，比如我们实例化一个ArrayBlockingList，可以在构造方法中传入一个整形的数字，表示这个基于数组的阻塞队列中能够容纳的元素个数。这种就是有界队列。

而无界队列，就是没有设置固定大小的队列，不过它并不是像我们理解的那种元 素没有任何限制，而是它的元素存储量很大，像 LinkedBlockingQueue，它的默 认队列长度是 Integer.Max_Value，所以我们感知不到它的长度限制。

无界队列存在比较大的潜在风险，如果在并发量较大的情况下，线程池中可以几 乎无限制的添加任务，容易导致内存溢出的问题！

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

ConcurrentHashMap 的整体架构

这个是 ConcurrentHashMap 在 JDK1.8 中的存储结构，它是由数组、单向链表、 红黑树组成。

当我们初始化一个 ConcurrentHashMap 实例时，默认会初始化一个长度为 16 的数组。由于 ConcurrentHashMap 它的核心仍然是 hash 表，所以必然会存在 hash 冲突问题。 ConcurrentHashMap 采用链式寻址法来解决 hash 冲突。

当 hash 冲 突 比 较 多 的 时 候 ， 会 造 成 链 表 长 度 较 长 ， 这 种 情 况 会 使 得 ConcurrentHashMap 中数据元素的查询复杂度变成 O(n)。因此在 JDK1.8 中， 引入了红黑树的机制。 当数组长度大于 64 并且链表长度大于等于 8 的时候，单项链表就会转换为红黑树。 另外，随着 ConcurrentHashMap 的动态扩容，一旦链表长度小于 8，红黑树会退化成单向链表。

ConcurrentHashMap 的基本功能

ConcurrentHashMap 本质上是一个 HashMap，因此功能和 HashMap 一样，但 是 ConcurrentHashMap 在 HashMap 的基础上，提供了并发安全的实现。 并发安全的主要实现是通过对指定的 Node 节点加锁，来保证数据更新的安全性。

ConcurrentHashMap 在性能方面做的优化

如果在并发性能和数据安全性之间做好平衡，在很多地方都有类似的设计，比如 cpu 的三级缓存、mysql 的 buffer_pool、Synchronized 的锁升级等等。

ConcurrentHashMap 也做了类似的优化，主要体现在以下几个方面： 在 JDK1.8 中， ConcurrentHashMap 锁的粒度是数组中的某一个节点， 而在 JDK1.7，锁定的是 Segment，锁的范围要更大，因此性能上会更低。

引入红黑树，降低了数据查询的时间复杂度，红黑树的时间复杂度是 O(logn)。

当数组长度不够时， ConcurrentHashMap 需要对数组进行扩容，在扩容的实现 上， ConcurrentHashMap 引入了多线程并发扩容的机制，简单来说就是多个线程对原始数组进行分片后，每个线程负责一个分片的数据迁移，从而提升了扩容 过程中数据迁移的效率。

ConcurrentHashMap 中有一个 size()方法来获取总的元素个数，而在多线程并 发场景中，在保证原子性的前提下来实现元素个数的累加，性能是非常低的。 ConcurrentHashMap 在这个方面的优化主要体现在两个点：

当线程竞争不激烈时，直接采用 CAS 来实现元素个数的原子递增。

如果线程竞争激烈，使用一个数组来维护元素个数，如果要增加总的元素个数， 则直接从数组中随机选择一个，再通过 CAS 实现原子递增。它的核心思想是引 入了数组来实现对并发更新的负载

27.基于数组的阻塞队列 ArrayBlockingQueue 原理

阻塞队列（BlockingQueue）是在队列的基础上增加了两个附加操作，

在队列为空的时候，获取元素的线程会等待队列变为非空。

当队列满时，存储元素的线程会等待队列可用。

由于阻塞队列的特性，可以非常容易实现生产者消费者模型，也就是生产者只需 要关心数据的生产，消费者只需要关注数据的消费，所以如果队列满了，生产者 就等待，同样，队列空了，消费者也需要等待。

要实现这样的一个阻塞队列，需要用到两个关键的技术，队列元素的存储、以及 线程阻塞和唤醒。

而 ArrayBlockingQueue 是基于数组结构的阻塞队列，也就是队列元素是存储在 一个数组结构里面，并且由于数组有长度限制，为了达到循环生产和循环消费的 目的， ArrayBlockingQueue 用到了循环数组。

而线程的阻塞和唤醒， 用到了 J.U.C 包里面的 ReentrantLock 和 Condition。 Condition 相当于 wait/notify 在 JUC 包里面的实现。