以下所有整理内容都是我从第一次面试开始，将所有遇到的问题整合后的结果。所有的内容都是我在面试中真实遇到的问题，有bat这样的大厂，也有很多小厂。在面试超过20家之后，遇到的绝大多数问题都开始重复，这份资料给我的面试带来了非常多的便利。现在我将这份资料分享在这里，希望也能够给你带来一些帮助，加油吧少年！

---

JDK 提供了一组主要的数据结构实现，如List、Map、Set 等常用数据结构。这些数据都继承自java.util.Collection 接口，并 位于java.util 包内。

1. 常见的集合有哪些

Map接口和Collection接口是所有集合框架的父接口

（1）Collection接口的子接口包括Set接口和List接口还有Queue接口

（2）Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties

（3）Set接口的实现类主要有：HashSet、TreeSet（上面有个SortedSet）、LinkedHashSet等

（4）List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

（5）Queue接口的实现类主要有：LinkedList、PriorityQueue

1. List接口

最重要的三种List接口实现：ArrayList、Vector、LinkedList

三种List均来自AbstractList的实现，而AbstractList直接实现了List接口，并扩展自AbstractCollection

ArrayList和Vector 使用了数组实现，可以认为，ArrayList 封装了对内部数组的操作。比如向数组中添加、删除、插入新的元 素或数组的扩展和重定义。对ArrayList 或者 Vector 的操作，等价于对内部对象数组的操作。

**ArrayList和Vector 几乎使用了相同的算法，它们的唯一区别可以认为是对多线程的支持。**ArrayList没有对一个方法做线程同 步，因此不是线程安全的。Vector 中绝大多数方法都做了线程同步，是一种线程安全的实现。因此ArrayList和 Vector 的性能 特性相差无几。

LinkedList使用了循环双向链表数据结构。LinkedList由一系列表项连接而成。一个表项总是包含 3个部分：元素内容、前驱 表项和后驱表项。

无论LinkedList是否为空，链表都有一个header表项，它既是链表的开始，也表示链表的结尾。它的后驱表项便是链表的第一个元素，前驱表项便是链表的最后一个元素。如图：

2. ArrayList和LinkedList的不同

2.1 增加元素到列表尾端

对于ArrayList来说，只要当前容量足够大，add()操作的效率是非常高的。

只有当ArrayList 对容量的需求超过当前数组的大小时，才需要进行扩容。扩容会进行大量的数组复制操作。而复制时最终调用 的是System.arraycopy()方法，因此，add()效率还是相当高的。

LinkedList由于使用了链表的结构，因此不需要维护容量的大小。这点比ArrayList有优势，不过，由于每次元素增加都需要新 建Node 对象，并进行更多的赋值操作。在频繁的系统调用中，对性能会产生一定影响。

2.2 插入元素到列表任意位置

ArrayList是基于数组实现的，而数组是一块连续的内存空间，每次插入操作，都会进行一次数组复制。大量的数组复制会导致系统性能低下。

LinkedList是基于链表实现的，在任意位置插入和在尾端增加是一样的。所以，如果系统应用需要对 List 对象在任意位置进行 频繁的插入操作，可以考虑用LinkedList替代 ArrayList。

2.3 删除任意位置元素

对ArrayList 来说，每次remove()移除元素都需要进行数组重组。并且元素位置越靠前开销越大，要删除的元素越靠后，开销越小。

在LinkedList的实现中，首先需要通过循环找到要删除的元素。如果要删除的元素位置处于 List的前半段，则从前往后找；若 处于后半段，则从后往前找。如果要移除中间位置的元素，则需要遍历完半个List，效率很低。

2.4 容量参数

容量参数是ArrayList 和 Vector 等基于数组的List 的特有性能参数，它表示初始数组的大小。默认ArrayList的数组初始大小为 10。

合理的设置容量参数，可以减少数组扩容，提升系统性能。

2.5 遍历数组

常用的三种列表遍历方式：ForEach操作、迭代器和for 循环。

对于ForEach 操作，反编译可知实际上是将ForEach 循环体作为迭代器处理。不过ForEach 比自定义的迭代器多了一步赋值操 作，性能不如直接使用迭代器的方式。

使用For 循环通过随机访问遍历列表，ArrayList 表现很好，速度最快；但是LinkedList 的表现非常差，因为 对LinkedList的随机访问时，总会进行一次列表的遍历操作。

3. Map接口

最主要的实现有Hashtable，HashMap，LinkedHashMap和TreeMap与CurrentHashMap，在Hashtable中，还有Properties类的实现

3.1 Hashtable和HashMap的区别

