Java 中内置了许许多多的数据结构，其中集合与映射的底层实现是面试八股文里经常被问到的，因此我写下这篇博客来系统整理一下这些知识点。

Java 中有哪些常用的集合与映射 链接到标题

img1

img2

从上文这个继承演示图中可以直观的看到，在 Collection 这个大类下分为了 List、Set、Queue 三个子类，而 Map 是独立的一大类。

List 链接到标题

List 是一类有序（指插入顺序）的 Collection，实现此接口的类允许用户精准的控制每个元素的插入位置，也能根据索引访问 List 中的元素。

常用的 List 实现类有：ArrayList、LinkedList、Vector、Stack。

其中 ArrayList 和 Vector 的功能和底层实现上几乎一模一样，区别在于 Vector 是线程安全的，因此性能较 ArrayList 差，使用的频率几乎可以忽略不计，因此本文只介绍另外三者。

ArrayList 链接到标题

ArrayList 的底层是一个可变大小的数组，允许存储包括 null 在内的所有元素。

底层数组的默认大小为 10，在当前数组存满了的情况下通过 add 方法再添加元素时会触发扩容机制：若翻倍扩容后的数组大小小于常数 SOFT_MAX_ARRAY_LENGTH（值为 Integer.MAX_VALUE - 8）时则是翻倍扩容，否则先将容量一次性扩充到常数 SOFT_MAX_ARRAY_LENGTH 的大小，然后再随着元素的添加递增容量直到超出 int 类型的正范围。

当需要插入大量元素时，可以在插入前调用 ensureCapacity 方法来手动触发扩容机制，从而提高插入的效率。

需要注意的是，ArrayList 没有同步方法。如果多个线程访问同一个 List，则必须手动实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(new ArrayList(...));

因为底层是数组实现，因此 ArrayList 支持对元素的快速随机访问（$O(1)$)，但插入和删除的速度较慢（$O(n)$)。

LinkedList 链接到标题

LinkedList 的底层是一个双向链表，允许存储包括 null 在内的所有元素。

双向链表的特性导致 LinkedList 的插入和删除效率很高（$O(1)$)，但随机访问的速度较慢（$O(n)$)。

同样因为双向链表的特性，LinkedList 实现了 Deque 接口，可以作为堆栈、队列、双端队列使用。

同样需要注意的是，LinkedList 没有同步方法。如果多个线程访问同一个 List，则必须手动实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(new LinkedList(...));

Stack 链接到标题

Stack 其实是 Vector 的一个子类，把一些 Vector 中已有的一些方法再次封装为堆栈中所特有的那些名称，以实现其先进后出的特性。

Stack 的栈顶是底层数组的尾部，因此它很好的避免了数组删改效率低的问题，同时线程安全的设计让它可以在多线程的情况下方便使用。

Set 链接到标题

Set 是一类无序（指插入顺序）的不允许存在重复元素的 Collection。

常用的 Set 实现有 HashSet、LinkedHashSet、TreeSet。

Set 底层是通过 Map 来实现的，所有的 Key 都对应一个相同的 Value，即一个名为 PRESENT 的 Object 类型常量。

HashSet 链接到标题

HashSet 底层通过 HashMap 实现，保证 Key 的唯一性但不保证任何有序性，且是线程不安全的，因此如果想在多线程的情况下使用，需要进行同步封装：

Set set = Collections.synchronizedSet(new HashSet(...));

HashSet 允许用 null 作为元素，有且仅有一个元素为 null。因为底层散列表的存在，HashMap 在元素的增删改查上有很高的效率（$O(1)$)。

LinkedHashSet 链接到标题

LinkedHashSet 是 HashSet 的一个子类，底层通过 LinkedHashMap 实现，在 HashMap 的基础上使用双向链表维护了元素的插入顺序。

TreeSet 链接到标题

TreeSet 底层通过 TreeMap 实现，可以维护集合中元素的顺序（默认为升序，可以通过构造时传入比较器来实现自定义排序），且是线程不安全的，因此如果想在多线程的情况下使用，需要进行同步封装：

Set set = Collections.synchronizedSet(new TreeSet(...));

TreeSet 不允许用 null 作为元素。底层红黑树的存在导致 TreeSet 不允许快速随机访问，只能通过迭代器进行遍历，因此在元素的增删改查上效率较低（$O(log_2n)$)。

Queue 链接到标题

Queue 是一类满足先进先出特性的 Collection，因为其像一列队伍一般，所以可以运用到很多场景下，也因此产生了很多变种。

按阻塞分类可以分成 阻塞队列 和 非阻塞队列 两种。阻塞队列提供了可阻塞的 put 和 take 方法，即在队列满的时候调用 put 方法或是在队列空的时候调用 take 方法会阻塞直到有位置可以插入或有元素可以使用。

按大小分类可以分成 有界队列 和 无界队列 两种，队列的容量固定的就是有界，容量可变的就是无界。

按功能分类可以分成 普通队列、双端队列、优先队列、延迟队列 和 其他队列 五种：

  • 普通队列只允许在尾部添加新元素，从头部获取元素。
  • 双端队列则允许在收尾都进行增删操作。
  • 优先队列则是一种通常运用堆来实现的，根据一种已知的优先级规律来决定队首元素的特殊队列。
  • 延迟队列则可以看作是一种以时间为度量单位的优先队列，入队元素到达指定的延迟时间后方可出队。
  • 其他队列是指一种特殊的队列—— SynchronousQueue，它的特别之处在于它内部没有容器，每次调用 put 方法添加数据后，必须等待另一个线程拿走数据后才可以再次添加数据。

