Java 集合框架面经

1、说说有哪些常见的集合框架？

集合框架可以分为两条大的支线：

• Map 接口：表现键值对的集合，一个键映射到一个值。键不能重复，每个键只能对应一个值。Map 接口的实现类包括 HashMap、LinkedHashMap、TreeMap 等。
  
• Collection 接口：最根本的集合框架表现方式，提供了添加、删除、清空等根本操作，它紧张有三个子接口：
  

• List 代表有序、可重复的集合，典型代表就是封装了动态数组的 ArrayList 和封装了链表的 LinkedList。
  
• Set 代表无序、不可重复的集合，典型代表就是 HashSet 和 TreeSet。
  
• Queue 代表队列，典型代表就是双端队列 ArrayDeque，以及优先级队列 PriorityQueue。
  

1.1 集合框架有哪几个常用工具类？

集合框架位于 java.util 包下，提供了两个常用的工具类：

• Collections：提供了一些对集合举行排序、二分查找、同步的静态方法。
  
• Arrays：提供了一些对数组举行排序、打印、和 List 举行转换的静态方法。
  

1.2 简朴先容一下队列？

Java 中的队列紧张通过 Queue 接口和并发包下的 BlockingQueue 两个接口来实现。
优先级队列 PriorityQueue 实现了 Queue 接口，是一个无界队列，它的元素按照自然次序排序或者 Comparator 比较器举行排序。双端队列 ArrayDeque 也实现了 Queue 接口，是一个基于数组的，可以在两端插入和删除元素的队列。
1.3 用过哪些集合类，它们的优劣？

我常用的集合类有 ArrayList、LinkedList、HashMap、LinkedHashMap。
ArrayList 可以看作是一个动态数组，可以在需要时动态扩容数组的容量，只不外需要复制元素到新的数组。优点是访问速率快，可以通过索引直接查找到元素。缺点是插入和删除元素大概需要移动或者复制元素。
LinkedList 是一个双向链表，适合频繁的插入和删除操作。优点是插入和删除元素的时候只需要改背叛点的前后指针，缺点是访问元素时需要遍历链表。
HashMap 是一个基于哈希表的键值对集合。优点是可以根据键的哈希值快速查找到值，但有大概会发生哈希冲突，并且不保留键值对的插入次序。
LinkedHashMap 在 HashMap 的基础上增加了一个双向链表来保持键值对的插入次序。
1.4 队列和栈的区别了解吗？

队列是一种先进先出的数据布局，第一个参加队列的元素会成为第一个被移除的元素。栈是一种后进先出的数据布局，最后一个参加栈的元素会成为第一个被移除的元素。
1.5 哪些是线程安全的容器？

Vector、Hashtable、ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue、ArrayBlockingQueue、LinkedBlockingQueue 都是线程安全的。
1.6 Collection 继承了哪些接口？

Collection 继承了 Iterable 接口，这意味着全部实现 Collection 接口的类都必须实现 iterator() 方法，之后就可以使用加强型 for 循环遍历集合中的元素了。
2、ArrayList 和 LinkedList 有什么区别？

ArrayList 是基于数组实现的，LinkedList 是基于链表实现的。

2.1 ArrayList 和 LinkedList 的用途有什么差别？

多数情况下，ArrayList 更利于改查，LinkedList 更利于增删。
2.2 ArrayList 和 LinkedList 是否支持随机访问？

• ArrayList 是基于数组的，也实现了 RandomAccess 接口，所以它支持随机访问，可以通过下标直接获取元素。
  
• LinkedList 是基于链表的，所以它没法根据下标直接获取元素，不支持随机访问。
  

2.3 ArrayList 和 LinkedList 内存占用有何差别？

• ArrayList 是基于数组的，是一块连续的内存空间，所以它的内存占用是比较紧凑的；但如果涉及到扩容，就会重新分配内存，空间是原来的 1.5 倍。
  
• LinkedList 是基于链表的，每个节点都有一个指向下一个节点和上一个节点的引用，于是每个节点占用的内存空间比 ArrayList 稍微大一点。
  

2.4 ArrayList 和 LinkedList 的使用场景有什么差别？

ArrayList 适用的场景：

• 随机访问频繁：需要频繁通过索引访问元素的场景。
  
• 读取操作远多于写入操作：如存储不常常改变的列表。
  
• 末端添加元素：需要频繁在列表末端添加元素的场景。
  

LinkedList 适用的场景：