（1） Hashtable 的大部分方法都做了线程同步，而HashMap 没有，因此，Hashtable 是线程 安全的，HashMap 不是。

（2）Hashtable 不允许 key 或value 使用null 值，而HashMap 可以。

（3）它们在内部对key 的hash算法和hash 值到内存索引的映射算法不同。 由于HashMap 使用更广泛

（4）HashMap集成自AbstractMap，而Hashtable集成自Dictionary类

3.2 HashMap的实现原理

jdk1.7以前是数组加链表，jdk1.8如果链表长度到达阀值(默认是8)，就会将链表转换成红黑二叉树。

简单来说，HashMap 就是将 key 做 hash 算法，然后将 hash 值映射到内存地址，直接取得key 所对应的数据。在HashMap 中，底层数据结构使用的是数组。所谓的内存地址，就是数组的下标索引。

代码表示：Object[key_hash] = value

3.3 Hash冲突

当需要存放的两个元素1 和2 经 hash 计算后，发现对应在内存中的同一个地址。此时 HashMap 又会如何处理以保证数据的 完整存放？

**在HashMap 的底层使用数组，但数组内的元素不是简单的值，而是一个Entity 类的对象。**每一个 Entity 表项包括key，value， next，hash几项。注意这里的 next部分，它指向另外一个 Entity。

当put()操作有冲突时，新的Entity 会替换原有的值，为了保证旧值不丢失，会将 next 指向旧值。这便实现了在一个数组空间 内存放多个值项。因此，HashMap 实际上是一个链表的数组。

而在进行get()操作时，如果定位到的数组元素不含链表（当前 entry 的 next 指向null），则直接返回；如果定位到的数组元 素包含链表，则需要遍历链表，通过key 对象的equals 方法逐一比对查找。

3.4 容量参数

和ArrayList 一样，基于数组的结构，不可避免的需要在数组空间不足时，进行扩展。而数组的重组比较耗时，因此对其做一定 的优化很有必要了。

HashMap 提供了两个可以指定初始化大小的构造函数：

// 构造一个带指定初始容量和默认负载因子（0.75）的空HashMap HashMap(int initialCapacity) // 构造一个带指定初始容量和负载因子的空HashMap HashMap(int initialCapacity, float loadFactor)

其中，HashMap 会使用大于等于initialCapacity 并且是 2的指数次幂的最小的整数作为内置数组的大小。

负载因子又叫做填充比，它是介于0和1之间的浮点数。

负载因子 = 实际元素个数 / 内部数组总大小

负载因子的作用就是决定HashMap 的阈值（threshold）。

阈值 = 数组总容量 × 负载因子

当HashMap 的实际容量超过阈值便会进行扩容，每次扩容将新的数组大小设置为原大小的 1.5 倍。

默认情况下，HashMap 的初始大小是 16，负载因子为 0.75

3.5 LinkedHashMap

LinkedHashMap 继承自HashMap，因此，它具备了 HashMap 的优良特性，并在此基础上，LinkedHashMap 又在内部增加 了一个链表，用以存放元素的顺序。因此，LinkedHashMap 可以简单理解为一个维护了元素次序表的 HashMap.

LinkedHashMap 提供两种类型的顺序：一是元素插入时的顺序；二是最近访问的顺序。

// 构造一个带指定初始容量、负载因子和排序模式的空LinkedHashMap实例 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

其中accessOrder 为true时，按照元素最后访问时间排序；当 accessOrder 为false 时，按照插入顺序排序。默认为 false 。

在内部实现中，LinkedHashMap 通过继承 HashMap.Entity 类，实现LinkedHashMap.Entity，为 HashMap.Entity 增加了 before 和after 属性用以记录某一表项的前驱和后继，并构成循环链表。

3.6 TreeMap

TreeMap 可以简单理解为一种可以进行排序的Map 实现。与 LinkedHashMap 不同，LinkedHashMap 是根据元素增加或者 访问的先后顺序进行排序，而TreeMap 则根据元素的Key 进行排序。为了确定Key 的排序算法，可以使用两种方式指定：

（1）在 TreeMap 的构造函数中注入一个 Comparator：

TreeMap(Comparator<? super K> comparator)

（2）使用一个实现了 Comparable 接口的 Key

**TreeMap的内部实现是基于红黑树的。**红黑树是一种平衡查找树

注入Comparator代码以及TreeMap其他排序接口

// 返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括） subMap(K fromKey, K toKey) // 返回此映射的部分视图，其键大于等于 fromKey。 tailMap(K fromKey) // 返回此映射中当前第一个（最低）键。 firstKey() // 返回此映射的部分视图，其键值严格小于 toKey headMap(K toKey)

