之前以为面经只是死记硬背的东西，后来发现记住了它们，对自己对知识的理解确实有帮助，难怪语文的文章老是要求背背背。

前言

这次的面经整理分为以下几个部分，希望对大家的工作有帮助。

目录：

• 前言
• 1 Java 集合概论
• 2 如何选用集合
• 3 扩容机制
• • 3.1 ArrayList 的扩容机制
  • 3.2 LinkedList 的扩容机制
  • 3.3 HashMap 的扩容机制
• 4 HashMap 的相关问题？
• • 4.1 HashMap 的底层实现
  • 4.2 为什么要改成“数组+链表+红黑树”
  • 4.3 面试回答
• 5 HashSet 的相关问题
• • 5.1 HashSet 的底层实现
  • 5.2 HashSet 如何检查重复
• 6 ConcurrentHashMap 的相关问题
• • 6.1 ConcurrentHashMap 的底层具体实现
  • 6.2 面试回答
• 7 相似集合的异同
• • 7.1 ArrayList 和 LinkedList 的异同
  • 7.2 ArrayList 和 Vector 的异同
  • 7.3 HashMap 和 Hashtable 的异同
  • 7.4 HashMap 和 ConcurrentHashMap 的异同
  • 7.5 ConcurrentHashMap 和 Hashtable 的异同
  • 7.6 HashMap 和 HashSet 的异同
  • 7.7 TreeSet 和 HashSet 的异同

1 Java 集合概论

数组（Array）和集合都是对多个数据进行存储操作的结构，也简称为 Java 容器。此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储（文件或数据库)。

然而目前数组（Array）在存储数据方面存在以下特点：

1. 数组初始化以后，长度就不可变了，不便于扩展；
2. 数组声明的类型，就决定了进行元素初始化时的类型；
3. 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，同时无法直接获取存储元素的个数；
4. 数组存储的数据是有序的、可以重复的。 存储数据的特点单一；

当然，上述有些特点也可以被当作优点，然而在实际操作中，由于数组的不够灵活，所以我们需要其它的方式来存储数据，Java 集合类就这样应运而生了。

Java 集合类中有可以用于存储数量不确定的多个对象的集合（Collection 接口），还有可用于保存具有映射关系的关联数组的集合（Map 接口）。

• Collection 接口：单列数据，用于存储数量不确定的多个对象 ；

  • List接口：元素有序、可重复的集合（对应“动态”数组），即集合中的每个元素都有其对应的顺序索引，可以根据序号存取容器中的元素。
    • ArrayList 实现类：作为 List 接口的主要实现类，它是线程不安全的，但效率高；适⽤于频繁的查找⼯作。
    • LinkedList 实现类：使用 LinkedList 实现类对于频繁的插入、删除操作的效率比 ArrayList 高；
    • Vector 实现类：作为 List 接口的古老实现类，它是线程安全的，但效率低；
  • Set 接口：元素无序、不可重复的集合（对应高中讲的“集合”）
    • HashSet 实现类：作为 Set 接口的主要实现类，是线程不安全的；可以存储 null 值。
      • LinkedHashSet 实现类：是 HashSet 的子类。遍历其内部数据时，可以按照添加的顺序遍历，使其看起来是有序的。
    • TreeSet 实现类：底层使⽤红⿊树，TreeSet可以确保集合元素处于排序状态；排序方法分为自然排序和定制排序，自然排序指的是根据自然规律排序，比如数字的话就按照从小到大排序，定制排序指的是根据自己既定的规则进行排序。

• Map 接口：双列数据，保存具有映射关系 “key-value对” 的集合

  • HashMap 实现类：作为Map的主要实现类，它是线程不安全的，但效率高。可以存储 null 值的 key 和 value。
    • LinkedHashMap 实现类：保证在遍历 map 元素时，可以按照添加的顺序实现遍历。
  • ConcurrentHashMap 实现类：线程安全的 Map；
  • TreeMap 实现类：底层使用红黑树，保证按照添加的 key-value 对进行排序，实现排序遍历。
  • Hashtable 实现类：古老的实现类，它是线程安全的，但效率低；不能存储 null 的 key 和 value。
    • Properties 实现类：常用来处理配置文件，key 和 value 都是 String 类型。