• 不需要快速随机访问：次序访问多于随机访问的场景。
  
• 频繁插入和删除：在列表中间频繁插入和删除元素的场景。
  
• 队列和栈：由于其双向链表的特性，LinkedList 可以实现队列（FIFO）和栈（LIFO）。
  

2.5 链表和数组有什么区别？

• 数组在内存中占用的是一块连续的存储空间，因此我们可以通过数组下标快速访问任意元素。数组在创建时必须指定大小，一旦分配内存，数组的大小就固定了。
  
• 链表的元素存储在于内存中的任意位置，每个节点通过指针指向下一个节点。
  
  
  
  

3、ArrayList 的扩容机制了解吗？

当往 ArrayList 中添加元素时，会先查抄是否需要扩容，如果当前容量 + 1 超过数组长度，就会举行扩容。扩容后的新数组长度是原来的 1.5 倍，然后再把原数组的值拷贝到新数组中。

4、ArrayList 怎么序列化的知道吗？

ArrayList 自界说了序列化逻辑从而只序列化有效数据，因为数组的容量一样平常大于实际的元素数量。
4.1 为什么 ArrayList 不直接序列化元素数组呢？

出于服从的考虑，数组大概长度 100，但实际只用了 50，剩下的 50 没用到，也就不需要序列化。
5、快速失败 fail-fast 了解吗？

在用迭代器遍历集合对象时，如果线程 A 遍历过程中，线程 B 对集合对象的内容举行了修改，就会抛出 Concurrent Modification Exception。迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用 hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出非常，停止遍历。
java.util 包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 ArrayList 类。
5.1 什么是安全失败？

采用安全失败机制的集合容器，在遍历时并不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上举行遍历。
场景：java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如 CopyOnWriteArrayList 类
6、有哪几种实现 ArrayList 线程安全的方法？

• 可以使用 Collections.synchronizedList() 方法，它可以返回一个线程安全的 List。内部是通过 synchronized 关键字加锁来实现的。
  
• 也可以直接使用 CopyOnWriteArrayList，它是线程安全的 ArrayList，遵循写时复制的原则，每当对列表举行修改时，都会创建一个新副本，这个新副本会更换旧的列表，而对旧列表的全部读取操作仍然在原有的列表上举行。
  

6.1 ArrayList 和 Vector 的区别？

Vector 属于 JDK 1.0 时期的遗留类，不推荐使用，仍然保留着是因为 Java 希望向后兼容。
ArrayList 是在 JDK 1.2 时引入的，用于替代 Vector 作为紧张的非同步动态数组实现。因为 Vector 全部的方法都使用了 synchronized 关键字举行同步，所以单线程环境下服从较低。
7、CopyOnWriteArrayList 了解多少？

CopyOnWriteArrayList 就是线程安全版本的 ArrayList。采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的。至于写操作，比如说向容器中添加一个元素，起首将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

8、能说一下 HashMap 的底层数据布局吗？

JDK 8 中 HashMap 的数据布局是数组 + 链表 + 红黑树：

数组用来存储键值对，每个键值对可以通过索引直接拿到，索引是通过对键的哈希值举行进一步的 hash() 处理得到的。当多个键经过哈希处理后得到相同的索引时，需要通过链表来解决哈希冲突：将具有相同索引的键值对通过链表存储起来。不外，链表过长时，查询服从会比较低，于是当链表的长度超过 8 时（且数组的长度大于 64），链表就会转换为红黑树。红黑树的查询服从是 O(logn)，比链表的 O(n) 要快。
hash() 方法的目的是尽量淘汰哈希冲突，包管元素可以或许匀称地分布在数组的每个位置上。如果键的哈希值已经在数组中存在，其对应的值将被新值覆盖。
HashMap 的初始容量是 16，随着元素的不断添加，HashMap 就需要举行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。扩容后的数组大小是原来的 2 倍，然后把原来的元素重新盘算哈希值，放到新的数组中。
9、你对红黑树了解多少？

红黑树是一种自平衡的二叉查找树：

• 左根右；
  
• 根叶黑；
  
• 不红红；
  
• 黑路同；
  
  
  
  

9.1 为什么不用二叉树？

二叉树是最根本的树布局，每个节点最多有两个子节点，但是二叉树容易出现极端情况，比如插入的数据是有序的，那么二叉树就会退化成链表，查询服从就会酿成 O(n)。
9.2 为什么不用平衡二叉树？

