前言
数据结构作为每一个开发者不可回避的问题，而 Java 对于不同的数据结构提供了非常成熟的实现，这一个又一个实现既是面试中的难点，也是工作中必不可少的工具，在此，笔者经历漫长的剖析，将其抽丝剥茧的呈现出来，在此仅作抛砖引玉，望得诸君高见，若君能有所获则在下甚是不亦乐乎，若有疑惑亦愿与诸君共求之！本文一共 3.5 W字，25 张图，预计阅读 2h。可以收藏这篇文章，用的时候防止找不到，这可能是你能看到的最详细的一篇文章了。整理了2021年Java面试题。
1、集合框架
Java整个集合框架如上图所示（这儿不包括Map，Map的结构将放在集合后边进行讲述），可见所有集合实现类的最顶层接口为Iterable和Collection接口，再向下Collection分为了三种不同的形式，分别是List，Queue和Set接口，然后就是对应的不同的实现方式。
1.1顶层接口Iterable
//支持lambda函数接口
import java.util.function.Consumer;
public interface Iterable {
//iterator()方法
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}}
复制代码
Iterable接口中只有iterator()一个接口方法，Iterator也是一个接口，其主要有如下两个方法hasNext()和next()方法。
package java.util;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public interface Collection extends Iterable {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
boolean retainAll(Collection<?> c);
void clear();
int hashCode();
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}}
复制代码
可见Collection的主要接口方法有：
2、List
List表示一串有序的集合，和Collection接口含义不同的是List突出有序的含义。
2.1 List接口
package java.util;
import java.util.function.UnaryOperator;
public interface List extends Collection {
<T> T[] toArray(T[] a);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
boolean equals(Object o);
E get(int index);
E set(int index, E element);
void add(int index, E element);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}}
复制代码
可见List其实比Collection多了添加方法add和addAll查找方法get,indexOf,set等方法，并且支持index下标操作。Collection 与 List 的区别？a. 从上边可以看出Collection和List最大的区别就是Collection是无序的，不支持索引操作，而List是有序的。Collection没有顺序的概念。b. List中Iterator为ListIterator。c. 由a推导List可以进行排序，所以List接口支持使用sort方法。d. 二者的Spliterator操作方式不一样。为什么子类接口里重复申明父类接口呢?官方解释: 在子接口中重复声明父接口是为了方便看文档。比如在 java doc 文档里，在 List 接口里也能看到 Collecion 声明的相关接口。
2.2 List实现ArrayList
ArrayList是List接口最常用的一个实现类，支持List接口的一些列操作。
2.2.1 ArrayList继承关系
2.2.2 ArrayList组成
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
//真正存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
private int size;
复制代码
一定要记住ArrayList中的transient Object[] elementData，该elementData是真正存放元素的容器，可见ArrayList是基于数组实现的。
2.2.3 ArrayList构造函数
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
复制代码
Object[] elementData 是ArrayList真正存放数据的数组。
ArrayList支持默认大小构造，和空构造，当空构造的时候存放数据的Object[] elementData是一个空数组{}。
2.2.4 ArrayList中添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;}
复制代码
注意ArrayList中有一个modCount的属性，表示该实例修改的次数。（所有集合中都有modCount这样一个记录修改次数的属性），每次增改添加都会增加一次该ArrayList修改次数，而上边的add(E e)方法是将新元素添加到list尾部。
2.2.4 ArrayList扩容
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;}
复制代码
可见当初始化的list是一个空ArrayList的时候，会直接扩容到DEFAULT_CAPACITY，该值大小是一个默认值10。而当添加进ArrayList中的元素超过了数组能存放的最大值就会进行扩容。注意到这一行代码
int newCapacity = oldCapacity + (oldCapacity >> 1);
复制代码
采用右移运算，就是原来的一般，所以是扩容1.5倍。比如10的二进制是1010，右移后变成101就是5。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);}
复制代码
2.2.5 数组copy
Java 是无法自己分配空间的，是底层C和C++的实现。以 C 为例，我们知道 C 中数组是一个指向首部的指针，比如我们 C 语言对数组进行分配内存。Java 就是通过 arraycopy 这个 native 方法实现的数组的复制。
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);复制代码
p = (int )malloc(lensizeof(int));
复制代码
这样的好处何在呢？**Java里内存是由jvm管理的，而数组是分配的连续内存，而arrayList不一定是连续内存，当然jvm会帮我们做这样的事，jvm会有内部的优化，会在后续的例子中结合问题来说明。
2.2.6 why?elementData用transient修饰？
transient的作用是该属性不参与序列化。
ArrayList继承了标示序列化的Serializable接口
对arrayList序列化的过程中进行了读写安全控制。是如何实现序列化安全的呢?
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}}
/**
- Reconstitute the ArrayList instance from a stream (that is,
- deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}}
复制代码
在序列化方法writeObject()方法中可以看到，先用默认写方法，然后将size写出，最后遍历写出elementData，因为该变量是transient修饰的，所有进行手动写出，这样它也会被序列化了。那是不是多此一举呢？
protected transient int modCount = 0;
复制代码
当然不是，其中有一个关键的modCount, 该变量是记录list修改的次数的，当写入完之后如果发现修改次数和开始序列化前不一致就会抛出异常，序列化失败。这样就保证了序列化过程中是未经修改的数据,保证了序列化安全。（java集合中都是这样实现）
2.3 LinkedList
众所周知LinkedList是一种链表结构，那么Java里LinkedList是如何实现的呢？
2.3.1 LinkedList继承关系
可见LinkedList既是List接口的实现也是Queue的实现（Deque），故其和ArrayList相比LinkedList支持的功能更多，其可视作队列来使用，当然下文中不强调其队列的实现。
2.3.2 LinkedList的结构
transient Node first;
/**
- Pointer to last node.
- Invariant: (first == null && last == null) ||
- (last.next == null && last.item != null)
*/
transient Node last;
复制代码
LinkedList由一个头节点和一个尾节点组成，分别指向链表的头部和尾部。 LinkedList中Node源码如下，由当前值item，和指向上一个节点prev和指向下个节点next的指针组成。并且只含有一个构造方法，按照(prev, item, next)这样的参数顺序构造。
private static class Node {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}}
复制代码
那LinkedList里节点Node是什么结构呢？ LinkedList由一个头节点，一个尾节点和一个默认为0的size构成，可见其是双向链表。
transient int size = 0;
transient Node first;
transient Node last;
public LinkedList() {
}
复制代码
数据结构中链表的头插法linkFirst和尾插法linkLast
/**
* Links e as first element. 头插法
*/
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element. 尾插法
*/
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
复制代码
2.3.3 LinkedList查询方法
按照下标获取某一个节点**：get方法，获取第index个节点。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
复制代码
node(index)方法是怎么实现的呢？判断index是更靠近头部还是尾部，靠近哪段从哪段遍历获取值。
Node node(int index) {
// assert isElementIndex(index);
//判断index更靠近头部还是尾部
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
复制代码
查询索引修改方法，先找到对应节点，将新的值替换掉老的值。
public E set(int index, E element) {
checkElementIndex(index);
Node x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
复制代码
这个也是为什么ArrayList随机访问比LinkedList快的原因**，LinkedList要遍历找到该位置才能进行修改，而ArrayList是内部数组操作会更快。
2.4.3 LinkedList修改方法
新增一个节点，可以看到是采用尾插法将新节点放入尾部。
public boolean add(E e) {
linkLast(e);
return true;
}
复制代码
2.5 Vector
和ArrayList一样，Vector也是List接口的一个实现类。其中List接口主要实现类有ArrayLIst，LinkedList，Vector，Stack，其中后两者用的特别少。
2.5.1 vector组成
和ArrayList基本一样。
//存放元素的数组
protected Object[] elementData;
//有效元素数量，小于等于数组长度
protected int elementCount;
//容量增加量，和扩容相关
protected int capacityIncrement;
复制代码
2.5.2 vector线程安全性
vector是线程安全的，synchronized修饰的操作方法。
2.5.3 vector扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容大小
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码
看源码可知，扩容当构造没有capacityIncrement时，一次扩容数组变成原来两倍，否则每次增加capacityIncrement。
2.5.4 vector方法经典示例
移除某一元素
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
//复制数组，假设数组移除了中间某元素，后边有效值前移1位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//引用null ，gc会处理
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
复制代码
这儿主要有一个两行代码需要注意，笔者在代码中有注释。数组移除某一元素并且移动后，一定要将原来末尾设为null，且有效长度减1。总体上vector实现是比较简单粗暴的，也很少用到，随便看看即可。
2.6 Stack
Stack也是List接口的实现类之一，和Vector一样，因为性能原因，更主要在开发过程中很少用到栈这种数据结构，不过栈在计算机底层是一种非常重要的数据结构，下边将探讨下Java中Stack。
2.6.1 Stack的继承关系
Stack继承于Vector，其也是List接口的实现类。之前提到过Vector是线程安全的，因为其方法都是synchronized修饰的，故此处Stack从父类Vector继承而来的操作也是线程安全的。
2.6.2 Stack的使用
正如Stack是栈的实现，故其主要操作为push入栈和pop出栈，而栈最大的特点就是LIFO（Last In First Out）。
Stack strings = new Stack<>();
strings.push("aaa");
strings.push("bbb");
strings.push("ccc");
System.err.println(strings.pop());
复制代码
上边代码可以看到，最后push入栈的字符串"ccc"也最先出栈。
2.6.3 Stack源码
/**
* Stack源码（Jdk8）
*/
public
class Stack extends Vector {
public Stack() {
}
//入栈，使用的是Vector的addElement方法。
public E push(E item) {
addElement(item);
return item;
}
//出栈，找到数组最后一个元素，移除并返回。
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
private static final long serialVersionUID = 1224463164541339165L;
}
复制代码
从Stack的源码中可见，其用的push方法用的是Vector的addElement（E e）方法，该方法是将元素放在集合的尾部，而其pop方法使用的是Vector的removeElementAt(Index x)方法，移除并获取集合的尾部元素，可见Stack的操作就是基于线性表的尾部进行操作的。
3、Queue
正如数据结构中描述，queue是一种先进先出的数据结构，也就是first in first out。可以将queue看作一个只可以从某一段放元素进去的一个容器，取元素只能从另一端取，整个机制如下图所示，不过需要注意的是，队列并没有规定是从哪一端插入，从哪一段取出。
3.1 什么是Deque
Deque英文全称是Double ended queue，也就是俗称的双端队列。就是说对于这个队列容器，既可以从头部插入也可以从尾部插入，既可以从头部获取，也可以从尾部获取，其机制如下图所示。
3.1.1 Java中的Queue接口
此处需要注意，Java中的队列明确有从尾部插入，头部取出，所以Java中queue的实现都是从头部取出。
package java.util;
public interface Queue extends Collection {
//集合中插入元素
boolean add(E e);
//队列中插入元素
boolean offer(E e);
//移除元素，当集合为空，抛出异常
E remove();
//移除队列头部元素并返回，如果为空，返回null
E poll();
//查询集合第一个元素，如果为空，抛出异常
E element();
//查询队列中第一个元素，如果为空，返回null
E peek();
}
复制代码
Java queue常常使用的方法如表格所示，对于表格中接口和表格中没有的接口方法区别为：队列的操作不会因为队列为空抛出异常，而集合的操作是队列为空抛出异常。
3.1.2 Deque接口
package java.util;
public interface Deque extends Queue {
//deque的操作方法
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// 省略一堆stack接口方法和collection接口方法
}
复制代码
和Queue中的方法一样，方法名多了First或者Last，First结尾的方法即从头部进行操作，Last即从尾部进行操作。
3.1.3 Queue，Deque的实现类
Java中关于Queue的实现主要用的是双端队列，毕竟操作更加方便自由，Queue的实现有PriorityQueue，Deque在java.util中主要有ArrayDeque和LinkedList两个实现类，两者一个是基于数组的实现，一个是基于链表的实现。在之前LinkedList文章中也提到过其是一个双向链表，在此基础之上实现了Deque接口。
3.2 PriorityQueue
PriorityQueue是Java中唯一一个Queue接口的直接实现，如其名字所示，优先队列，其内部支持按照一定的规则对内部元素进行排序。
3.2.1 PriorityQueue继承关系
先看下PriorityQueue的继承实现关系，可知其是Queue的实现类，主要使用方式是队列的基本操作，而之前讲到过Queue的基本原理，其核心是FIFO（First In First Out）原理。 Java中的PriorityQueue的实现也是符合队列的方式，不过又略有不同，却别就在于PriorityQueue的priority上，其是一个支持优先级的队列，当使用了其priority的特性的时候，则并非FIFO。
3.2.2 PriorityQueue的使用
案列1：
PriorityQueue