Java中的 List、Set、Map 之类的集合容器中只能存放引用类型，而不能存放类似于 int、double 之类的基本类型。

参考文献：【传送门】

2 如何选用集合

如果我们需要根据键值获取元素值就选用 Map 接口下的集合，当需要排序时就选择 TreeMap，不需要排序时就选择 HashMap，需要保证线程安全就选用 ConcurrentHashMap；

如果我们只需要存放元素时，就选择实现 Collection 接口的集合，此时如果需要保证元素唯一就选择实现 Set 接口的集合，如 TreeSet 或者 HashSet，此时如果需要排序就只选择 TreeSet；

当确定选择实现 Collection 接口的集合后，如果不需要保证元素唯一，就选择实现 List 接⼝的 ArrayList 或 LinkedList 等集合，此时如果需要线程安全的话，就只能选择 Vector，当不需要保证线程安全时，该集合需要频繁的删除和插入，就选择 LinkedList，需要频繁的查找就选择 ArrayList；

3 扩容机制

3.1 ArrayList 的扩容机制

ArrayList 底层的数据结构是动态数组，其扩容情况可以分为两种情况：

第一种情况，当 ArrayList 的容量为 0 时，此时添加元素的话，需要扩容，三种构造方法创建的 ArrayList 在扩容时略有不同：

1. 无参构造，创建 ArrayList 后容量为 0，添加第一个元素后，容量变为 10，此后若需要扩容，则按照 1.5 倍进行扩容；
2. 当传容量，参数为 0 或者传列表，列表为空构造时，创建 ArrayList 后容量为 0，添加第一个元素后，容量为 1，此时 ArrayList 是满的，下次添加元素时则按照 1.5 倍进行扩容；

第二种情况，当 ArrayList 的容量大于 0，并且 ArrayList 是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的 1.5 倍。

ArrayList 没有缩容。无论是remove方法还是clear方法，它们都不会改变现有数组elementData的长度。但是它们都会把相应位置的元素设置为null，以便垃圾收集器回收掉不使用的元素，节省内存。

3.2 LinkedList 的扩容机制

LinkedList 的底层是双向链表，所以不需要主动扩容。ArrayList 的底层是动态数组，所以当数组的内存不足时，需要主动扩容。

3.3 HashMap 的扩容机制

HashMap 的扩容机制分为两种情况：

第一种情况，无参构造时，HashMap 的默认初始容量是16，之后每次扩充，容量变为原来的 2 倍；

第二种情况，有参构造时，HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的 2 的 N 次方，例如传 9，容量为16。之后每次扩充，容量变为原来的 2 倍。

为什么HashMap 的容量大小永远是 2 的 N 次方呢？

**为了能让 HashMap 存取⾼效，尽量减少哈希碰撞，也就是要尽量把数据分配均匀。**我们上⾯也讲过了，Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得⽐较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。

我们⾸先可能会想到采⽤ % 取余的操作来实现。但是，重点来了：“如果除数是2的幂次，那么取余(%)操作则等价于与其被除数减⼀的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次⽅；）。” 并且 采⽤⼆进制位操作 &，相对于 % 能够提⾼运算效率，这就解释了 HashMap 的⻓度为什么是 2 的幂次⽅。

4 HashMap 的相关问题？

4.1 HashMap 的底层实现

JDK1.8 之前：

此时 HashMap 的底层实现是数组+链表的形式，HashMap 通过 key 的 hashCode() 经过扰动函数处理过后得到 hash 值，然后利用公式（(n - 1) & hash）判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash 值以及 key 值是否相同，如果均相同则直接覆盖，如果值不同，则通过拉链法来解决哈希冲突。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8 及之后：

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

对于移除，当同一个索引位置的节点在移除后小于 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。

4.2 为什么要改成“数组+链表+红黑树”

主要是为了提升在 hash 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)（线性级），而使用红黑树是 O(logn)（对数级）。

4.3 面试回答

请问 HashMap 的底层实现是怎么样的？

