简介要介绍

Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 <code>Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。

Collection接口有三个子主要的子接口：List ,Set,Queue。

下面我们就来详细的介绍：List ,Set, Queue，Map

目录

简介要介绍

List

ArrayList

LinkedList

CopyOnWriteArrayList

set

queue

queue

Dqueue

非阻塞队列

ArrayDqueue

PriorityQueue 

ConcurrentLinkedQueue 

BlockingQueue

ArrayBlockingQueue

LinkedBlockingQueue

PriorityBlockingQueue

SynchronousQueue

DelayQueue

map

HashMap 和 HashSet 区别

HashMap 和 TreeMap 区别

HashMap 的底层实现

JDK1.8 之前

JDK1.8 之后

HashMap 多线程操作导致死循环问题

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.8 之前

JDK1.8 之后

JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

---

 

区别：

List：存储的元素是有序可重复的。

Set:存储的元素是无序不可重复的。

Queue: 按特定的排队规则来确定先后顺序,可重复

Map: 使用键值对（key-value）存储,key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

下面我们分别来讲解这些集合常用的实现类

List

ArrayList

ArrayList是线程不安全的，底层使用 Object[]存储数据，可以存储任何类型的对象，包括 null 值，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。

核心属性：

private static final int DEFAULT_CAPACITY = 10;//默认容量

transient Object[] 存储元素的集合

private int size;  元素个数

构造方法：

public ArrayList() ；

public ArrayList(int initialCapacity) ；

public ArrayList(Collection<? extends E> c) ；

 

 

实现接口

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

扩容机制：

我们可以在创建ArrayList的时候指定初始容量的大小，以无参数构造方法创建 ArrayList 时，有一个默认容量10，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。

ArrayList 扩容主要依赖三个核心参数

1.数组默认容量

2.数组长度

3.数组的最小需求容量

在add方法内部执行元素添加前会先判断数组是否需要扩容。

1）需求容量初始为元素个数加一，先判断数组是否为空，如果为空选择默认容量和元素个数加一值大的来作为最小需求容量。

2）然后判断数组最小需求量是否大于数组实际长度，若大于说明需要扩容，调用grow方法

3）grow方法 会先将目标扩充容量设置为数组长度的1.5倍，判断最小需求量是否大于目标扩充容量，若大于将最小需求量赋值给目标扩充容量。

3）接着判断目标扩充容量是否大于数组最大容量，若大于，判断最小需求量和数组最大容量的大小，若需求量大将目标扩充容量设置为Intger.MAXVALUE,若小于目标容量的值设置为数组最大容量（Intger.MAXVALUE-6）

4）执行扩容。

LinkedList

LinkedList 是一个基于双向链表实现的集合类，经常被拿来和 ArrayList 做比较。

实现了以下接口：

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。需要注意，Deque 的发音为 "deck" [dɛk]，这个大部分人都会读错。Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

CopyOnWriteArrayList

CopyOnWriteArrayList是线程安全的List，CopyOnWriteArrayList 线程安全的核心在于其采用了 写时复制（Copy-On-Write） 的策略。

Copy-On-Write：如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。

当需要修改（ add，set、remove 等操作） CopyOnWriteArrayList 的内容时，不会直接修改原数组，而是会先创建底层数组的副本，对副本数组进行修改，修改完之后再将修改后的数组赋值回去，这样就可以保证写操作不会影响读操作了。

实现了以下接口：

List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

set

HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素。LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。

善者异同

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

queue

queue

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

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

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

---

Dqueue

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

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

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

---

非阻塞队列

ArrayDqueue

ArrayDeque 实现了 Deque 接口具有队列的功能.线程不安全

ArrayDeque 是基于可变长的数组和双指针来实现,不支持存储 NULL 数据,ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。

PriorityQueue 

PriorityQueue 是在 JDK1.5 中被引入的, 是Queue的实现类，其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。并且它是线程不安全的。

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

ConcurrentLinkedQueue 

ConcurrentLinkedQueue 是线程安全的非阻塞队列，基于链表实现，是无界的

ConcurrentLinkedQueue 应该算是在高并发环境中性能最好的队列了。 主要使用 CAS 非阻塞算法来实现线程安全。

ConcurrentLinkedQueue 适合在对性能要求相对较高，同时对队列的读写存在多个线程同时进行的场景，即如果对队列加锁的成本较高则适合使用无锁的 ConcurrentLinkedQueue 来替代。