常用的 Queue 实现类有：ArrayDeque、PriorityQueue、LinkedBlockingDeque。

ArrayDeque 链接到标题

ArrayDeque 底层通过循环的可变长度的数组来实现双端队列，且是线程不安全的，不允许存储 null 元素。

ArrayDeque 的底层数组在扩容方面用了另外一套规则：容量小于 64 时翻倍扩容，容量大于 64 时扩容 50%，此外还有一些特殊情况要区别对待，例如新增元素所需空间大于扩容空间时直接扩容到新增元素所需大小、扩容超出 int 类型的正范围时直接扩容到 Integer.MAX_VALUE 大小。

需要特别注意的是在扩容时遇到元素跨过数组的起始和结束位置的情况需要特殊处理：将数组的第二部分（从 head 到数组的结束位置）的元素复制到新数组的末尾同样长度的部分，此时扩容出来的缓冲区就变成了从 tail 到 head 的这一段区域。

PriorityQueue 链接到标题

PriorityQueue 底层通过可变长度的数组实现的优先堆来实现功能的，且是线程不安全的，不允许存储 null 元素。

PriorityQueue 的扩容规则类似 ArrayDeque，它的优先级比较算法可以通过在构造队列时传入一个 Comparator 的实现类来自定义。

LinkedBlockingDeque 链接到标题

LinkedBlockingDeque 底层通过链表实现阻塞队列，可以通过在构造的时候传入一个 int 类型的数据来控制队列元素的容量，使其成为一个有界队列，如果不传入则默认的容量上限为 int 类型的正范围。

LinkedBlockingDeque 底层通过可重入锁 ReentrantLock 来实现阻塞的功能，因此它是线程安全的，但不允许存储 null 元素。

Map 链接到标题

Map 是一类存储键值对的映射，没有实现 Collection 接口。Key 是唯一的，Value 可以重复。从 Map 中检索元素时，只要给出了键对象，就会返回对应的值对象。

常用的 Map 实现类有：HashMap、LinkedHashMap、TreeMap、Hashtable、ConcurrentHashMap。

Hashtable 可以被看作是 JDK 1.8 之前的 HashMap 的线程安全且不允许 null 键版本，但 Hashtable 是一个效率低的历史遗留类，应该避免使用，本文也不过多介绍。

HashMap 链接到标题

在 JDK 1.8 之前，HashMap 底层通过数组 + 链表实现，数组实现的 Hash 表作为 HashMap 的主体，将键对象通过 Hash 算法得到的 HashCode 作为数组的 index 进行存储，若遇到哈希冲突，则通过“拉链法”解决：在该 index 对应的桶上拉一个单向链表。

在 JDK 1.8 及之后，解决哈希冲突有了较大变化，当链表的长度大于树化阈值（默认为 8）后，链表将会被转换为红黑树进行存储，当红黑树的结点数量小于反树化阈值（默认为 6）后，红黑树将会被转换为链表进行存储。

HashMap 是无序的，允许存储一个 null 键和任意个 null 值，其高效的底层设计为基本操作带来了十分稳定的低时间代价。HashMap 是线程不安全的，因此如果想在多线程的情况下使用，需要进行同步封装：

Map map = Collections.synchronizedMap(new HashMap(...));

需要注意的是 Hash 表的容量必须为 2 的幂，当 Hash 表中占用的桶数量到达一个阈值（最大容量的 Load Factor 倍，默认为 0.75 倍）时，Hash 表会进行翻倍扩容。

img3

HashMap 的线程不安全 链接到标题

  • JDK 1.7 中，由于多线程对 HashMap 进行扩容，调用了 HashMap.transfer()，具体原因：某个线程执行过程中，被挂起，其他线程已经完成数据迁移，等 CPU 资源释放后被挂起的线程重新执行之前的逻辑，数据已经被改变，造成死循环、数据丢失。
  • JDK 1.8 中，由于多线程对 HashMap 进行 put 操作，调用了 HashMap.putVal()，具体原因：假设两个线程 A、B 都在进行 put 操作，并且 hash 函数计算出的插入下标是相同的，当线程 A 执行完一部分代码（此时得到了插入下标且完成了 hash 碰撞测试，尚未插入数据）后由于时间片耗尽导致被挂起，而线程 B 得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程 A 获得时间片，由于之前已经进行了 hash 碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程 B 插入的数据被线程 A 覆盖了，从而线程不安全。

数据丢失、死循环已经在在 JDK 1.8 中已经得到了很好的解决，如果你去阅读 1.8 的源码会发现找不到 HashMap.transfer()，因为 JDK 1.8 直接在 HashMap.resize() 中完成了数据迁移。

LinkedHashMap 链接到标题

LinkedHashMap 是 HashMap 的子类，因此底层是和 HashMap 一样的由数组、链表、红黑树实现的，但在此基础上 LinkedHashMap 增加了一条双向链表，维护了键值对的插入顺序。

TreeMap 链接到标题

TreeMap 底层通过红黑树实现，因此它的基本操作比起 HashMap 来说略逊一筹，但比链表等结构来说也是十分优秀了。

此外 TreeMap 可以维护键值对集合中的顺序（默认为键对象升序，可以通过构造时传入比较器来实现键对象自定义排序）。

ConcurrentHashMap 链接到标题

ConcurrentHashMap 底层实现和 HashMap 一致，但是它通过锁的机制使其变得线程安全（ JDK 1.8 之前使用的是 segment 分段锁，JDK 1.8 及之后使用的是一种叫做 CAS（Compare and Swap） 的原子操作来实现的。