在 JDK1.8 之前的话，HashMap 的底层是通过数组+链表的形式来实现的，在 JDK1.8 及之后的话，则是通过数组+链表/红黑树的形式来实现，这两者的区别在于，当哈希冲突严重时，后者会将链表转换成红黑树来存储，从而提升查找性能。

2 什么是哈希冲突

因为 HashMap 在存储数据时是根据键的哈希值所对应的位置来存放的，然后可能存在键不同，对应的位置相同的情况，这种情况便是哈希冲突，在实际中，常采用拉链法来解决，拉链法指的是将链表和数组相结合，数组中每⼀格就是⼀个链表，若遇到哈希冲突，则将冲突的值加到链表后即可。

3 什么是红黑树，红黑树如何进行自调整，与哈希表的区别

红黑树是一种可以自平衡的二叉查找树。（两头乌，路径上不能有两个连续的红色节点）

红黑树通过变色、左旋转和右旋转来保持平衡。

与哈希表的区别：

1. 在增改查性能上，红黑树的性能是稳定且高效的，而哈希表当哈希碰撞严重时，时间复杂度会达到线性级；
2. 红黑树是有序的，哈希表是无序的；
3. 相对来说，红黑树占用的内存更小。

5 HashSet 的相关问题

5.1 HashSet 的底层实现

HashSet 的底层实际上是通过 HashMap 来实现的，除了实现 Set 接口所规范的方法外，其它方法都是直接调用 HashMap，HashSet 将对应元素存放在 HashMap 的键上，与此相对应的值存放了一个静态的 final 修饰的 Object 对象。

5.2 HashSet 如何检查重复

当把对象加入到 HashSet 中时，HashSet 会比较该对象的哈希值是否和 HashSet 中已经存在的对象的哈希值相等，如果不相等则直接加入；如果相等，则调用 equals() 方法来检查这两个哈希值相等的对象是否真的相同，如果两者相同，HashSet 就不会让其加⼊操作成功。

6 ConcurrentHashMap 的相关问题

6.1 ConcurrentHashMap 的底层具体实现

JDK1.8 之前：

⾸先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程占⽤锁访问其中⼀个段数据时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组 + HashEntry 数组 + 链表组成。

⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数组，Segment 每一格包含着一个 HashEntry 数组， HashEntry 数组的每一格则包含一条链表，每个 Segment 元素守护着 HashEntry 数组⾥的元素，当对 HashEntry 数组的数据进⾏修改时，必须⾸先获得对应的 Segment 的锁。

JDK1.8 之后：

ConcurrentHashMap 取消了 Segment 分段锁，采⽤ CAS（Compare And Swap，比较并交换） 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。在链表⻓度超过⼀定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红⿊树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑树的首节点，这样只要 hash 不冲突，就不会产生并发，效率⼜提升 N 倍。

6.2 面试回答

1 ConcurrentHashMap 相对于 HashMap 做了哪些优化

ConcurrentHashMap 相对于 HashMap 是线程安全的，它采用了分段锁的形式来保证了线程安全；

JDK1.8 之前的话，它是由 Segment 数组 + HashEntry 数组 + 链表组成的，其中 Segment 数组的每一格包含着一个 HashEntry 数组， HashEntry 数组的每一格则包含一条链表，当对链表中的数据进行修改时，必须首先获得对应的 Segment 的锁。

在 JDK1.8 及之后，取消了 Segment 分段锁，采用 CAS 和同步的方式来保证并发安全。数据结构跟 HashMap 类似，也是采用数组+链表/红黑树，同时同步关键字只锁定当前链表或红黑树的首节点，这样只要 hash 不冲突，就不会产生并发。

7 相似集合的异同

7.1 ArrayList 和 LinkedList 的异同

1. 底层数据结构： Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是双向链表；

2. 线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

3. 是否支持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)；