BlockingQueue

BlockingQueue （阻塞队列）是一个接口，继承自 Queue。BlockingQueue阻塞的原因是其支持当队列没有元素时一直阻塞，直到有元素；还支持如果队列已满，一直等到队列可以放入新元素时再放入。

Java 中常用的阻塞队列实现类有以下几种：

ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为Integer.MAX_VALUE。和ArrayBlockingQueue不同的是， 它仅支持非公平的锁访问机制。PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现Comparable接口或者在构造函数中传入Comparator对象，并且不能插入 null 元素。SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。

ArrayBlockingQueue

ArrayBlockingQueue 是 BlockingQueue 接口的有界阻塞队列实现类，常用于多线程之间的数据共享，底层采用数组实现。

在创建时必须指定容量大小，并且还可以设置公平性。

为了保证线程安全，ArrayBlockingQueue 的并发控制采用可重入锁 ReentrantLock ，不管是插入操作还是读取操作，都需要获取到锁才能进行操作。并且，它还支持公平和非公平两种方式的锁访问机制，默认是非公平锁。

应用举例：

生产者生产完会使用 put 方法生产 元素给消费者进行消费，当队列元素达到我们设置的上限时，put 方法就会阻塞。同理消费者也会通过 take 方法消费元素，当队列为空时，take 方法就会阻塞消费者线程。

 

 

通过继承 AbstractQueue 获得队列所有的操作模板，其实现的入队和出队操作的整体框架。然后 ArrayBlockingQueue 通过继承 BlockingQueue 获取到阻塞队列的常见操作并将这些操作实现，填充到 AbstractQueue 模板方法的细节中，由此 ArrayBlockingQueue 成为一个完整的阻塞队列。

实现原理：

ArrayBlockingQueue 的实现原理主要分为以下几点（这里以阻塞式获取和新增元素为例介绍）：

ArrayBlockingQueue 内部维护一个定长的数组用于存储元素。通过使用 ReentrantLock 锁对象对读写操作进行同步，即通过锁机制来实现线程安全。通过 Condition 实现线程间的等待和唤醒操作。

这里再详细介绍一下线程间的等待和唤醒具体的实现（不需要记具体的方法，面试中回答要点即可）：

当队列已满时，生产者线程会调用 notFull.await() 方法让生产者进行等待，等待队列非满时插入（非满条件）。当队列为空时，消费者线程会调用 notEmpty.await()方法让消费者进行等待，等待队列非空时消费（非空条件）。当有新的元素被添加时，生产者线程会调用 notEmpty.signal()方法唤醒正在等待消费的消费者线程。当队列中有元素被取出时，消费者线程会调用 notFull.signal()方法唤醒正在等待插入元素的生产者线程。

核心成员变量 notEmpty(非空) 和 notFull （非满）实际上就是两个Condition接口的实例对象，在ArrayBliockingQueue构造方法内部创建。

//用lock锁创建两个条件控制队列生产和消费

notEmpty = lock.newCondition();

notFull = lock.newCondition();

ArrayBlockingQueue 阻塞式获取和新增元素的方法为：

put(E e)：将元素插入队列中，如果队列已满，则该方法会一直阻塞，直到队列有空间可用或者线程被中断。take() ：获取并移除队列头部的元素，如果队列为空，则该方法会一直阻塞，直到队列非空或者线程被中断。

ArrayBlockingQueue 非阻塞式获取和新增元素的方法为：

offer(E e)：将元素插入队列尾部。如果队列已满，则该方法会直接返回 false，不会等待并阻塞线程。poll()：获取并移除队列头部的元素，如果队列为空，则该方法会直接返回 null，不会等待并阻塞线程。add(E e)：将元素插入队列尾部。如果队列已满则会抛出 IllegalStateException 异常，底层基于 offer(E e) 方法。remove()：移除队列头部的元素，如果队列为空则会抛出 NoSuchElementException 异常，底层基于 poll()。peek()：获取但不移除队列头部的元素，如果队列为空，则该方法会直接返回 null，不会等待并阻塞线

LinkedBlockingQueue

 LinkedBlockingQueue是BlockingQueue 接口的无界阻塞队列， 基于链表实现，创建时可以不指定容量大小，默认是Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。

