2024年java面试准备--集合篇

终有救赎

发布于 2023-10-16 10:11:43

3180

发布于 2023-10-16 10:11:43

文章被收录于专栏：多线程

集合面试准备

Collection接口是集合类的根接口，Java中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口，就是Set和List。Set中不能包含重复的元素。List是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。

Map是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key，但是可以包含相同的value。

Iterator，所有的集合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法： 1.hasNext()是否还有下一个元素。 2.next()返回下一个元素。 3.remove()删除当前元素。

List

有索引，有序可重复。ArrayList与Vector底层是数组，查询快增删慢。LinkedList底层是双向链表，查询慢增删快。ArrayList，LinkedList都是线程不安全，Vector线程安全。

List遍历

①普通for循环遍历List删除指定元素

for(int i=0; i < list.size(); i++){
   if(list.get(i) == 5) 
       list.remove(i);
}

② 迭代遍历,用list.remove(i)方法删除元素

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

③foreach遍历List删除元素

for(Integer i:list){
    if(i==3) list.remove(i);
}

Set

无索引。无序不重复，Set实质上使用的是Map的Key存储，如果要将自定义的类存储到Set中，需要重写equals和hashCode方法。HashSet底层是通过Hashmap来实现的，HashSet是无序不重复的，且不能排序,集合元素可以是null,但只能放入一个null

LinkedHashSet底层是链表（保证有序）+哈希表（保证集合的唯一性），查询慢增删快，它是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的顺序所以遍历的时候会按照添加时的顺序来访问。

TreeSet底层是红黑树，一般用于排序，可以使用compareTo进行排序方法来比较元素之间大小关系，然后将元素按照升序排列，有序。

Map

Map: Key无序不重复，Value可重复。

HashMap底层是数组+链表，它根据键的HashCode值存储数据,根据键可以直接获取它的值，访问速度很快。所以在Map中插入、删除和定位元素比较适合用hashMap。

LinkedHashMap底层是链表+哈希表，它是HashMap的一个子类，如果需要读取的顺序和插入的相同,可以用LinkedHashMap来实现。

TreeMap底层是红黑树，与TreeSet类似，取出来的是排序后的键值对。但如果是要按自然顺序或自定义顺序遍历键，那么TreeMap会更好，有序。

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）时，将链表转化为红黑树，以减少搜索时间

JDK1.7 HashMap：

底层是 数组和链表 结合在⼀起使⽤也就是链表散列。如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。扩容翻转时顺序不一致使用头插法会产生死循环，导致cpu100%

JDK1.8 HashMap：

底层数据结构上采用了数组＋链表＋红黑树；当链表⻓度⼤于阈值（默认为 8-泊松分布），数组的⻓度大于 64时，链表将转化为红⿊树，以减少搜索时间。（解决了tomcat臭名昭著的url参数dos攻击问题）

LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
HashTable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
TreeMap：红黑树（自平衡的排序二叉树）

List

ArrayList和LinkedList的区别

1.首先，他们的底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现的

2.由于底层数据结构不同，他们所适用的场景也不同，ArrayList更适合查找，LinkedList更适合删除和添加

3.另外ArrayList和LinkedList都实现了List接口，但是LinkedList还额外实现了Deque接口，所以LinkedList还可以当做队列来使用

4.ArratList的底层使用动态数组，默认容量为10，当元素数量到达容量时，生成一个新的数组，大小为前一次的1.5倍，然后将原来的数组copy过来；

Set

HashSet的实现原理？

HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，value统一为present，因此 HashSet 的实现比

较简单，相关 HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成，HashSet 不允许重复的值。

List接口和Set接口的区别

List：有序、可重复集合。按照对象插入的顺寻保存数据，允许多个Null元素对象，可以使用iterator迭代器遍历，也可以使用get(int index)方法获取指定下标元素。

Set：无序、不可重复集合只允许有一个Null元素对象，取元素时，只能使用iterator迭代器逐一遍历。

Map : key-value键值对形式的集合，添加或获取元素时，需要通过key来检索到value。

Map

HashMap

hashmap底层实现

HashMap 基于 Hash 算法实现的：

当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时，如果出现hash值相同的key，此时有两种情况。 (1)如果key相同，则覆盖原始值； (2)如果key不同（出现冲突），则将当前的key-value放入链表中
获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

数组加链表（1.8以前)，1.8之后添加了红黑树，基于hash表的map接口实现

阈值（边界值)>8并且桶位数(数组长度)大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

HashTable与HashMap的区别

（1）HashTable的每个方法都用synchronized修饰，因此是线程安全的，但同时读写效率很低

（2）HashTable的Key不允许为null

（3）HashTable只对key进行一次hash，HashMap进行了两次Hash

（4）HashTable底层使用的数组加链表

（5）HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。

线程不安全体现

在HashMap扩容的是时候会调用resize（）方法中的transfer()方法，在这里由于是头插法所以在多线程情况下可能出现循环链表，所以后面的数据定位到这条链表的时候会造成数据丢失。和读取的可能导致死循环。

