集合框架面试题

一、集合容器的概述

1. 什么是集合

集合框架：用于存储数据的容器。
集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：
对外的接口、接口的实现和对集合运算的算法。
接口：表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现，从而达到“多态”。在面
向对象编程语言中，接口通常用来形成规范。
实现：集合接口的具体实现，是重用性很高的数据结构。
算法：在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法，例如查找、排序
等。这些算法通常是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实
上，算法是可复用的函数。它减少了程序设计的辛劳。

2. 集合的特点

集合的特点主要有如下两点：
对象封装数据，对象多了也需要存储。集合用于存储对象。
对象的个数确定可以使用数组，对象的个数不确定的可以用集合。因为集合是可变长度的

3. 集合和数组的区别

数组是固定长度的；集合可变长度的。
数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

4. 常用的集合类有哪些？

Map接口和Collection接口是所有集合框架的父接口：
1. Collection接口的子接口包括：Set接口和List接口
2. Map接口的实现类主要有：HashMap、TreeMap、Hashtable、 ConcurrentHashMap以及
Properties等
3. Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
4. List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

5. List，Set，Map三者的区别？

List、Set、Map 是否继承自Collection 接口？List、Map、Set 三个接口存取元素时，各有什么
特点？

Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、 List、Queue三种子接口。
我们比较常用的是Set、List，Map接口不是 collection的子接口。
Collection集合主要有List和Set两大接口
List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个
null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个
null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、 LinkedHashSet 以及
TreeSet。
Map是一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。
Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对
象。
Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、 ConcurrentHashMap

6. 集合框架底层数据结构

Collection
List
Arraylist： Object数组
Vector： Object数组
LinkedList：双向循环链表
Set
HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素
LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现
的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一
点点区别的。
TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树。) Map
HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要
为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后
在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，
以减少搜索时间
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结
构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向
链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
HashTable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存
在的
TreeMap：红黑树（自平衡的排序二叉树）

7. 哪些集合类是线程安全的

hashtable：就比hashmap多了个线程安全

8. 怎么确保一个集合不能被修改

可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个只读集合，这样改变集合
的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。示例代码如下

List list  = new ArrayList();list.add("呀");Collection collection = Collections.unmodifiableCollection(list);collection.add("hah");//运行时，此行会报错

二、Collection接口

1. List接口

1.1 Iterator是什么？

是迭代器，Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器允许调用者在迭代过程中移除元素

Iterator iterator = list.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}

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

1.2 如何边遍历边移除 Collection 中的元素

边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下

  Iterator<Integer> it = list.iterator();while(it.hasNext()){it.remove(); 
}

一种常见的错误代码如下

for(Integer i : list){list.remove(i)}

运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integeri : list)) 语句时，会自动生成一个iterator 来遍历该 list，但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它

1.3 Iterator 和 ListIterator 有什么区别

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

1.4 集合的遍历方式

1. for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读
取到后一个元素后停止。
2. 迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，
统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。
3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明
Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操
作数据集合，例如删除、替换。

最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支持
Random Access。
如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读取元素的平均时间
复杂度为 O(1)，如ArrayList。
如果没有实现该接口，表示不支持 Random Access，如LinkedList。推荐的做法就是，支持
Random Access 的列表可用 for 循环遍历，否则建议用 Iterator 或 foreach 遍历。

1.5 ArrayList的优缺点

ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查
找的时候非常快。
ArrayList 在顺序添加一个元素的时候非常方便

ArrayList 的缺点如下：
删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
插入元素的时候，也需要做一次元素复制操作，缺点同上。
ArrayList 比较适合顺序添加、随机访问的场景。

1.6 多线程场景下如何使用 ArrayList

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

1 List<String> synchronizedList = Collections.synchronizedList(list);
2 synchronizedList.add("aaa");
3 synchronizedList.add("bbb");
4
5 for (int i = 0; i < synchronizedList.size(); i++) {
6 System.out.println(synchronizedList.get(i));
7 }

1.7 List 和 Set 的区别

