Java 八股文：集合篇

4 - 集合篇

4.1 集合基础

4.1.1 算法复杂度

**时间复杂度：**表示算法的执行时间与数据规模之间的增长关系。常见：O(1)、O(logn)、O(n)、O(n^2)、O(n!)。找出算法中重复执行的基本操作，如循环、递归等。分析基本操作在不同输入规模下的执行次数。将基本操作的执行次数用大O表示法表示出来，忽略常数因子和低阶项。
**空间复杂度：**表示算法的存储空间与数据规模之间的增长关系。常见：O(1)、O(n)、O(n ^2)。找出算法中使用的额外空间，如变量、数据结构等。分析额外空间在不同输入规模下的使用量。将空间使用量用大O表示法表示出来，忽略常数因子和低阶项。

4.1.2 List 相关

4.1.2.1 数组

数组的下标为什么从 0 开始？因为寻址公式是：baseAddress + i * dataTypeSize，这样计算下标的内存地址效率较高。
数组查找的时间复杂度？已知下标，查找元素的时间复杂度是 O(1)未知下标，查找元素的时间复杂度是 O(n)未知下标但排序，二分查找元素的时间复杂度是 O(logn)
数组插入和删除的时间复杂度？为了保证数组的内存连续性，需要挪动数组元素，平均时间复杂度为 O(n)

4.1.2.2 链表

单向链表和双向链表的区别是什么？单向链表只有一个方向，结点只有一个后继指针 next。双向链表支持两个方向，结点不止有一个后继指针 next，还有一个前驱指针 prev。
链表操作数据的时间复杂度是多少？单向链表的增删查：头节点 O(1)，其他节点 O(n)。双向链表的增删查：头尾节点 O(1)，其他节点 O(n)，给定节点 O(1)。

4.1.3 HashMap 相关

4.1.3.1 二叉树

什么是二叉树？
每个节点最多有两个 “叉”，分别是左子节点和右子节点。
不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。
二叉树每个节点的左子树和右子树也分别满足二叉树的定义。
什么是二叉搜索树？
二叉搜索树（Binary Search Tree，BST）又名二叉查找树，有序二叉树。
左子树中的每个节点的值都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
通常情况下时间复杂度为 O(logn)。
什么是红黑树？
红黑树（Red Black Tree）是一种自平衡的二叉搜索树。
时间复杂度：查找、添加、删除都是 O(logn)。

4.1.3.2 散列表

什么是散列表？
散列表又称哈希表，由数组演化而来。根据 key 访问内存下标 value 的数据结构。
什么是散列冲突？
散列冲突又称哈希冲突，哈希碰撞。指多个 key 映射到同一个数组下标 value。
什么是拉链法？
数组的每个下标位置称为桶，每个桶对应一条链表。冲突后的元素都放到对应的链表或红黑树中。

4.2 集合面试题

4.2.1 常见集合类

单列集合：Vector：动态数组，ArrayList：动态数组，LinkedList：双向链表，HashSet：哈希表，TreeSet：红黑树。
双列集合：Hashtable：哈希表，HashMap：哈希表，ConcurrentHashMap：哈希表，TreeMap：红黑树。

4.2.2 List 相关

4.2.2.1 ArrayList 的底层原理？

数据结构：ArrayList 底层是用动态数组实现的。
初始容量：ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10。
扩容逻辑：ArrayList 在进行扩容的时候是原来容量的 1.5 倍，每次扩容都需要拷贝数组。
添加逻辑：确保数组已使用长度 size + 1 后足够存下一个数据。如果数组已使用长度 size + 1 后大于当前数组长度，则调用 grow 方法扩容。确保新元素有地方存储之后，将新元素添加到位于 size 的位置上，返回 true。

4.2.2.2 ArrayList list = new ArrayList(10) 中的 List 扩容几次？

4.2.2.3 如何实现数组和 List 之间的转换？

数组转 List，使用 Arrays 工具类的 asList 方法。用 asList 转 list 后，如果修改了数组，list 会受影响。因为底层构造器仅把集合进行了包装，但指向的是同一个内存地址。
List 转数组，使用 List 工具类的 toArray 方法。用 toArray 转数组后，如果修改了 list，数组不会影响。因为底层进行了数组的拷贝，跟原来的元素没啥关系了。

4.2.2.4 ArrayList 和 LinkedList 的区别是什么？

4.2.2.5 ArrayList 和 LinkedList 不是线程安全的，如何解决？

ArrayList 和 LinkedList 在单线程下表现良好，但在多线程下，由于缺乏必要的同步措施，会导致数据不一致和竞态条件。
解决方案：
使用同步包装器：Collections.synchronizedList 方法可以将任何 List 实例包装成一个线程安全的列表。
使用并发集合：CopyOnWriteArrayList 适用于读多写少的场景，写操作时会复制整个底层数组，因此读操作不需要加锁。
**手动同步：**在操作列表时，可以在代码块外部使用 synchronized 关键字或 ReentrantLock 来手动同步。
**使用原子操作类：**对于简单的添加和删除操作，可以使用原子操作类，如 AtomicIntegerArray 或 AtomicReferenceArray。

