剖析⾯试最常⻅问题之Java集合框架

集合概述

Java集合概述

集合概述 Java 集合概览 从下图可以看出，在 Java 中除了以 Map 结尾的类之外， 其他类都实现了 Collection 接⼝。 并且，以 Map 结尾的类都实现了 Map 接⼝。

image-20211105192518597

说说List,Set,Map 三者的区别？

• List (对付顺序的好帮⼿): 存储的元素是有序的、可重复的。
• Set(注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的。
• Map (⽤ Key 来搜索的专家): 使⽤键值对（kye-value）存储，类似于数学上的函数 y=f(x)， “x”代表 key，”y”代表 value，Key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个 键最多映射到⼀个值。

集合框架底层数据结构总结

先来看⼀下 Collection 接⼝下⾯的集合。

List

• Arraylist ： Object[] 数组
• Vector ： Object[] 数组
• LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set

• HashSet （⽆序，唯⼀）: 基于 HashMap 实现的，底层采⽤ HashMap 来保存元素
• LinkedHashSet ： LinkedHashSet 是 HashSet 的⼦类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现⼀样，不过还是有⼀点点区别的
• TreeSet （有序，唯⼀）： 红⿊树(⾃平衡的排序⼆叉树)

再来看看 Map 接⼝下⾯的集合。

Map

• HashMap ： JDK1.8 之前 HashMap由数组+链表组成的，数组是 HashMap 的主体，链表则是主 要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较⼤ 的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓ 度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以 减少搜索时间
• LinkedHashMap： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散 列结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了 ⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作， 实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
• Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突 ⽽存在的
• TreeMap ： 红⿊树（⾃平衡的排序⼆叉树）

如何选用集合？

主要根据集合的特点来选⽤，⽐如我们需要根据键值获取到元素值时就选⽤ Map 接⼝下的集合，需 要排序时选择 TreeMap ,不需要排序时就选择 HashMap ,需要保证线程安全就选⽤ ConcurrentHashMap 。

当我们只需要存放元素值时，就选择实现 Collection 接⼝的集合，需要保证元素唯⼀时选择实现 Set 接⼝的集合⽐如 TreeSet 或 HashSet ，不需要就选择实现 List 接⼝的⽐如 ArrayList 或 LinkedList ，然后再根据实现这些接⼝的集合的特点来选⽤。

为什么要使⽤集合？

当我们需要保存⼀组类型相同的数据的时候，我们应该是⽤⼀个容器来保存，这个容器就是数组，但 是，使⽤数组存储对象具有⼀定的弊端， 因为我们在实际开发中，存储的数据的类型是多种多样的， 于是，就出现了“集合”，集合同样也是⽤来存储多个数据的。

数组的缺点是⼀旦声明之后，⻓度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数 据的类型；⽽且，数组存储的数据是有序的、可重复的，特点单⼀。 但是集合提⾼了数据存储的灵活 性，Java 集合不仅可以⽤来存储不同类型不同数量的对象，还可以保存具有映射关系的数据

Iterator 迭代器

迭代器 Iterator 是什么？

java

public interface Iterator<E> {
    //集合中是否还有元素
    boolean hasNext();
    //获得集合中的下⼀个元素
    E next();
    ......
}

Iterator 对象称为迭代器（设计模式的⼀种），迭代器可以对集合进⾏遍历，但每⼀个集合内部的 数据结构可能是不尽相同的，所以每⼀个集合存和取都很可能是不⼀样的，虽然我们可以⼈为地在每⼀ 个类中定义 hasNext() 和 next() ⽅法，但这样做会让整个集合体系过于臃肿。于是就有了迭代器。

迭代器是将这样的⽅法抽取出接⼝，然后在每个类的内部，定义⾃⼰迭代⽅式，这样做就规定了整个集 合体系的遍历⽅式都是 hasNext() 和 next() ⽅法，使⽤者不⽤管怎么实现的，会⽤即可。迭代器的 定义为：提供⼀种⽅法访问⼀个容器对象中各个元素，⽽⼜不需要暴露该对象的内部细节。

迭代器 Iterator 有啥用？

Iterator 主要是⽤来遍历集合⽤的，它的特点是更加安全，因为它可以确保，在当前遍历的集合元 素被更改的时候，就会抛出 ConcurrentModificationException 异常。

如何使用？

我们通过使⽤迭代器来遍历 HashMap ，演示⼀下 迭代器 Iterator 的使⽤。

xml

Map<Integer, String> map = new HashMap();
map.put(1, "Java");
map.put(2, "C++");
map.put(3, "PHP");
Iterator<Map.Entry<Integer, Stringef iterator =
map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    System.out.println(entry.getKey() + entry.getValue());
}

有哪些集合是线程不安全的？怎么解决呢？

我们常⽤的 Arraylist , LinkedList , Hashmap , HashSet , TreeSet , TreeMap ， PriorityQueue 都不是线程安全的。 解决办法很简单，可以使⽤线程安全的集合来代替。

如果你要使⽤线程安全的集合的话， java.util.concurrent 包中提供了很多并发容器供你使⽤：

1. ConcurrentHashMap : 可以看作是线程安全的 HashMap
2. CopyOnWriteArrayList :可以看作是线程安全的 ArrayList ，在读多写少的场合性能⾮常 好，远远好于 Vector .
3. ConcurrentLinkedQueue :⾼效的并发队列，使⽤链表实现。可以看做⼀个线程安全的 LinkedList ，这是⼀个⾮阻塞队列。
4. BlockingQueue : 这是⼀个接⼝，JDK 内部通过链表、数组等⽅式实现了这个接⼝。表示阻塞队列，⾮常适合⽤于作为数据共享的通道。
5. ConcurrentSkipListMap :跳表的实现。这是⼀个Map，使⽤跳表的数据结构进⾏快速查找。