List , Set 都是继承自Collection 接口
List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null
元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector

Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是HashSet、LinkedHashSet 以及 TreeSet。
另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。
Set和List对比
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变

1.8 ArrayList扩容机制

ArrayList是一个数组结构的存储容器，默认情况下，数组的长度是10。

当然我们也可以在构建ArrayList对象的时候自己指定初始长度。

随着在程序里面不断的往ArrayList中添加数据，当添加的数据达到10个的时候，ArrayList就没有多余容量可以存储后续的数据。

这个时候ArrayList会自动触发扩容。

扩容的具体流程很简单：

首先，创建一个新的数组，这个新数组的长度是原来数组长度的1.5倍。
然后使用Arrays.copyOf方法把老数组里面的数据拷贝到新的数组里面。
扩容完成后再把当前要添加的元素加入到新的数组里面，从而完成动态扩容的过程。

1.9 为什么扩容因子是1.5

扩容的目的需要综合考虑这两种情况：

扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制

扩容容量不能太大，需要充分利用空间，避免浪费过多空间；

而扩容固定容量，很难决定到底取多少值合适，取任何具体值都不太合适，因为所需数据量往往由数组的客户端在具体应用场景决定。依赖于当前已经使用的量 * 系数，比较符合实际应用场景。

比如，我现在已经用到一个数组100的容量，接下来很可能会有这个数量级的数据需要插入。

为什么是1.5，而不是1.2，1.25，1.8或者1.75？

因为1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

ArrayList采用1.5倍扩容的主要原因是在平衡内存空间的利用率和性能之间。通过选择1.5倍的扩容，可以在一定程度上减少频繁扩容的次数，同时也避免了过多的内存浪费。这种折中的策略在大多数情况下都能够提供较好的性能和内存利用率

2. Set接口

2.1 HashSet 的实现原理

HashSet 是基于 HashMap 实现的，HashSet的元素存放于HashMap的key上，HashMap的value统一为PRESENT，因为hashmap的key不可重复，从而保证了hashset元素不可重复，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成

解析不重复

向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。
HashSet 中的add ()方法会使用HashMap 的put()方法。

先看下面这个案例

public static void main(String[] args) {HashSet<Student> students = new HashSet<>();Student s1 = new Student("张三", 10);Student s2 = new Student("张三", 10);Student s3 = new Student("张三", 10);students.add(s1);students.add(s2);students.add(s3);
System.out.println(students.size());for (Student student : students) {System.out.println(student);}
}

输出结果为

结果好像与我们设想的不太一致，HashSet不是不允许元素重复吗？这里却有三个重复的元素？

因为hashset底层是基于hashmap实现的，所以要仔细研究一下hashmap的add方法，打开源码

(k = p.key) == key || (key != null && key.equals(k))

当我们调用一次add方法，添加一个对象s1后，再调用添加s2，就会判断s1==s2（判断地址），显然两个对象的地址值不同，所以继续判断，s1.equal(s2)，但是我们没有重写对象的equals方法，就会直接判断地址值，即也是s1==s2。两次判断都是false，所以判断为新的元素，就添加到hashmap中了

总结：所以要实现去除重复数据，是要重写对象的equals方法和hashcode方法，也就是比较成员属性值是否是一样的

2.2 ==和equals

==与equals的区别
1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存
空间的值是不是相同
2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.== 指引用是否相同 equals()指的
是值是否相同

2.3 hashCode与equals

如果两个对象相等，则hashcode一定也是相同的

两个对象相等,对两个equals方法返回true

两个对象有相同的hashcode值，它们也不一定是相等的

2.4 为什么重写equals方法也要重写hashcode方法

equals和hashcode是用来协同判断两个对象是否相等的，如果只重写了equals方法，而不重写hashcode，就会导致某些场景下程序异常