并发修改导致数据不一致

HashMap的数据结构是基于数组和链表实现的。在进行插入或删除操作时，如果不同线程同时修改同一个位置的元素，就会导致数据不一致的情况。具体来说，当两个线程同时进行插入操作时，假设它们都要插入到同一个数组位置，并且该位置没有元素，那么它们都会认为该位置可以插入元素，最终就会导致其中一个线程的元素被覆盖掉。此外，在进行删除操作时，如果两个线程同时删除同一个元素，也会导致数据不一致的情况。

并发扩容导致死循环或数据丢失

当HashMap的元素数量达到一定阈值时，它会触发扩容操作，即重新分配更大的数组并将原来的元素重新映射到新的数组上。然而，在进行扩容操作时，如果不加锁或者加锁不正确，就可能导致死循环或者数据丢失的情况。具体来说，当两个线程同时进行扩容操作时，它们可能会同时将某个元素映射到新的数组上，从而导致该元素被覆盖掉。此外，在进行扩容操作时，如果线程不安全地修改了next指针，就可能会导致死循环的情况。

想要线程安全的HashMap怎么办？

（1）使用ConcurrentHashMap

（2）使用HashTable

（3）Collections.synchronizedHashMap()方法

put操作步骤：

1、判断数组是否为空，为空进行初始化;

2、不为空，则计算 key 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;

3、查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；

4、存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据；

5、若不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；

6、若不是红黑树，创建普通Node加入链表中；判断链表长度是否大于 8，大于则将链表转换为红黑树；

7、插入完成之后判断当前节点数是否大于阈值，若大于，则扩容为原数组的二倍

Map的put方法的是怎么实现的?

通过调用key的hashCode方法获取哈希值找到存放的数组下标，通过遍历此位置的key与插入的key通过equals比较，如果已存在则替换

值，不存在则插入进来。

Map如何遍历

Map实现类调用entrySet方法获得一个Entry类型的Set，通过遍历这个Set集合获取Entry调用getKey或者getValue获取值

HashMap和HashTable有什么区别?其底层实现是什么?

区别：

HashMap方法没有synchronized修饰，线程非安全，HashTable线程安全;
HashMap允许key和value为null，而HashTable不允许

ConcurrentHashMap

可以通过ConcurrentHashMap 和 Hashtable来实现线程安全；Hashtable 是原始API类，通过synchronize同步修饰，效率低下；ConcurrentHashMap 通过分段锁实现，效率较比Hashtable要好；

ConcurrentHashMap的底层实现：

ConcurrentHashMap是基于Segment分段实现的
每个Segment相对于一个小型的HashMap
扩容时，对待扩容Segment内部会进行扩容，不影响其他Segment对象
扩容时，先生成新的数组，然后转移元素到新数组中
扩容的判断也是每个Segment内部单独判断的，判断是否超过阈值

JDK1.7的 ConcurrentHashMap 底层采⽤ ReentrantLock和分段的数组+链表实现；采用 分段锁（Sagment）对整个桶数组进⾏了分割分段(Segment默认16个)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。

元素查询

采用两次hash的方式进行元素查询。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部

ConcurrentHashMap不再基于Segment实现
当某个线程进行put时，如果发现ConcurrentHashMap正在进行扩容那么该线程一起进行扩容
如果某个线程put时，发现没有正在进行扩容，则将key-value添加到ConcurrentHashMap中，然后判断是否超过阈值，超过了则进行扩容
ConcurrentHashMap是支持多个线程同时扩容的。扩容前也是生成一个新数组，在转移元素时，会按照不同的线程进行分组
在转移元素时，先将原数组分组，将每组分给不同的线程来进行元素的转移，每个线程负责一组或多组的元素转移工作

JDK1.8的 ConcurrentHashMap 采⽤的数据结构跟HashMap1.8的结构⼀样，数组+链表/红⿊树；摒弃了Segment的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，通过并发控制 synchronized 和CAS（乐观锁）来操作保证线程的安全。每次插入数据时判断在当前数组下标是否是第一次插入，是就通过CAS方式插入，然后判断f.hash是否=-1，是的话就说明其他线程正在进行扩容，当前线程也会参与扩容；删除方法用了synchronized修饰，保证并发下移除元素安全

相关面试题

ConcurrentHashMap 是如何保证线程安全的？ ConcurrentHashMap 使用分段锁的方式来实现线程安全，它将一个大的哈希表分成多个小的哈希表（段），每个小的哈希表都有自己的锁。这样，不同的线程可以同时访问不同的小哈希表，从而避免了多个线程同时竞争同一个锁的情况，提高了并发性能。

ConcurrentHashMap 的扩容机制是怎样的？ ConcurrentHashMap 的扩容机制与 HashMap 类似，它会在哈希表的负载因子达到阈值时进行扩容。扩容的过程中，ConcurrentHashMap 会将原来的小哈希表逐一复制到新的大哈希表中，这个过程中仍然可以保证线程安全。扩容后，ConcurrentHashMap 会继续使用分段锁的方式来维护新的小哈希表。