3.7 HashMap的put方法具体流程

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; // 1如果table为空或者长度为0，即没有元素那么使用resize()方法扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2.计算插入存储的数组索引i，此处计算方法同1.7中的indexFor()方法 // 如果数组为空，即不存在Hash冲突，则直接插入数组 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 3.插入时，如果发生Hash冲突，则依次往下判断 else { HashMap.Node<K,V> e; K k; // a.判断table[i]的元素的key是否与需要插入的key一样，若相同则直接用新的value覆盖掉旧的value // 判断原则equals() - 所以需要当key的对象重写该方法 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // b.继续判断：需要插入的数据结构是红黑树还是链表 // 如果是红黑树，则直接在树中插入 or 更新键值对 else if (p instanceof HashMap.TreeNode) e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 如果是链表，则在链表中插入 or 更新键值对 else { // i .遍历table[i]，判断key是否已存在：采用equals对比当前遍历结点的key与需要插入数据的key // 如果存在相同的，则直接覆盖 // ii.遍历完毕后任务发现上述情况，则直接在链表尾部插入数据 // 插入完成后判断链表长度是否>8：若是，则把链表转换成红黑树 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash,key,value,null); // -1 for 1st if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 对于i 情况的后续操作：发现key已存在，直接用新value覆盖旧value&返回旧value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 插入成功后，判断实际存在的键值对数量size > 最大容量 // 如果大于则进行扩容 if (++size > threshold) resize(); // 插入成功时会调用的方法（默认实现为空） afterNodeInsertion(evict); return null; }

3. 8 CurrentHashMap（1.7对比1.8）

JDK1.7版本的ReentrantLock+Segment+HashEntryJDK1.8版本中synchronized+CAS+HashEntry+红黑树

具体对比：

数据结构：JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。取而代之的是数组+链表+红黑树的结构。保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

Segment(分段锁)-减少锁的粒度：ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

cas是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源

4. Set接口

Set并没有在 Collection接口之上增加额外的操作，Set 集合中的元素是不能重复的。

其中最为重要的是HashSet、LinkedHashSet、TreeSet 的实现。所有的这些Set实现都只是对对应的 Map 的一种封装而已。

5. 优化集合访问代码

5.1 分离循环中被重复调用的代码

for(int i = 0; i < collection.size(); i++){ //... } // 改进 int size = collection.size(); for(int i = 0; i < size; i++){ //... }

很明显，每次循环都会调用size()方法，并且每次都会返回相同的数值。分离所有类似的代码对提升循环性能有着积极地意义。

5.2 省略相同的操作

int size = collection.size(); for(int i = 0; i < size; i++){ if (list.get(i)==1||list.get(i)==2||list.get(i)==3){ // ,,, } } // 改进之后 int size = collection.size(); int k = 0; for(int i = 0; i < size; i++){ if (k = list.get(i) == 1 || k == 2 || k == 3){ // ,,, } }

虽然每次循环调用get(i)的返回值不同，但在同一次调用中，结果是相同的，因此可以提取这些相同的操作。

5.3 减少方法调用

方法调用是需要消耗系统堆栈的，如果可以，则尽量访问内部元素，而不要调用对应的接口，函数调用是需要消耗系统资源的， 直接访问元素会更高效。

假设上面的代码是Vector.class 的子类的部分代码，那么可以这么改写

int size = collection.size(); object k = 0; for(int i = 0; i < size; i++){ if (k = elementData[i] == "1" || k == "2" || k == "3"){ // ,,, } }

原本的 size() 和 get() 方法被直接替代为访问原始变量，这对系统性能的提升是非常有用的。

6. RandomAccess接口

RandomAccess接口是一个标志接口，本身并没有提供任何方法，任何实现 RandomAccess 接口的对象都可以认为是支持快 速随机访问的对象。+此接口的主要目的是标识那些可以支持快速随机访问的List 实现。

在JDK中，任何一个基于数组的 List实现都实现了 RandomAccess 接口，而基于链表的实现则没有。因为只有数组 能够快速随机访问，（比如：通过 object[5]，object[6]可以直接查找并返回对象），而对链表的随机访问需要进行链表的遍 历。

在实际操作中，可以根据 listinstanceof RandomAccess来判断对象是否实现 RandomAccess 接口，从而选择是使用随机访 问还是iterator 迭代器进行访问。

在应用程序中，如果需要通过索引下标对 List 做随机访问，尽量不要使用 LinkedList，可以选择ArrayList和Vector 。