平衡二叉树比红黑树的要求更高，每个节点的左右子树的高度最多相差 1，这种高度的平衡包管了极佳的查找服从，但在举行插入和删除操作时，大概需要频繁地举行旋转来维持树的平衡，维护本钱更高。
9.3 为什么用红黑树？

链表的查找时间复杂度是 O(n)，当链表长度较长时，查找性能会下降。红黑树是一种折中的方案，查找、插入、删除的时间复杂度都是 O(log n)。
9.4 红黑树插入删除规则？

​默认新节点为红色：
​插入逻辑：若插入后破坏红黑性子：
​情况1：父节点为玄色 → 无需调整。
​情况2：父节点为红色，递归调整。
删除逻辑：更复杂，需处理黑节点删除后的黑高淘汰问题。
10、红黑树怎么保持平衡的？

旋转和染色：

• 旋转：通过左旋和右旋来调整树的布局，避免某一侧过深。
  
• 染⾊：修复红黑规则，从而包管树的高度不会失衡。
  

11、HashMap 的 put 流程知道吗？

• 起首盘算键的哈希值，通过 hashCode() 高位运算和扰动函数，淘汰哈希冲突。
  
• 举行第一次的数组扩容，确定桶的位置，根据哈希值按位盘算数组索引。
  
• 处理键值对，若桶为空，直接插入新节点。若桶不为空，判断当前位置第一个节点是否与新节点的 key 相同，如果相同则更新 value，如果差别阐明发生哈希冲突，如果是链表，将新节点添加到链表的尾部；如果链表长度大于即是 8，则将链表转换为红黑树。
  
• 查抄容量并扩容，插入后若 size > threshold (capacity * loadFactor)，则扩容为原容量的两倍。并且重新盘算每个节点的索引，数据将会重新分布。
  

11.1 只重写元素的 equals 方法没重写 hashCode，put 的时候会发生什么?

如果只重写 equals 方法，没有重写 hashCode 方法，那么会导致 equals 相等的两个对象，hashCode 不相等，这样的话，两个对象会被 put 到数组中差别的位置，size + 1，导致大量哈希冲突，退化成链表，查询服从降为 O(n)。
12、HashMap 怎么查找元素的呢？

通过哈希值定位索引 → 定位桶 → 查抄第一个节点 → 遍历链表或红黑树查找 → 返回效果。

13、HashMap 的 hash 函数是怎么设计的?

先拿到 key 的哈希值，是一个 32 位的 int 类型数值，然后再让哈希值的高 16 位和低 16 位举行异或操作，这样能包管哈希分布匀称，淘汰哈希冲突。
14、为什么 hash 函数，能淘汰哈希冲突？

哈希函数通过异或操作将哈希值的高位引入低位，可以增加哈希值的随机性，从而淘汰哈希冲突。将哈希值无符号右移 16 位，意味着原哈希值的高 16 位被移到了低 16 位的位置。这样，原哈希值的高 16 位和低 16 位就可以参与到终极用于索引盘算的低位中。选择 16 位是因为它是 32 位整数的一半，这样处理既考虑了高位的信息，又没有完全忽视低位的信息，从而达到了一种微妙的平衡状态。
15、为什么 HashMap 的容量是 2 的幂次方？

是为了快速定位元素在底层数组中的下标。HashMap 是通过 hash & (n - 1) 来定位元素下标的，n 为数组的大小，也就是 HashMap 底层数组的容量。数组长度 - 1 正好相当于一个低位掩码。掩码的低位最好满是 1，这样 & 运算才有意义，否则最后一位效果肯定是 0。 2 的幂次方刚好是偶数，偶数 - 1 是奇数，奇数的二进制最后一位是 1，也就包管了 hash & (n - 1) 的最后一位大概为 0，也大概为 1（取决于 hash 的值），这样可以包管哈希值的匀称分布。
15.1 对数组长度取模定位数组下标，这块有没有优化策略？

HashMap 的策略是将取模运算优化为位运算 hash & (n - 1)。因为当数组的长度是 2 的 N 次幂时，hash & (n - 1) = hash % n。位运算的速率要远高于取余运算，因为盘算机本质上是二进制的。
15.2 说说什么是取模运算？

在 Java 中，通常使用 % 运算符来表现取余，用 Math.floorMod() 来表现取模。当操作数都是正数的话，取模运算和取余运算的效果是一样的；只有操作数出现负数的情况下，效果才会差别。当数组的长度是 2 的 n 次幂时，取模运算/取余运算可以用位运算来取代，服从更高，因为盘算机本质上二进制的。
16、如果初始化 HashMap，传一个 17 的容量，它会怎么处理？

