java八股文面试[数据结构]——集合框架

迈不过友情╰ 2024-03-24 20:14 55阅读 0赞

### Java集合体系框架 ###

![0b453a0a27fd6fddc47bffc190145cde.png][]

Java集合类主要由两个根接口Collection和Map派生出来的。

**Collection派生出了三个子接口：**

![8afe09adff8afa258861f832bb637110.png][]

**Map接口派生：**

Map代表的是存储key-value对的集合，可根据元素的key来访问value。

![3a91331430fc2ce71c11a54704942021.png][]

因此Java集合大致也可分成**List、Set、Queue、Map四种接口体系**。

### Java集合List ###

List代表了有序可重复集合，可直接根据元素的索引来访问。

List接口常用的实现类有：ArrayList、LinkedList、Vector。

### List集合特点 ###

*  集合中的元素允许重复
 *  集合中的元素是有顺序的，各元素插入的顺序就是各元素的顺序
 *  集合中的元素可以通过索引来访问或者设置

### ArrayList ###

ArrayList是一个动态数组，也是我们最常用的集合，是List类的典型实现。

它允许任何符合规则的元素插入甚至包括null，每一个ArrayList都有一个**初始容量（10）**，该容量代表了数组的大小。

随着容器中的元素不断增加，容器的大小也会随着增加，在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。

所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

ArrayList擅长于随机访问，同时ArrayList是非同步的。

### Vector ###

与ArrayList相似，但是Vector是同步的，它的操作与ArrayList几乎一样。

### LinkedList ###

LinkedList是采用**双向循环链表**实现，LinkedList是List接口的另一个实现，除了可以根据索引访问集合元素外，LinkedList还实现了Deque接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用。

### Java List总结 ###

**1）ArrayList**  
优点: 底层数据结构是数组，查询快，增删慢。  
缺点: 线程不安全，效率高

**2）Vector**  
优点: 底层数据结构是数组，查询快，增删慢。  
缺点: 线程安全，效率低

**3）LinkedList**  
优点: 底层数据结构是链表，查询慢，增删快。  
缺点: 线程不安全，效率高

### Java集合Set ###

Set扩展Collection接口,无序集合，不允许存放重复的元素。

Set接口常用的实现类有：HashSet、LinkedHashSet、TreeSet

![056c2b96e50a89d220abb457cbd1c776.png][]

### HashSet ###

**HashSet是Set集合最常用实现类，是其经典实现。**

HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写**hashCode()和equals()**方法来保证的，如果没有重写这两个方法，则**无法保证元素的唯一性**。

### LinkedHashSet ###

底层数据结构采用链表和哈希表共同实现，链表保证了**元素的顺序与存储顺序一致**，哈希表保证了元素的唯一性。

（**面试题**：设计一个记录存储顺序的HashSet思路）

### TreeSet ###

底层数据结构采用二叉树来实现，元素唯一且已经排好序,唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。

### Java Set总结 ###

**1）HashSet**

*  底层其实是包装了一个HashMap实现的
 *  底层数据结构是数组+链表 + 红黑树
 *  具有比较好的读取和查找性能， 可以有null 值
 *  通过equals和HashCode来判断两个元素是否相等
 *  非线程安全

**2）LinkedHashSet**

*  继承HashSet，本质是LinkedHashMap实现
 *  底层数据结构由哈希表(是一个元素为链表的数组)和双向链表组成。
 *  有序的，根据HashCode的值来决定元素的存储位置，同时使用一个链表来维护元素的插入顺序
 *  非线程安全，可以有null 值

**3）TreeSet**

*  是一种**排序的Set集合**，实现了SortedSet接口，底层是用TreeMap实现的，本质上是一个红黑树原理
 *  排序分两种：自然排序（存储元素实现Comparable接口）和定制排序（创建TreeSet时，传递一个自己实现的Comparator对象）
 *  正常情况下不能有null值，可以重写Comparable接口 局可以有null值了。

### Java集合Queue ###

![a8f4b13a91913e15a8fa9f5873aedb1e.png][]

队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

### PriorityQueue ###

PriorityQueue保存队列元素的顺序并不是按照加入的顺序，而是按照队列**元素的大小**进行排序的。  
PriorityQueue不允许插入null元素。

### Deque ###

Deque接口是Queue接口的子接口，它代表一个双端队列,当程序中需要使用“**栈**”这种数据结构时，推荐使用ArrayDeque。

### Java集合Map ###

Map用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。

![befb1b3cb0524146cb8de0dc606a550e.png][]

### 1.HashMap ###

Map接口基于哈希表的实现，是使用频率最高的用于键值对处理的数据类型。

它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，特点是访问速度快，遍历顺序不确定，线程不安全，最多允许一个key为null，允许多个value为null。