4.2.2.6 CopyOnWriteArrayList 底层原理？

初始容量：如果没有指定初始容量，那么CopyOnWriteArrayList会使用一个空数组来初始化。
扩容机制：加锁，以确保在扩容过程中不会有其他线程修改数组。创建一个新数组，其长度为原数组长度加 1。将原数组中的所有元素拷贝到新数组中。释放锁。使用volatile关键字修饰的成员变量更新为新数组，确保内存可见性。
线程安全保证：使用ReentrantLock加锁，确保在写操作过程中，同一时间只有一个线程能够修改数组，从而保证线程安全。使用volatile关键字修饰数组，确保当数组被重新赋值后，其他线程能够及时感知到这一变化。

4.2.3 HashMap 相关

4.2.3.1 HashMap 的底层原理？

HashMap 的数据结构：在 JDK 1.7 中，是数组加上链表，即每个数组元素是一个链表。当发生哈希冲突时，新的元素会被添加到链表的头部。在 JDK 1.8 中，是数组加上链表或红黑树。当链表的长度超过 8 并且数组的长度超过 64 时，链表会转换成红黑树。
HashMap 的存取过程：通过 hash(key) 方法计算键的哈希值，然后通过哈希值来确定数组中的下标，进而定位到具体的桶（bucket）。如果在该桶中发生哈希冲突，即有其他键具有相同的哈希值，HashMap 会先比较键是否相等。如果键相同，则更新该键对应的值；如果键不同，则将新键值对添加到链表尾部（JDK 1.7）或红黑树中（JDK 1.8）。

4.2.3.3 HashMap 的 put 方法的具体流程？

如果数组为空或 null，则执行 resize() 初始化。
先根据 hash(key) 得到数组下标 i，再进行判断：如果 table[i] 为 null 则直接添加，否则进行判断：如果 key 相同则覆盖，否则存入链表 / 红黑树中。
如果 put 后大小超过了 数组长度 * 0.75，则执行 resize() 扩容。

4.2.3.4 HashMap 的扩容机制？

当向其中添加元素时，如果数组（即哈希表）为空或其大小为 0，则会执行resize()方法，初始化其大小为默认值16。
当 HashMap 中的元素个数超过“数组长度 * 加载因子”时，会触发resize()方法进行扩容。加载因子（load factor）是一个衡量HashMap满的程度的参数，其默认值为0.75。当 HashMap 中的元素个数达到数组长度的75%时，就会进行扩容操作，扩容通常是将数组的大小增加到原来的两倍。
扩容操作会创建一个新的数组，这个新数组的大小是原数组的两倍。然后，原数组中的所有元素会重新计算其在新数组中的索引位置，并移动到新数组中对应的位置上。（rehash）

4.2.3.5 HashMap 的寻址算法？

hashMap 的寻址算法？
先计算对象的 hashCode()，再调用 hash() 二次哈希。
将哈希值右移 16 位与其异或运算，让哈希分布更为均匀。
最后 hash & (capacity – 1)，即取模得到数组下标。
为何 HashMap 的数组长度一定是 2 的次幂？
这样可以使用位与运算 hash & (capacity – 1) 代替取模，效率更高。
扩容时重新计算下标 hash & oldCap == 0 的元素留在原来位置，效率更高。

4.2.3.6 Hashmap 在 JDK1.7 下的多线程死循环问题？

在 JDK 1.7 中，HashMap 是非线程安全的。当多个线程同时修改 HashMap 时，可能会产生死循环。
这个问题是由于 HashMap 在扩容时，节点的重新哈希分配可能会导致循环链。
解决方案：
**使用同步包装器：**类似于列表，可以使用 Collections.synchronizedMap 方法将 HashMap 包装成线程安全的 Map。
使用使用并发集合：ConcurrentHashMap 是 HashMap 的线程安全替代品，它通过分段锁（Segment）来提高并发性能。
**手动同步：**在操作 HashMap 时，可以在代码块外部使用 synchronized 关键字或 ReentrantLock 来手动同步。

4.2.3.7 ConcurrentHashMap 的底层原理？

JDK1.7 的 ConcurrentHashMap 确实采用了 Segment 分段锁机制。它将整个哈希表分割成若干个段（Segment），每个段是一个子哈希表，拥有自己的锁。当对哈希表进行操作时，只需要锁定相关的段，而不是整个哈希表，这样可以减少锁竞争，提高并发访问性能。
JDK1.8 的 ConcurrentHashMap 进行了重大改进，移除了 Segment 分段锁机制。它采用了 CAS（Compare-And-Swap）操作来支持更高的并发，并且只在某些情况下使用 synchronized 锁。ConcurrentHashMap 由数组+链表+红黑树组成。对于链表中的元素，如果遇到哈希冲突，会通过CAS操作来解决。当链表的长度超过一定阈值时，会转换成红黑树，减少搜索时间。对于重要操作（如扩容）才使用 synchronized 锁。