HashMap 会将容量调整到大于即是 17 的最小的 2 的幂次方，也就是 32。这是因为哈希表的大小最好是 2 的 N 次幂，这样可以通过 hash & (n - 1) 高效盘算出索引值。
17、你还知道哪些哈希函数的构造方法呢？

• 除留取余法：取 key 除以一个不大于哈希表长度的正整数 p，所得余数为所在。
  
• 直接定址法：取 key 映射到对应的数组位置，比方 12345 放到索引为 12345 的位置。
  
• 数字分析法：取 key 的某些数字作为映射的位置。
  
• 平方取中法：取 key 平方的中间几位作为映射的位置。
  
• 折叠相加法：取 key 分割成位数相同的几段，然后把它们的叠加和作为映射的位置。
  
  

18、解决哈希冲突有哪些方法？

• 链所在法：当发生哈希冲突的时候，使用链表将冲突的元素串起来。
  
• 再哈希法：当发生哈希冲突的时候，使用另外一种哈希算法，直到找到空槽。
  
• 开放寻址法：遇到哈希冲突的时候，就去寻找下一个空的槽：
  

• 线性探测：从冲突的位置开始，依次今后找，直到找到空槽。
  
• 二次探测：从冲突的位置开始，第一次增加 2 个位置，第二次增加 4，第三次增加 9 个，直到找到空槽。
  

19、为什么 HashMap 链表转红黑树的阈值为 8 呢？

树化发生在 table 数组的长度大于 64，且链表的长度大于 8 的时候。阈值选择 8 跟统计学有关，源码注释给出的回答是：抱负情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为 8 的情况，发生概率仅为小数点后八位。至于红黑树转回链表的阈值为什么是 6，而不是 8？是因为如果这个阈值也设置成 8，假如发生碰撞，节点增减刚好在 8 附近，会发生链表和红黑树的不断转换，导致资源浪费。
20、HashMap扩容发生在什么时候呢？

当键值对数量超过阈值，也就是容量(默认：16) * 负载因子(默认：0.75)时。
20.1 为什么使用 1 << 4 而不是直接写 16？

起首是为了夸大这个值是 2 的幂次方，而不是一个完全随机的选择。然后是为了通过位运算符快速盘算索引。
20.2 为什么选择 0.75 作为 HashMap 的默认负载因子呢？

这是一个经验值。如果设置得太低，如 0.5，会浪费空间；如果设置得太高，如 0.9，会增加哈希冲突。0.75 是 JDK 作者经过大量验证后得出的最优解，可以或许最大限度淘汰 rehash 的次数。
21、HashMap的扩容机制了解吗？

扩容时，HashMap 会创建一个新数组，其容量是原来的两倍。然后遍历旧哈希表中的元素，将其重新分配到新的哈希表中。如果当前桶中只有一个元素，那么直接通过键的哈希值与新数组的大小取模锁定新的索引位置。如果当前桶是红黑树，那么会调用 split() 方法分裂树节点，以包管树的平衡。如果当前桶是链表，会通过旧键的哈希值与旧的数组大小取余 == 0 来判断，如果条件为真，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。
21.1 JDK 7 扩容的时候有什么问题？

JDK 7 在扩容的时候使用头插法来重新插入链表节点，这样会导致链表无法保持原有的次序。
21.2 JDK 8 是怎么解决这个问题的？

JDK 8 改用了尾插法，并且当 (e.hash & oldCap) == 0 时，元素保留在原索引的位置；否则元素移动到原索引 + 旧数组大小的位置。这样可以避免重新盘算全部元素的哈希值，只需查抄高位的某一位，就可以快速确定新位置。
22、JDK 8 对 HashMap 做了哪些优化呢？

• 底层数据布局由数组 + 链表改成了数组 + 链表或红黑树的布局。
  
• 链表的插入方式由头插法改为了尾插法。头插法在扩容后容易改变原来链表的次序。
  
• 扩容的时机由插入时判断改为插入后判断，这样可以避免在每次插入时都举行不必要的扩容查抄，因为有大概插入后仍然不需要扩容。
  
• 哈希扰动算法也举行了优化。JDK 7 是通过多次移位和异或运算来实现的。JDK 8 让 hash 值的高 16 位和低 16 位举行了异或运算，让高位的信息也能参与到低位的盘算中，这样可以极大水平上淘汰哈希碰撞。
  

