集合是Java面试必考的高频知识点，虽然大家平时多少都会在用，但是对这个体系和底层实现很少有较全面的认知。

本文参考了《极客时间-Java核心技术36讲》和《牛客网-Java开发岗高频面试题全解析》，在较为系统的复习之后总结于此。希望对同样的正在准备找工作的同学有所帮助

关于Java中的集合类，你知道多少呢？

首先，放上一张整体分类图，从图中可以看出，Java的集合类起源于两个接口，一个是Map，另一个是Collection。平时我们所能接触到的包括HashMap，ArrayList，HashSet等都直接或间接的实现了这两个接口中的一个。而Collection接口的分支包括了List接口和Set接口。这样一来，我们常见的Map，List和Set就都包含到了。

说到集合肯定大家都知道Collection接口，但是不一定知道Map接口是和Collection接口平级的，所以Map接口不是Collection接口的子接口。

Java中常见的集合类有哪些呢？

下面我们就以Map、Set、List作为三个分支来进行讲解

• Map接口的实现类主要有：HashMap、TreeMap、LinkedHashMap、Hashtable、ConcurentHashMap和Properties等
• Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
• List接口的实现类主要有：ArrayList、LinkedList、Stack、Vector等

为了能更清楚的了解下他们之间的关系，我找了两张结构的图也放到这里

• Collection接口及其分支的结构

• Map接口及其分支的结构

常见考题

同一类下的各个实现类不但名字有点相似，功能也都大体一致，所以同一类型的实现类之间的比较就是面试的热点，下面，我们就把常用的分成几组进行比较吧

Hashtable、HashMap、TreeMap 有什么不同？（三个最相似）

1. Key值和Value值是否能为空

• Hashtable的Key和Value均不能为null
• HashMap的Key和Value允许为空，允许有一个null的Key和多个null的Value
• TreeMap的Value允许为空
  未实现 Comparator 接口时，key 不可以为null
  实现 Comparator 接口时，若未对 null 情况进行判断，不能为空；若针对null实现了，可以为空，但是不能通过get（）方法获取，只能遍历获得值。

2. 是否有序

• Hashtable和HashMap是无序的
• TreeMap是有序的，TreeMap由红黑树实现，默认是升序排列，可自定义实现Comparator接口实现排序方式

3. 初始化和增长方式

• Hashtable初始化默认容量为11，且不要求底层数组容量为2的整数次幂。
  扩容时容量变为原来的2倍加1
• HashMap初始化默认容量为16，要求容量一定为2的整数次幂
  扩容时容量变为原来的2倍
• TreeMap底层实现是红黑树，就不需要初始化默认大小和扩容了

4. 线程安全性

• Hashtable的方法函数全部都是同步的（synchronized实现），保证了线程安全性。当多线程访问Hashtable时，效率极低，所以Hashtable现在已经不推荐使用了
• HashMap和TreeMap不支持线程同步，所以是线程不安全的

举例说明HashMap是线程不安全的

• HashMap线程不安全主要是考虑到了多线程环境下进行扩容可能会出现HashMap死循环
• Hashtable的线程安全是由于内部实现put和remove操作时使用synchronized进行了同步，所以单个方法线程安全。而HashMap并没有，所以当一个线程执行remove操作时另一个线程执行get操作就可能出现越界现象

LinkedHashMap和TreeMap的区别（两个有序）

• LinkedHashMap基于HashMap和双向链表实现，TreeMap基于红黑树实现
• TreeMap的有序是指基于Key进行内部排序
• LinkedHashMap的有序分为插入顺序和访问顺序，默认插入顺序
  插入顺序：插入时是什么顺序，读取就是什么顺序
  访问顺序：访问了之后，访问的元素就放到最后面

ConcurrentHashMap和Hashtable的区别？（两个线程安全）

• Hashtable通过synchronized锁住整个结构实现线程同步，效率低
• ConcurrentHashMap采用分段锁实现线程同步，效率明显提高

关于ConcurrentHashMap你知道多少？

为什么需要ConcurrentHashMap？

Hashtable线程安全，但各种方法操作时都直接使用了synchronized锁住了整个结构
HashMap虽然效率高，但是在多线程环境下不安全
需要一个中和了Hashtable和HashMap的类在多线程下高效的使用

ConcurrentHashMap分析

ConcurrentHashMap设计实体一直在变化，这里就分两个阶段来说

• 早期ConcurrentHashMap，其实现是基于分离锁，将内部进行分段（Segment），里面则是HashEntry的数组，和HashMap类似，哈希相同的条目还是以链表形式存放，可参考其早起的结构示意图。其核心是利用分段设计，在进行并发操作时，只需要锁定响应段，这样就可以有效的避免类似Hashtable的整体锁定，大大的提升性能。
  在构造的时候，Segment由concurrentcyLevel所决定，默认值是16，因为Java需要的是2的整数幂值，如果不是，则向上取，如输入15则被自动调整到16
  在扩容的时候不是针对整体的扩容，而是针对Segment的单独的扩展
  
• Java 8及其之后的版本中，Segment不再有任何结构式的作用，仅仅是为了保证序列化时兼容，初始化操作大大简化，修改成了lazy-load形式，极大地避免了初始化开销。使用 CAS 操作，在特定场景进行无锁并发操作，同步的粒度要更细致。

关于HashMap你了解多少？

HashMap的底层实现结构是什么？

• JDK8之前，HashMap的底层实现数据结构为数组+链表形式
• JDK8及之后，HashMap的底层实现采用数组+链表+红黑树的形式，有效的解决了链表太长导致的查询速度变慢问题
  

HashMap 的初始容量，加载因子，扩容增量是多少？