4.2.3.8 == 和 equals 的区别？对象做 HashMap 的 key 时需要做什么处理？

== 和 equals() 的区别：== 是一个操作符，用于比较两个引用是否指向同一个对象实例，即它们是否具有相同的内存地址。equals() 是一个方法，用于比较两个对象的内容是否相等。默认情况下，equals() 方法的行为与 == 相同，即比较引用，但可以通过重写这个方法来比较对象的属性值。
对象作为 HashMap 的 key：重写 equals() 方法：确保当两个对象的属性值相等时，equals() 方法返回 true，以便 HashMap 能够识别出这两个对象是“相等”的。重写 hashCode() 方法：确保当两个对象通过 equals() 方法比较为相等时，它们的哈希码也相同。这是因为 HashMap 依赖于哈希码来快速定位对象存储的位置。如果两个对象的哈希码不同，即使它们的内容相同，也会被存储在 HashMap 的不同位置。

4.2.4 Java 相关

4.2.4.1 java 根类是什么？Object 有哪些方法？

Object 类。equals()、hashCode()、toString()、getClass() 等。

4.2.4.2 介绍一下 JDK 7、JDK 8、JDK 17 新特性？

JDK 7：引入了 try-with-resources、字符串在 switch 语句中的支持、增强的异常处理、Diamond 语法、并发库的改进等。
JDK 8：引入了 Lambda 表达式、Stream API、java.time 包、接口的默认方法和静态方法、Nashorn JavaScript 引擎等。
JDK 17：引入了增强的 Switch 语句、增强的字符串拼接、增强的伪随机数生成器、密封类（sealed classes）等。

4.2.4.3 Java 基本数据类型？数值范围？对应的包装类？32 位和 64 位的 JVM 中 int 的长度？

32 位与 64 位的 jvm 中，int 类型变量的长度是相同的，都是 32 位或者 4 个字节。
byte（1字节，8位）：有符号的整数，-2^(n-1) ~ 2^(n-1)-1。包装类：Byte。
short（2字节，16位）：有符号的整数，-2^(n-1) ~ 2^(n-1)-1。包装类：Short。
int（4字节，32位）：有符号的整数，-2^(n-1) ~ 2^(n-1)-1。包装类：Integer。
long（8字节，64位）：有符号的整数，-2^(n-1) ~ 2^(n-1)-1。包装类：Long。
float（4字节，32位）：单精度浮点数，大约有7位有效数字。包装类：Float。
double（8字节，64位）：双精度浮点数，大约有15位有效数字。包装类：Double。
char（2字节，16位）：无符号的整数，0 ~ 2^n-1。包装类：Character。
boolean：只有两个值，true和false。包装类：Boolean。

4.2.4.4 Java 常见数据结构？

数组（Array）：一种基本的数据结构，用于存储固定大小的同类型元素。
链表（Linked List）：由节点组成的集合，每个节点包含数据部分和指向下一个节点的引用。
栈（Stack）：后进先出（LIFO）的数据结构，通常使用数组或链表实现。
队列（Queue）：先进先出（FIFO）的数据结构，可以是数组、链表或使用优先级队列。
集合（List、Set、Map）：List：允许对元素进行索引的数据结构，常见的实现有ArrayList和LinkedList。Set：存储不重复元素的集合，通常不允许对元素进行索引。Map：存储键值对的数据结构，不允许键重复，常见的实现有HashMap和TreeMap。
树（Tree）：由节点组成的层次结构，每个节点有零个或多个子节点。
图（Graph）：由节点（顶点）和边组成的数据结构，可以表示复杂的关系和网络。

4.2.4.5 Java 三大特性？面向对象的三大特性？

面向对象：Java是面向对象的编程语言，它基于“对象”来设计软件。对象是现实世界中事物的抽象，包含数据（属性）和行为（方法）。继承：允许子类继承父类的属性和方法，支持代码复用。（代码重用）封装：将属性和操作方法捆绑，隐藏内部细节，只能通过类的方法来访问和修改数据。（模块化，提高可读性）多态：同一个接口可以被不同的实例以不同的方式实现。（易于维护和扩展）
平台无关性：Java代码可以“一次编写，到处运行”（Write Once, Run Anywhere，简称WORA）。Java源代码被编译成平台无关的字节码文件，这些字节码可以在任何安装了JVM的设备上运行。JVM负责将字节码转换为特定平台的机器码，从而实现跨平台运行。
健壮性：Java的设计目标之一是创建一种能够自动检测程序错误和异常的语言。Java还有自动垃圾回收机制，帮助开发者管理内存，减少了内存泄漏和其他内存管理错误。异常处理机制允许程序在遇到错误时优雅地恢复，而不是直接崩溃。