23、你能自己设计实现一个 HashMap 吗？

可以，我先说一下整体的设计思路：

• 第一步，实现一个 hash 函数，对键的 hashCode 举行扰动。
  
• 第二步，实现一个链所在法的方法来解决哈希冲突。
  
• 第三步，扩容后，重新盘算哈希值，将元素放到新的数组中。
  

24、HashMap 是线程安全的吗？

HashMap 不是线程安全的，紧张有以下几个问题：

• 多线程下扩容会死循环。JDK7 中的 HashMap 使用的是头插法来处理链表，在多线程环境下扩容会出现环形链表，造成死循环。不外，JDK 8 时通过尾插法修复了这个问题，扩容时会保持链表原来的次序。
  
• 多线程在举行 put 元素的时候，大概会导致元素丢失。因为盘算出来的位置大概会被其他线程覆盖掉。
  
• 多线程在举行 get 元素的时候，大概导致 get 为 null。因为其他线程大概先执行 put ，导致容量超出阈值从而扩容。
  

25、怎么解决 HashMap 线程不安全的问题呢？

• 可以用 Hashtable 来包管线程安全。Hashtable 在方法上加了 synchronized 关键字。
  
• 可以通过 Collections.synchronizedMap 方法返回一个线程安全的 Map，内部是通过 synchronized 对象锁来包管线程安全的，比在方法上直接加 synchronized 关键字更轻量级。
  
• 可以使用并发工具包下的 ConcurrentHashMap，使用了CAS + synchronized 关键字来包管线程安全。
  

26、HashMap 内部节点是有序的吗？

无序的，根据 hash 值随机插入。
27、讲讲 LinkedHashMap 怎么实现有序的？

LinkedHashMap 在 HashMap 的基础上维护了一个双向链表，通过 before 和 after 标识前置节点和后置节点。实现了次序读写。
28、讲讲 TreeMap 怎么实现有序的？

TreeMap 通过 key 的比较器来决定元素的次序，如果没有指定比较器，那么 key 必须实现 Comparable 接口。TreeMap 的底层是红黑树，红黑树是一种自平衡的二叉查找树。插入或删除元素时通过旋转和染色来保持树的平衡。查找的时候从根节点开始，利用二叉查找树的特点，渐渐向左子树或者右子树递归查找，直到找到目的元素。

29、TreeMap 和 HashMap 的区别？

• HashMap 是基于数组 + 链表 + 红黑树实现的，put 元素的时候会先盘算 key 的哈希值，然后通过哈希值盘算出元素在数组中的存放下标，然后将元素插入到指定的位置，如果发生哈希冲突，会使用链表来解决，如果链表长度大于 8，会转换为红黑树。
  
• TreeMap 是基于红黑树实现的，put 元素的时候会先判断根节点是否为空，如果为空，直接插入到根节点，如果不为空，会通过 key 的比较器来判断元素应该插入到左子树还是右子树。
  

在没有哈希冲突的情况下，HashMap 的查找服从是 O(1)。适用于查找操作比较频繁的场景。TreeMap 的查找服从是 O(logn)。并且包管了元素的次序，因此适用于需要大范围查找或者有序遍历的场景。
30、讲讲 HashSet 的底层实现？

HashSet 的底层实际是一个 HashMap 实例，其中 key 是用户添加的元素（如 String、Integer）。value 是一个固定的静态 Object 类型 PRESENT 对象。HashSet 紧张用于去重，HashMap 的 put() 方法会覆盖旧值，但 HashSet 的 add() 方法会返回 false，且集合内容稳定。

30.1 HashSet 和 ArrayList 的区别？

• ArrayList 是基于动态数组实现的，HashSet 是基于 HashMap 实现的。
  
• ArrayList 可以有多个相同的元素；HashSet 不允许重复元素，通过 hashCode() 和 equals() 联合判断重复。
  
• ArrayList 保持元素的插入次序，可以通过索引访问元素；HashSet 不包管元素的次序，元素的存储次序依赖于哈希算法，并且大概随着元素的增删而改变。
  

30.2 HashSet 怎么判断元素重复，重复了是否 put ？

判断重复：通过 hashCode() 和 equals() 联合判断。
​重复处理：不覆盖，直接忽略，返回 false。若需要更新元素，需先删除旧元素再添加新元素。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。