ConcurrentHashMap 的 get() 方法是否需要加锁？ ConcurrentHashMap 的 get() 方法不需要加锁，因为它是线程安全的。在并发访问时，ConcurrentHashMap 使用了 volatile 和 CAS 等机制来保证数据的一致性和可见性，所以可以保证多个线程同时访问时不会出现数据竞争和不一致的情况。

ConcurrentHashMap 与 Hashtable 有什么区别？ ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表，但是它们有很大的区别。ConcurrentHashMap 使用了分段锁的方式来提高并发性能，而 Hashtable 使用了一个全局锁来保证线程安全，所以并发性能比 ConcurrentHashMap 差很多。此外，ConcurrentHashMap 允许空键和空值，而 Hashtable 不允许。另外，ConcurrentHashMap 支持更多的操作，比如 ConcurrentHashMap 支持的批量操作和原子操作等，Hashtable 不支持。

红黑树

红黑树是一种特殊的二叉查找树。红黑树的每个结点上都有存储位表示结点的颜色，可以是红(Red)或黑(Black)。

红黑树的每个结点是黑色或者红色。当是不管怎么样他的根结点是黑色。每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！

如果一个结点是红色的，则它的子结点必须是黑色的。

每个结点到叶子结点NIL所经过的黑色结点的个数一样的。[确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的！]

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转和变色的目的是让树保持红黑树的特性。

解决哈希冲突的四种方式

1. 开放定址法

当关键字key的哈希地址p =H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，若p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

即：Hi=（H（key）+di）% m （i=1，2，…，n）

开放定址法有下边三种方式：

线性探测再散列 顺序查看下一个单元，直到找出一个空单元或查遍全表 di=1，2，3，…，m-1 二次(平方)探测再散列 在表的左右进行跳跃式探测，直到找出一个空单元或查遍全表 di=1^2，-1^2，2^2，-2^2，…，k^2，-k^2 ( k<=m/2 ) 伪随机探测再散列 建立一个伪随机数发生器，并给一个随机数作为起点 di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

优点

容易序列化若可预知数据总数，可以创建完美哈希数列

缺点

占空间很大。（开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间）删除节点很麻烦。不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

2. 再哈希法

提供多个哈希函数，如果第一个哈希函数计算出来的key的哈希值冲突了，则使用第二个哈希函数计算key的哈希值。

优点

不易产生聚集

缺点

增加了计算时间

3. 链地址法（hashmap使用此法）

对于相同的哈希值，使用链表进行连接

优点

处理冲突简单，无堆积现象。即非同义词决不会发生冲突，因此平均查找长度较短；适合总数经常变化的情况。（因为拉链法中各链表上的结点空间是动态申请的）占空间小。装填因子可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点

查询时效率较低。（存储是动态的，查询时跳转需要更多的时间）在key-value可以预知，以及没有后续增改操作时候，开放定址法性能优于链地址法。不容易序列化

4. 建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

Java集合的快速失败机制 “fail-fast”？

是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next() 遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。解决办法：在遍历过程中，所有涉及到改变modCount值的地方全部加上synchronized。使用CopyOnWriteArrayList来替换ArrayList

序列化和反序列化

序列化的意思就是将对象的状态转化成字节流，以后可以通过这些值再生成相同状态的对象。对象序列化是对象持久化的一种实现方法，它是将对象的属性和方法转化为一种序列化的形式用于存储和传输。反序列化就是根据这些保存的信息重建对象的过程。

序列化： 将java对象转化为字节序列的过程。

反序列化： 将字节序列转化为java对象的过程。

优点：

a、实现了数据的持久化，通过序列化可以把数据永久地保存到硬盘上（通常存放在文件里）Redis的RDB

b、利用序列化实现远程通信，即在网络上传送对象的字节序列。 Google的protoBuf

反序列化失败的场景：

序列化ID：serialVersionUID不一致的时候，导致反序列化失败

队列

Queue接口与List和Set同一级别，都是继承Collection接口。LinkedList实现了Deque接口

非阻塞队列

非阻塞队列不能阻塞，多线程时，当队列满或者队列空时，只能使用队列 wait()，notify() 进行队列消息传送。

LinkedList LinkedList 除了实现的 List 接口，也实现了 Deque 接口，可以当做双端队列来使用。
PriorityQueue PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。该队列不允许使用 null 元素也不允许插入不可比较的对象

PriorityQueue 队列的头指排序规则最小那个元素。如果多个元素都是最小值则随机选一个。 PriorityQueue 是一个无界队列，但是初始的容量（实际是一个Object[]），随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。

ConcurrentLinkedQueue ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列（CAS）。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。同样此队列不允许使用null元素

阻塞队列

阻塞队列 ArrayBlockingQueue ：一个由数组支持的有界队列。 LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。 PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。 DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。 SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。