数据结构作为每一个开发者不可回避的问题，而 Java 对于不同的数据结构提供了非常成熟的实现，这一个又一个实现既是面试中的难点，也是工作中必不可少的工具，在此，笔者经历漫长的剖析，将其抽丝剥茧的呈现出来，在此仅作抛砖引玉，望得诸君高见，若君能有所获则在下甚是不亦乐乎，若有疑惑亦愿与诸君共求之！本文一共 3.5 W字，25 张图，预计阅读 2h。可以收藏这篇文章，用的时候防止找不到，这可能是你能看到的最详细的一篇文章了。整理了2021年Java面试题。
Java整个集合框架如上图所示（这儿不包括Map，Map的结构将放在集合后边进行讲述），可见所有集合实现类的最顶层接口为Iterable和Collection接口，再向下Collection分为了三种不同的形式，分别是List，Queue和Set接口，然后就是对应的不同的实现方式。
Iterable接口中只有iterator()一个接口方法，Iterator也是一个接口，其主要有如下两个方法hasNext()和next()方法。
可见Collection的主要接口方法有： 
List表示一串有序的集合，和Collection接口含义不同的是List突出有序的含义。
可见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 声明的相关接口。
ArrayList是List接口最常用的一个实现类，支持List接口的一些列操作。
2.2.1 ArrayList继承关系
2.2.2 ArrayList组成
一定要记住ArrayList中的transient Object[] elementData，该elementData是真正存放元素的容器，可见ArrayList是基于数组实现的。
2.2.3 ArrayList构造函数
- Object[] elementData 是ArrayList真正存放数据的数组。
- ArrayList支持默认大小构造，和空构造，当空构造的时候存放数据的Object[] elementData是一个空数组{}。
2.2.4 ArrayList中添加元素
注意ArrayList中有一个modCount的属性，表示该实例修改的次数。（所有集合中都有modCount这样一个记录修改次数的属性），每次增改添加都会增加一次该ArrayList修改次数，而上边的add(E e)方法是将新元素添加到list尾部。
2.2.4 ArrayList扩容
可见当初始化的list是一个空ArrayList的时候，会直接扩容到DEFAULT_CAPACITY，该值大小是一个默认值10。而当添加进ArrayList中的元素超过了数组能存放的最大值就会进行扩容。注意到这一行代码
采用右移运算，就是原来的一般，所以是扩容1.5倍。比如10的二进制是1010，右移后变成101就是5。
2.2.5 数组copy
Java 是无法自己分配空间的，是底层C和C++的实现。以 C 为例，我们知道 C 中数组是一个指向首部的指针，比如我们 C 语言对数组进行分配内存。Java 就是通过 arraycopy 这个 native 方法实现的数组的复制。
这样的好处何在呢？Java里内存是由jvm管理的，而数组是分配的连续内存，而arrayList不一定是连续内存，当然jvm会帮我们做这样的事，jvm会有内部的优化，会在后续的例子中结合问题来说明。
2.2.6 why?elementData用transient修饰？
- transient的作用是该属性不参与序列化。
- ArrayList继承了标示序列化的Serializable接口
- 对arrayList序列化的过程中进行了读写安全控制。是如何实现序列化安全的呢?
在序列化方法writeObject()方法中可以看到，先用默认写方法，然后将size写出，最后遍历写出elementData，因为该变量是transient修饰的，所有进行手动写出，这样它也会被序列化了。那是不是多此一举呢？
当然不是，其中有一个关键的modCount, 该变量是记录list修改的次数的，当写入完之后如果发现修改次数和开始序列化前不一致就会抛出异常，序列化失败。这样就保证了序列化过程中是未经修改的数据,保证了序列化安全。（java集合中都是这样实现）
众所周知LinkedList是一种链表结构，那么Java里LinkedList是如何实现的呢？
2.3.1 LinkedList继承关系
可见LinkedList既是List接口的实现也是Queue的实现（Deque），故其和ArrayList相比LinkedList支持的功能更多，其可视作队列来使用，当然下文中不强调其队列的实现。
2.3.2 LinkedList的结构
LinkedList由一个头节点和一个尾节点组成，分别指向链表的头部和尾部。 LinkedList中Node源码如下，由当前值item，和指向上一个节点prev和指向下个节点next的指针组成。并且只含有一个构造方法，按照(prev, item, next)这样的参数顺序构造。
那LinkedList里节点Node是什么结构呢？ LinkedList由一个头节点，一个尾节点和一个默认为0的size构成，可见其是双向链表。
数据结构中链表的头插法linkFirst和尾插法linkLast
2.3.3 LinkedList查询方法
按照下标获取某一个节点：get方法，获取第index个节点。
node(index)方法是怎么实现的呢？判断index是更靠近头部还是尾部，靠近哪段从哪段遍历获取值。
查询索引修改方法，先找到对应节点，将新的值替换掉老的值。
这个也是为什么ArrayList随机访问比LinkedList快的原因，LinkedList要遍历找到该位置才能进行修改，而ArrayList是内部数组操作会更快。
2.4.3 LinkedList修改方法
新增一个节点，可以看到是采用尾插法将新节点放入尾部。
和ArrayList一样，Vector也是List接口的一个实现类。其中List接口主要实现类有ArrayLIst，LinkedList，Vector，Stack，其中后两者用的特别少。
2.5.1 vector组成
和ArrayList基本一样。
2.5.2 vector线程安全性
vector是线程安全的，synchronized修饰的操作方法。
2.5.3 vector扩容
看源码可知，扩容当构造没有capacityIncrement时，一次扩容数组变成原来两倍，否则每次增加capacityIncrement。
2.5.4 vector方法经典示例
移除某一元素
这儿主要有一个两行代码需要注意，笔者在代码中有注释。数组移除某一元素并且移动后，一定要将原来末尾设为null，且有效长度减1。总体上vector实现是比较简单粗暴的，也很少用到，随便看看即可。
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）。
上边代码可以看到，最后push入栈的字符串"ccc"也最先出栈。
2.6.3 Stack源码
从Stack的源码中可见，其用的push方法用的是Vector的addElement（E e）方法，该方法是将元素放在集合的尾部，而其pop方法使用的是Vector的removeElementAt(Index x)方法，移除并获取集合的尾部元素，可见Stack的操作就是基于线性表的尾部进行操作的。
正如数据结构中描述，queue是一种先进先出的数据结构，也就是first in first out。可以将queue看作一个只可以从某一段放元素进去的一个容器，取元素只能从另一端取，整个机制如下图所示，不过需要注意的是，队列并没有规定是从哪一端插入，从哪一段取出。
Deque英文全称是Double ended queue，也就是俗称的双端队列。就是说对于这个队列容器，既可以从头部插入也可以从尾部插入，既可以从头部获取，也可以从尾部获取，其机制如下图所示。
3.1.1 Java中的Queue接口
此处需要注意，Java中的队列明确有从尾部插入，头部取出，所以Java中queue的实现都是从头部取出。
Java queue常常使用的方法如表格所示，对于表格中接口和表格中没有的接口方法区别为：队列的操作不会因为队列为空抛出异常，而集合的操作是队列为空抛出异常。
3.1.2 Deque接口
和Queue中的方法一样，方法名多了First或者Last，First结尾的方法即从头部进行操作，Last即从尾部进行操作。
3.1.3 Queue，Deque的实现类
Java中关于Queue的实现主要用的是双端队列，毕竟操作更加方便自由，Queue的实现有PriorityQueue，Deque在java.util中主要有ArrayDeque和LinkedList两个实现类，两者一个是基于数组的实现，一个是基于链表的实现。在之前LinkedList文章中也提到过其是一个双向链表，在此基础之上实现了Deque接口。
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：
上述代码做的事为往队列中放入10个int值，然后使用Queue的poll()方法依次取出，最后结果为每次取出来都是队列中最小的值，说明 了PriorityQueue内部确实是有一定顺序规则的。
案例2：
上述代码重写了compareTo方法都返回0，即不做优先级排序。发现我们返回的顺序为Test{a=20}->Test{a=15}->Test{a=12}->Test{a=10}->Test{a=13}->Test{a=11}->Test{a=9}->Test{a=8}->Test{a=21}->Test{a=14}，和放入的顺序还是不同，所以这儿需要注意在实现Comparable接口的时候一定要按照一定的规则进行优先级排序，关于为什么取出来的顺序和放入的顺序不一致后边将从源码来分析。
3.2.3 PriorityQueue组成
可以看到PriorityQueue的组成很简单，主要记住一个存放元素的数组，和一个Comparator比较器即可。
3.2.4 PriorityQueue操作方法
offer方法
首先可以看到当Queue中为空的时候，第一次放入的元素直接放在了数组的第一位，那么上边案例二中第一个放入的20就在数组的第一位。而当queue中不为空时，又使用siftUp(i, e)方法，传入的参数是队列中已有元素数量和即将要放入的新元素，现在就来看下究竟siftUp(i, e)做了什么事。
还记得上边提到PriorityQueue的组成，是一个存放元素的数组，和一个Comparator比较器。这儿是指当没有Comparator是使用元素类实现compareTo方法进行比较。其含义为优先使用自定义的比较规则Comparator，否则使用元素所在类实现的Comparable接口方法。
可以看到，当PriorityQueue不为空时插入一个新元素，会对其新元素进行堆排序处理（对于堆排序此处不做描述），这样每次进来都会对该元素进行堆排序运算，这样也就保证了Queue中第一个元素永远是最小的（默认规则排序）。
pool方法
此处可知，当取出一个值进行了siftDown操作，传入的参数为索引0和队列中的最后一个元素。
当没有Comparator比较器是采用的siftDown方法如上，因为索引0位置取出了，找索引0的子节点比它小的作为新的父节点并在循环内递归。PriorityQueue是不是很简单呢，其他细节就不再详解，待诸君深入。
ArrayDeque是Java中基于数组实现的双端队列，在Java中Deque的实现有LinkedList和ArrayDeque，正如它两的名字就标志了它们的不同，LinkedList是基于双向链表实现的，而ArrayDeque是基于数组实现的。
3.3.1 ArrayDeque的继承关系
可见ArrayDeque是Deque接口的实现，和LinkedList不同的是，LinkedList既是List接口也是Deque接口的实现。
3.3.2 ArrayDeque使用
案列
案例二：
上述程序最后得到队列中排列结果为ccc,aaa,bbb,ddd所以循环使用pollLast(),结果ddd,bbb,aaa,ccc，图示案列二的插入逻辑如下：
3.3.4 ArrayDeque内部组成
3.3.5 数组elements长度
此处elements数组的长度永远是2的幂次方，此处的实现方法和hashMap中基本一样，即保证长度的二进制全部由1组成，然后再加1，则变成了100…，故一定是2的幂次方。
3.3.6 ArrayDeque实现机制
如下图所示：
此处应将数组视作首尾相连的，最初头部和尾部索引都是0，addLast方向往右，addFirst方向往左，所以数组中间可能是空的，当头指针和尾指针相遇的时候对数组进行扩容，并对元素位置进行调整。 源码：
注意下边这行代码，表示当head-1大于等于0时，head=head-1，否则head=elements.length - 1。
换一种写法就是下边这样，是不是就是上边addFirst的指针移动方向？
这个就是位运算的神奇操作了，因为任何数与大于它的一个全是二进制1做&运算时等于它自身，如1010&1111 = 1010，此处不赘述。 再看addLast方法：
同样的注意有一串神奇代码。
该表达式等于,是不是很神奇的写法，其原理是一个二进制数全部由1组成和一个大于它的数做&运算结果为0，如。poll方法和add方法逻辑是相反的，此处就不再赘述，诸君共求之！
如果说List对集合加了有序性的化，那么Set就是对集合加上了唯一性。
java中的Set接口和Colletion是完全一样的定义。
Java中的HashSet如其名字所示，其是一种Hash实现的集合，使用的底层结构是HashMap。
4.2.1 HashSet继承关系
4.2.2 HashSet源码
可以看到HashSet内部其实是一个HashMap。
4.2.3 HashSet是如何保证不重复的呢？
可见HashSet的add方法，插入的值会作为HashMap的key，所以是HashMap保证了不重复。map的put方法新增一个原来不存在的值会返回null，如果原来存在的话会返回原来存在的值。关于HashMap是如何实现的，见后续！
LinkedHashSet用的也比较少，其也是基于Set的实现。
4.3.1 LinkedHashSet继承关系
和HashSet一样，其也是Set接口的实现类，并且是HashSet的子类。
4.3.2 LinkedHashSet源码
其操作方法和HashSet完全一样，那么二者区别是什么呢？1.首先LinkedHashSet是HashSet的子类.2.LinkedHashSet中用于存储值的实现LinkedHashMap，而HashSet使用的是HashMap。LinkedHashSet中调用的父类构造器，可以看到其实列是一个LinkedHashMap。
LinkedHashSet的实现很简单，更深入的了解需要去看LinkedHashMap的实现，对LinkedHashMap的解析将单独提出。 
Map是一种键值对的结构，就是常说的Key-Value结构，一个Map就是很多这样K-V键值对组成的，一个K-V结构我们将其称作Entry，在Java里，Map是用的非常多的一种数据结构。上图展示了Map家族最基础的一个结构（只是指java.util中）。整理了2021年Java面试题。
Map接口本身就是一个顶层接口，由一堆Map自身接口方法和一个Entry接口组成，Entry接口定义了主要是关于Key-Value自身的一些操作，Map接口定义的是一些属性和关于属性查找修改的一些接口方法。
HashMap是Java中最常用K-V容器，采用了哈希的方式进行实现，HashMap中存储的是一个又一个Key-Value的键值对，我们将其称作Entry，HashMap对Entry进行了扩展（称作Node），使其成为链表或者树的结构使其存储在HashMap的容器里（是一个数组）。
5.2.1 HashMap继承关系
5.2.2 HashMap存储的数据
Map接口中有一个Entry接口，在HashMap中对其进行了实现，Entry的实现是HashMap存放的数据的类型。其中Entry在HashMap的实现是Node，Node是一个单链表的结构，TreeNode是其子类，是一个红黑树的类型，其继承结构图如下：
HashMap存放数据的数据是什么呢？代码中存放数据的容器如下：
说明了该容器中是一个又一个node组成，而node有三种实现，所以hashMap中存放的node的形式既可以是Node也可以是TreeNode。
5.2.3 HashMap的组成
有了上边的概念之后来看一下HashMap里有哪些组成吧！
这儿要说两个概念，table是指的存放数据的数组，bin是指的table中某一个位置的node，一个node可以理解成一批/一盒数据。
5.2.4 HashMap中的构造函数*
tableSizeFor()方法保证了数组大小一定是是2的幂次方,是如何实现的呢？
该方法将一个二进制数第一位1后边的数字全部变成1，然后再加1，这样这个二进制数就一定是100…这样的形式。此处实现在ArrayDeque的实现中也用到了类似的方法来保证数组长度一定是2的幂次方。
5.2.5 put方法
开发人员使用的put方法：
真正HashMap内部使用的put值的方法：
5.2.6 查找方法
和HashMap不同，HashTable的实现方式完全不同，这点从二者的类继承关系就可以看出端倪来，HashTable和HashMap虽然都实现了Map接口，但是HashTable继承了DIctionary抽象类，而HashMap继承了AbstractMap抽象类。
5.3.1 HashTable的类继承关系图
HashTable
HashMap
5.3.2 Dictionary接口
Dictionary类中有这样一行注释，当key为null时会抛出空指针NullPointerException,这也说明了HashTabel是不允许Key为null的。
5.3.3 HashTable组成
HashTable中的元素存在Entry[] table中，是一个Entry数组，Entry是存放的节点，每一个Entry是一个链表。
5.3.4 HashTable中的Entry
知道Entry是一个单链表即可，和HashMap中的Node结构相同，但是HashMap中还有Node的子类TreeNode。
5.3.5 put方法
本质上就是先hash求索引，遍历该索引Entry链表，如果找到hash值和key都和put的key一样的时候就替换旧值，否则使用addEntry方法添加新值进入table，因为添加新元素就涉及到修改元素大小，还可能需要扩容等，具体看下边的addEntry方法可知。
这行代码是真正插入新元素的方法，采用头插法，单链表一般都用头插法（快）。
5.3.6 get方法
get方法就简单很多就是hash，找到索引，遍历链表找到对应的value，没有则返回null。相比诸君都已经看到，HashTable中方法是用synchronized修饰的，所以其操作是线程安全的，但是效率会受影响。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/3099.html