4. 插入和删除是否受元素位置的影响： ① ArrayList 采⽤数组存储，所以插⼊和删除元素的时间复杂度受元素位置的影响。 ⽐如：执⾏ add(E e) ⽅法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插⼊和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进⾏上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执⾏向后位/向前移⼀位的操作。 ② LinkedList 采⽤链表存储，如果是要在指定位置 i 插⼊和删除元素的话（ (add(int index, E element) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊；（总的来说，查找遍历用 ArrayList，增加删除用 LinkedList）

5. 内存空间占用： ArrayList 的空间浪费主要体现在在列表的结尾会预留⼀定的容量空间（因为扩容时数组的大小不太可能是刚刚好的），⽽ LinkedList 的空间花费则体现在它的每⼀个元素都比 ArrayList 需要更多的空间（因为要存放前驱、后继以及数据）。

7.2 ArrayList 和 Vector 的异同

• ArrayList 是 List 的主要实现类，底层使⽤ Object[ ] 存储，线程不安全 ；
• Vector 是 List 的古老实现类，底层使⽤ Object[ ] 存储，线程安全的，因此效率低；

线程安全是多线程编程时的计算机程序代码中的一个概念，在拥有共享数据的多条线程并行执行的程序中，线程安全的代码会通过同步机制保证各个线程都可以正常且正确的执行，不会出现数据污染等意外情况。

线程的安全是以牺牲效率为代价的，所谓线程安全就是多了个加锁、解锁的操作，比如100亿个操作中都要加锁和解锁，线程是安全了，但效率就下降了。而有些软件是以效率为主的，为了提高效率，就少了加锁，解锁的操作，虽然容易出现并发访问问题，但效率却提高了。

7.3 HashMap 和 Hashtable 的异同

1. 线程是否安全： HashMap 是非线程安全的， HashTable 是线程安全的，因为 HashTable 内部的⽅法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使⽤ ConcurrentHashMap 吧！）；
2. 效率： 因为线程安全的问题， HashMap 要比 HashTable 效率高⼀点；
3. 对 Null key 和 Null value 的⽀持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有⼀个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException；
4. 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值， Hashtable 默认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1；HashMap 默认的初始化⼤⼩为 16，之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为 2 的幂次⽅⼤⼩，也就是说 HashMap 总是使⽤ 2 的幂作为哈希表的⼤⼩；
5. 底层数据结构： JDK1.8 之前 HashMap 使用的是数组和链表结合在一起的链表散列，JDK1.8 及之后使用的是 数组+链表+红黑树的方式；Hashtable 底层是数组+链表；

7.4 HashMap 和 ConcurrentHashMap 的异同

• HashMap 是线程不安全的，但速度快；
• ConcurrentHashMap 是线程安全的，但其并不是像 Hashtable 一样给每一个方法都加上同步修饰（整体锁），而且使用的是分段锁，因此如果需要保证线程安全，就使用这个 Map；
• Hashtable 是线程安全的，但效率实在太低，目前已基本被淘汰。

7.5 ConcurrentHashMap 和 Hashtable 的异同

1. 实现线程安全的方式：① 在 JDK1.7 的时候，ConcurrentHashMap 将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程问其中⼀个段数据时，其他段的数据也能被其他线程访问，即分段锁。到 JDK1.8 的时候，ConcurrentHashMap 取消了Segment 分段锁，采⽤ CAS 和 synchronized 来保证并发安全。② Hashtable 使⽤ synchronized 修饰所有方法来保证线程安全，效率十分低下，当一个线程访问同步方法时，其它线程也访问同步方法时便会进入阻塞或者轮询状态，即全表锁；
2. 底层数据结构：JDK1.7 的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8 采⽤的数据结构跟 HashMap 的结构⼀样的数组+链表/红⿊⼆叉树。Hashtable 底层是用数组+链表来实现的。

7.6 HashMap 和 HashSet 的异同

HashSet 的底层是基于 HashMap 来实现的，除了实现 Set 接口所必须实现的方法外，其它方法都是直接调用 HashMap 的方法。

HashSet 不能有重复的元素，HashMap 不允许有重复的键。HashSet 中的值实际上就是放在了 HashMap 中的 key 中，此时在 HashMap 的 value 则存储了一个 PRESENT，它是一个static final 的 Object 对象。

7.7 TreeSet 和 HashSet 的异同

HashSet 和 TreeSet 都是用来存放唯一元素的集合，只不过 TreeSet 可以确保集合元素处于排序状态；排序方法分为自然排序和定制排序。