• HashMap的初始容量是16
• HashMap的加载因子是0.75
• HashMap的扩容增量是1倍
  为什么初始容量是16而不是15：因为Java要求的是2的整数幂值
  加载因子0.75表达什么含义：表示当存储容量超过当前容量的0.75倍事触发扩容，如第一次扩容当超过16*0.75=12之后，就开始扩容
  扩容增量1倍表达什么含义：指每次扩容的容量是原来容量的一倍，即容量每次翻倍

HashMap的长度为什么是2的整数幂值？

2的N次幂有助于减少碰撞的几率，空间利用率大

对上面这句话做一个解释：

• 我们将一个键值对插入HashMap中，通过key的hash值与length-1进行&运算，实现了key定位。
• 当length为2的N次幂时，length-1的二进制为111…(全1）的形式，在于hash值进行&操作时会很快，而且没有空间浪费
• 当length不是2的N次幂时，如length=15，那么length-1=14，二进制值为1110，进行&操作时，0001、0011、0101、0111、1011、1001、1101这几个位置就不能存放值，空间浪费巨大！！！

HashMap的存储和获取原理

• 当调用put()方法传递键值对进行存储时，先对键调用hashCode()的方法，返回bucket的位置存储实体对象，当bucket位置发生冲突，也就是发生hash冲突时，会在每个bucket后面接上一个链表（JDK8及之后的版本如果冲突数超过MIN_TREEIFY_CAPACITY会使用红黑树）来解决，将新存储的键值对放在表头（bucket）中
• 当调用get()方法时，首先根据hashCode()获取到bucket的值，然后再通过equals方法在链表或者红黑树中查找

HashMap扩容的步骤

HashMap里面默认的负载因子大小为0.75，也就是说，当Map中的元素个数（包括数组，链表和红黑树中）超过了16*0.75=12之后开始扩容。将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

但是要注意，在多线程环境下，HashMap扩容会导致死循环

解决Hash冲突的方法有哪些？

• 开放定址法：当关键字key的hash地址p=hase(key)出现冲突时，以某种探测技术递归的寻找空白地址，直到找到返回。如：以p为基础再产生另一个hash地址p1，如果p1也冲突了就继续找直到找到
• 拉链法：所有hash地址相同的构成一个单链表，单链表的头指针放在hash表的第i个单元中。JDK8之前的HashMap就是使用的拉链法
• 线性补偿探测法：当发生冲突时，将线性探测的步长从 1 改为 Q ，将算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元

哪些类适合作为HashMap的键？

String和Integer这样的包装类非常适合作为HashMap的键。因为他们都是final类型的类，而且重写了equals和hashCode方法，避免了键值对改写，有效提高HashMap性能
hashCode 和 equals 的一些基本约定

• equals 相等，hashCode 一定要相等
• 重写了 hashCode 也要重写 equals
• hashCode 需要保持一致性，状态改变返回的哈希值仍然要一致

TreeMap相关的Comparable接口和Comparator接口有哪些区别呢？

• Comparable实现比较简单，但是当需要重新定义比较规则的时候，必须修改源代码，即修改User类里边的compareTo方法
• Comparator接口不需要修改源代码，只需要在创建TreeMap的时候重新传入一个具有指定规则的比较器即可

Vector、ArrayList和LinkedList有哪些区别？

底层实现

Vector和ArrayList底层使用动态数组实现
LinkedList底层使用双向链表实现，可当做堆栈、队列、双端队列使用

线程安全性

• Vector是线程安全的，效率较低，已经不推荐使用了，多线程环境下现在推荐使用CopyOnWriteArrayList替代ArrayList
• ArrayList和LinkedList是线程不安全的

扩容增量

Vector和ArrayList当数组满的时候，会自动创建扩容后的数组，并拷贝原有数组数据

• Vector扩容增量是1倍
• ArrayList扩容增量是50%
• LinkedList采用双向链表不需要扩容

应用场景

• Vector和ArrayList在随机存取方面效率高，适合随机访问较多的场景
• LinkedList在节点的增删方面效率高，适合于频繁对节点进行操作的场景

HashSet和TreeSet有哪些区别？

• HashSet底层使用hash表实现
  保证元素唯一性的原理：判断元素的hashCode值是否相同。如果相同，还会继续判断元素的equals方法，是否为true
  HashSet的contains方法使用HashMap得containsKey方法实现
• TreeSet底层使用了红黑树来实现，其实底层实现还是TreeSet，只是用来其中的Key
  保证元素唯一性是通过Comparable或者Comparator接口实现

Iterator和ListIterator的区别是什么？

• Iterator可以遍历list和set集合；ListIterator只能用来遍历list集合
• Iterator前者只能前向遍历集合；ListIterator可以前向和后向遍历集合
• ListIterator其实就是实现了前者，并且增加了一些新的功能

数组与List之间的转换

• 数组转为List
  通过Arrays.asList 方法实现，转换之后不可以使用add/remove等修改集合的相关方法，因为该方法返回的其实是一个Arrays的在这里插入代码片内部私有的一个类ArrayList，本质上还是一个数组
• List转为数组
• 通过方法List.toArray实现，这里最好传入一个类型一样的数组，大小为list.size()
  如果入参分配的数组空间不够大，会重新分配内存空间返回新的数组
  如果数组元素大于实际需要的，多余的数组元素会被置null

Collection和Collections有什么关系？

• Collection是一个顶层集合接口，其子接口包括List和Set；
• Collections是一个集合工具类，可以操作集合，比如说排序，二分查找，拷贝集合，寻找最大最小值等。 总而言之：带s的大都是工具类。

以上就是我目前所掌握的Java面试相关的题目，后续发现有没有写到的比较重要的再补充上来。

有问题可以给我留言，看到了会及时的进行回复