面试必问Java集合框架

我就是我 2023-03-02 10:55 123阅读 0赞

**了解Java 集合**

**Java 集合，也称作容器，用来存放数据的，主要是由两大接口` (Iterator、ListIterator)` 派生出来的：`Collection 和 Map。`**

![20200729101249654.png][]

**这两大接口的不同之处在于：**

*  Collection 存放单一元素；
 *  Map 存放 key-value 键值对。

### **Collection** ###

**Collection是集合List、Set、Queue的基本的接口。 **

Collection 里还定义了很多方法，这些方法也都会继承到各个子接口和实现类里，而这些 API 的使用也是日常工作和面试常见常考的，所以我们先来看下这些方法。

操作集合，无非就是「增删改查」四大类，也叫 `CRUD`:

> Create, Read, Update, and Delete.

那我也把这些 API 分为这四大类：

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>add()/addAll()</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>remove()/ removeAll()</td> 
  </tr> 
  <tr> 
   <td>改</td> 
   <td>Collection Interface 里没有</td> 
  </tr> 
  <tr> 
   <td>查</td> 
   <td>contains()/ containsAll()</td> 
  </tr> 
  <tr> 
   <td>其他</td> 
   <td>isEmpty()/size()/toArray()</td> 
  </tr> 
 </tbody> 
</table>

下面具体来看：

增：

boolean add(E e);

`add()` 方法传入的数据类型必须是 Object，所以当写入基本数据类型的时候，会做自动装箱 auto-boxing 和自动拆箱 unboxing。

还有另外一个方法 `addAll()`，可以把另一个集合里的元素加到此集合中。

boolean addAll(Collection<? extends E> c);

删：

boolean remove(Object o);

`remove()`是删除的指定元素。

那和 `addAll()` 对应的，  
自然就有`removeAll()`，就是把集合 B 中的所有元素都删掉。

boolean removeAll(Collection<?> c);

改：

Collection Interface 里并没有直接改元素的操作，反正删和增就可以完成改了嘛！

查：

*  查下集合中有没有某个特定的元素：

boolean contains(Object o);

*  查集合 A 是否包含了集合 B：

boolean containsAll(Collection<?> c);

还有一些对集合整体的操作：

*  判断集合是否为空：

boolean isEmpty();

*  集合的大小：

int size();

*  把集合转成数组：

Object[] toArray();

以上就是 Collection 中常用的 API 了。

在接口里都定义好了，子类不要也得要。当然子类也会做一些自己的实现，这样就有了不同的数据结构。

**List的三大实现类 LinkedList 和 ArrayList 和Vector**

下图为三种实现类的比较：

![20200729102946703.png][]

**总结：**

1.  **改查选择 ArrayList；**
2.  **增删在尾部的选择 ArrayList；**
3.  **其他情况下，如果时间复杂度一样，推荐选择 ArrayList，因为 overhead 更小，或者说内存使用更有效率。**
4.  **线程安全使用Vector（** 底层synchronized**）**

**set三大实现类 HashSet和 LinkedHashSet和TreeSet**

下图为三种实现类的比较：

![20200729104118609.png][]

那每个 Set 的**底层实现**其实就是对应的 Map：**数值放在 map 中的 key 上，value 上放了个 PRESENT，是一个静态的 Object，相当于 place holder，每个 key 都指向这个 object。**

**Queue& Deque**

![20200729105222525.png][]

Java 中的 这个 Queue 接口稍微有点坑，一般来说队列的语义都是**先进先出**（FIFO）的。但是这里有个例外，就是 PriorityQueue，也叫 heap，并不按照进去的时间顺序出来，而是按照规定的优先级出去，并且它的操作并不是 O(1) 的，时间复杂度的计算稍微有点复杂。

那 Queue 的方法官网都总结好了，它有两组 API，基本功能是一样的，但是呢：

*  一组是会抛异常的；
 *  另一组会返回一个特殊值。

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>抛异常</th> 
   <th>返回值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>add(e)</td> 
   <td>offer(e)</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>remove()</td> 
   <td>poll()</td> 
  </tr> 
  <tr> 
   <td>瞧</td> 
   <td>element()</td> 
   <td>peek()</td> 
  </tr> 
 </tbody> 
</table>

**为什么会抛异常呢？**

*  比如队列空了，那 remove() 就会抛异常，但是 poll() 就返回 null；element() 就会抛异常，而 peek() 就返回 null 就好了。

**那 add(e) 怎么会抛异常呢？**

有些 Queue 它会有容量的限制，比如 **BlockingQueue**，那如果已经达到了它最大的容量且不会扩容的，就会抛异常；但如果 offer(e)，就会 return false.

**那怎么选择呢？：**

*  首先，要用就用**同一组 API**，前后要统一；
 *  其次，根据需求。如果你需要它抛异常，那就是用抛异常的；不过做算法题时基本不用，所以选那组返回特殊值的就好了。

Deque 是两端都可以进出的，那自然是有针对 First 端的操作和对 Last 端的操作，那每端都有两组，一组抛异常，一组返回特殊值：

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>抛异常</th> 
   <th>返回值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>addFirst(e)/ addLast(e)</td> 
   <td>offerFirst(e)/ offerLast(e)</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>removeFirst()/ removeLast()</td> 
   <td>pollFirst()/ pollLast()</td> 
  </tr> 
  <tr> 
   <td>瞧</td> 
   <td>getFirst()/ getLast()</td> 
   <td>peekFirst()/ peekLast()</td> 
  </tr> 
 </tbody> 
</table>

使用时同理，要用就用同一组。

Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度，准确来说是均摊时间复杂度。

### MAP ###

**map三大实现类 HashMap和HashTable和TreeMap**

![20200729105817698.png][]

**因为HashMap和HashTable的出过详细的讲解文章（[点击查看具体讲解][Link 1]），这里就不做记录了，只记录一下TreeMap**

TreeMap （可排序）实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序， 也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。   
如果使用排序的映射，建议使用TreeMap。   
在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

[20200729101249654.png]: /images/20230208/f15d1cf443e64f65bcb16e78c08e9540.png
[20200729102946703.png]: /images/20230208/9aba9d807d934d40b95432be2a1c3cc9.png
[20200729104118609.png]: /images/20230208/8fce0daf26884ea8b53342de3ec5e47e.png
[20200729105222525.png]: /images/20230208/b7e71a166d294b829b6bcfe2306daa37.png
[20200729105817698.png]: /images/20230208/93dfce6e86f64b7598d54a6f41c598b7.png
[Link 1]: https://blog.csdn.net/weixin_38007185/article/details/107628756