LinkedBlockingQueue不同于ArrayBlockingQueue，它的锁是分离的，即生产用的是putLock，消费是takeLock，这样可以防止生产者和消费者线程之间的锁争夺。

PriorityBlockingQueue

PriorityBlockingQueue 是一个支持优先级的无界阻塞队列。默认情况下元素采用自然顺序进行排序，也可以通过自定义类实现 compareTo() 方法来指定元素排序规则，或者初始化时通过构造器参数 Comparator 来指定排序规则。

PriorityBlockingQueue 并发控制采用的是可重入锁 ReentrantLock，队列为无界队列（ArrayBlockingQueue 是有界队列，LinkedBlockingQueue 也可以通过在构造函数中传入 capacity 指定队列最大的容量，但是 PriorityBlockingQueue 只能指定初始的队列大小，后面插入元素的时候，如果空间不够的话会自动扩容）。

是 PriorityQueue 的线程安全版本。不可以插入 null 值，同时，插入队列的对象必须是可比较大小的（comparable），否则报 ClassCastException 异常。

SynchronousQueue

同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，SynchronousQueue通常用于线程之间的直接传递数据。

DelayQueue

延迟队列，用于实现延时任务比如订单下单 15 分钟未支付直接取消。它是 BlockingQueue 的一种，底层是一个基于 PriorityQueue 实现的一个无界队列，是线程安全的。

DelayQueue 中存放的元素必须实现 Delayed 接口，并且需要重写 getDelay()方法（计算是否到期）。

DelayQueue 的 4 个核心成员变量和构造方法如下：

//可重入锁，实现线程安全的关键

private final transient ReentrantLock lock = new ReentrantLock();

//延迟队列底层存储数据的集合,确保元素按照到期时间升序排列

private final PriorityQueue<E> q = new PriorityQueue<E>();

//指向准备执行优先级最高的线程

private Thread leader = null;

//实现多线程之间等待唤醒的交互

private final Condition available = lock.newCondition();

public DelayQueue() {}

//addAll()方法将集合元素存到优先队列 q 中

public DelayQueue(Collection<? extends E> c) {

this.addAll(c);

}

lock : 我们都知道 DelayQueue 存取是线程安全的，所以为了保证存取元素时线程安全，我们就需要在存取时上锁，而 DelayQueue 就是基于 ReentrantLock 独占锁确保存取操作的线程安全。q : 延迟队列要求元素按照到期时间进行升序排列，所以元素添加时势必需要进行优先级排序,所以 DelayQueue 底层元素的存取都是通过这个优先队列 PriorityQueue 的成员变量 q 来管理的。leader : 延迟队列的任务只有到期之后才会执行,对于没有到期的任务只有等待,为了确保优先级最高的任务到期后可以即刻被执行,设计者就用 leader 来管理延迟任务，只有 leader 所指向的线程才具备定时等待任务到期执行的权限，而其他那些优先级低的任务只能无限期等待，直到 leader 线程执行完手头的延迟任务后唤醒它。available : 上文讲述 leader 线程时提到的等待唤醒操作的交互就是通过 available 实现的，假如线程 1 尝试在空的 DelayQueue 获取任务时，available 就会将其放入等待队列中。直到有一个线程添加一个延迟任务后通过 available 的 signal 方法将其唤醒

map

HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

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

HashMap 和 TreeMap 区别

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

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

NavigableMap 接口提供了丰富的方法来探索和操作键值对:

定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry() 等方法可以用于定位大于、小于、大于等于、小于等于给定键的最接近的键值对。子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。

这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让 TreeMap 成为了处理有序集合搜索问题的强大工具。

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

HashMap 的底层实现

JDK1.8 之前

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

JDK1.8 之后

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

HashMap 多线程操作导致死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

ConcurrentHashMap 和 Hashtable 的区别

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；实现线程安全的方式（重要）：

在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分割分段(Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个。到了 JDK1.8 的时候，ConcurrentHashMap 已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.8 之前

首先将数据分为一段一段（这个“段”就是 Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

Segment 继承了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

JDK1.8 之后

ConcurrentHashMap 取消了 Segment 分段锁，采用 Node + CAS + synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。

Java 8 中，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。

JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

线程安全实现方式：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。并发度：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

 

 

参考链接：想详细理解请看Java集合常见面试题总结(下) | JavaGuide