比如给Set集合中插入两个对象时，因为这两个对象引用地址不同，但是属性值都相同，那么正常情况下，不能重复插入才对。然而，因为未重写hashcode，所以导致判断hashcode不同，因为hashcode是使用Object类的native的hashcode，所以就认为它们是不同的对象，这样就会将两个相同的对象都存储到Set集合中，这显然是有问题的，因为使用Set集合就是用来去重的，结果这样一来存入了两个相同的对象，与我们的期望不符

3. Map接口

3.1 hashmap的实现原理

HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，
并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap的数据结构：在Java编程语言中，基本的结构就是两种，一个是数组，另外一个是模拟指针
（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上
是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap 基于 Hash 算法实现的
1. 当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中
的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相
同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value 放入链表中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方
式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个
之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

3.2 HashMap在JDK1.7和JDK1.8中有哪些不同？

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突

JDK1.8之前
JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一
格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
JDK1.8之后
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
JDK1.7 VS JDK1.8 比较
JDK1.8主要解决或优化了一下问题：
1. resize 扩容优化
2. 引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考
3. 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。

3.3 hashmap最全总结

hashmap面试题汇总

三、辅助工具类

1. Array(数组) 和 ArrayList 有何区别？

Array 可以存储基本数据类型和对象，ArrayList 只能存储对象。
Array 是指定固定大小的，而 ArrayList 大小是自动扩展的。
Array 内置方法没有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。
对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

2. 如何实现 Array 和 List 之间的转换？

Array 转 List： Arrays. asList(array) ；
List 转 Array： List 的 toArray() 方法。

3. Collection 和 Collections 有什么区别？

java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操
作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为
各种具体的集合提供了大化的统一操作方式，其直接继承接口有List与Set。
Collections则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进
行排序、搜索以及线程安全等各种操作。

4. Comparable和Comparator

java的比较器有两类，分别是Comparable接口和Comparator接口。

在为对象数组进行排序时，比较器的作用非常明显，首先来讲解Comparable接口。

让需要进行排序的对象实现Comparable接口，重写其中的compareTo(T o)方法，在其中定义排序规则，那么就可以直接调用java.util.Arrays.sort()来排序对象数组

Comparator：“比较器”
使用这种策略来比较时，如何进行比较和两个对象本身无关，而是由第三者（即比较器）来完成的。第三方比较器类需要另外专门设计:只要实现Comparator接口，任何一个类(对象)都可能成为一个“比较器”，但比较器并不是比较自己的实例，而是比较其它类的两个不同对象，比较器在这里充当“仲裁者”的角色，这也就是为什么compare()方法需要两个参数。
比如，两个人要比较谁智商更高，靠他们自身无法进行，这时要借助一个比较器（比如，智商测试题）。

Comparable和Comparator这两个接口和集合接口（Collection）本身无关，但通常和集合内的元素有关，因为集合的排序要用到这两个排序接口中的方法（二选其一）。一个类的多个实例要想实现排序，必须实现Comparable，或者提供相应的Comparator才能使用Collections.sort()进行排序

5. Vector,ArrayList, LinkedList的区别是什么

1. Vector、ArrayList都是以类似数组的形式存储在内存中，LinkedList则以链表的形式进行存储。
2. List中的元素有序、允许有重复的元素，Set中的元素无序、不允许有重复元素。
3. Vector线程同步，ArrayList、LinkedList线程不同步。
4. LinkedList适合指定位置插入、删除操作，不适合查找；ArrayList、Vector适合查找，不适合指定位置的插入、删除操作。
5. ArrayList在元素填满容器时会自动扩充容器大小的50%，而Vector则是100%，因此ArrayList更节省空间。

6. HashTable, HashMap，TreeMap区别？

1. HashTable线程同步，HashMap非线程同步。
2. HashTable不允许<键,值>有空值，HashMap允许<键,值>有空值。
3. HashTable使用Enumeration，HashMap使用Iterator。
4. HashTable中hash数组的默认大小是11，增加方式的old*2+1，HashMap中hash数组的默认大小
是16，增长方式一定是2的指数倍。
5. TreeMap能够把它保存的记录根据键排序，默认是按升序排序。