可以用 **Collections的synchronizedMap**方法使HashMap具有线程安全的能力，或者使用**ConcurrentHashMap**类。

### 2.Hashtable ###

Hashtable和HashMap从存储结构和实现来讲有很多相似之处，不同的是**它承自Dictionary类**，而且是**线程安全**的，另外Hashtable不允许key和value为null，并发性不如ConcurrentHashMap。

Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

### 3.LinkedHashMap ###

LinkedHashMap继承了HashMap，是Map接口的哈希表和链接列表实现，它维护着一个双重链接列表，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

### 4.TreeMap ###

TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序（自然顺序），也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是**排过序**的。

### 5.Map总结 ###

![2ececb1ae546a4e3424467ad4026938a.png][]

hashtable TreeMap key不可以为null

速记：线程安全的有：**Vector Hashtable** **ConcurrentHashMap**

###### 其他知识点： ######

**怎么确保一个集合不能被修改？**  
可以使用 Collections. unmodififiableCollection(Collection c) 方法来创建一个只读集合，这样改变  
集合的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。

**如何边遍历边移除 Collection 中的元素？**  
边遍历边修改 Collection 的唯一正确方式是使用 **Iterator.remove() 方法**，如下：  
一种最常见的 错误 代码如下：  
运行以上错误代码会报 ConcurrentModifificationException 异常 。这是因为当使用  
foreach(for(Integer i : list)) 语句时，会自动生成一个 iterator 来遍历该 list ，但同时该 list 正在被  
Iterator.remove() 修改。 Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它。

**Iterator 和 ListIterator 有什么区别？**  
Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能遍历 List 。  
Iterator 只能单向遍历，而 ListIterator 可以双向遍历（向前 / 后遍历）。  
ListIterator 实现 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元  
素、获取前面或后面元素的索引位置。

**多线程场景下如何使用 ArrayList ？**  
ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方  
法将其转换成线程安全的容器后再使用。

**为什么 ArrayList 的 elementData 加上 transient 修饰？**  
ArrayList 中的数组定义如下：  
private **transient** Object\[\] elementData;  
再看一下 ArrayList 的定义：  
List<String> synchronizedList = Collections.synchronizedList(list);  
synchronizedList.add("aaa");  
synchronizedList.add("bbb");  
for (int i = 0; i < synchronizedList.size(); i++) \{  
System.out.println(synchronizedList.get(i));  
\}  
public class ArrayList<E> extends AbstractList<E>  
implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 **Serializable** 接口，这意味着 ArrayList **支持序列化**。 transient 的作用  
是说**不希望 elementData 数组被序列化**，重写了 writeObject 实现：  
每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后  
遍历 elementData ，**只序列化已存入的元素**，这样既加快了序列化的速度，又减小了序列化之后  
的文件大小。

**什么是 Hash 算法**  
哈希算法是指把任意长度的二进制映射为**固定长度**的较小的二进制值，这个较小的二进制值叫做哈  
希值。

**知识速记：**

![9b57e5acf7ebabd9002f1262a88f02b6.png][]

![747a3b43849867e4e80aef6691ef69d8.png][]

知识来源：

[Java集合框架最全详解(看这篇就够了) - 知乎][Java_ -]

[JAVA集合面试题52道\_秋枫要学习的博客-CSDN博客][JAVA_52_-CSDN]

同步容器：（TODO)

[https://www.cnblogs.com/liyanbofly/p/16871925.html][https_www.cnblogs.com_liyanbofly_p_16871925.html]

[0b453a0a27fd6fddc47bffc190145cde.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c70fa9410d8f4ad9b380bd3e0b6adf04.png
[8afe09adff8afa258861f832bb637110.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/4bef9cce2ca54891bb248eb3504e2d97.png
[3a91331430fc2ce71c11a54704942021.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/225219b8e55d432f936179231e35a77c.png
[056c2b96e50a89d220abb457cbd1c776.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/a45cdc9e1c0745eb985e45e58370d337.png
[a8f4b13a91913e15a8fa9f5873aedb1e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e553b9092ff641cfb299a14ff2d71f85.png
[befb1b3cb0524146cb8de0dc606a550e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/45448eb4f6454395b5dbb0cd435830b3.png
[2ececb1ae546a4e3424467ad4026938a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/0b87788aaed2465ba790eb8a48b2b00b.png
[9b57e5acf7ebabd9002f1262a88f02b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/03517f84c9164da09a71b61ec6f456d2.png
[747a3b43849867e4e80aef6691ef69d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/d38d030a4fb643f7b0e70f39036006bc.png
[Java_ -]: https://zhuanlan.zhihu.com/p/511540318
[JAVA_52_-CSDN]: https://blog.csdn.net/The____wind/article/details/120762937
[https_www.cnblogs.com_liyanbofly_p_16871925.html]: https://www.cnblogs.com/liyanbofly/p/16871925.html