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 扩容几次？
该语句只是声明和实例了一个 ArrayList，指定容量为 10，未进行扩容。参考源码：
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } }
4.2.2.3 如何实现数组和 List 之间的转换？
数组转 List，使用 Arrays 工具类的
asList方法。用
asList转 list 后，如果修改了数组，list 会受影响。因为底层构造器仅把集合进行了包装，但指向的是同一个内存地址。List 转数组，使用 List 工具类的
toArray方法。用
toArray转数组后，如果修改了 list，数组不会影响。因为底层进行了数组的拷贝，跟原来的元素没啥关系了。
4.2.2.4 ArrayList 和 LinkedList 的区别是什么？
特性 ArrayList LinkedList 底层数据结构 动态数组 双向链表 查找效率 O(1) O(n) 插入与删除效率 O(n) O(1) 内存使用 低（仅存储数据） 较高（需存储指针） 适用场景 读多写少 写多读少
4.2.2.5 ArrayList 和 LinkedList 不是线程安全的，如何解决？
ArrayList和LinkedList在单线程下表现良好，但在多线程下，由于缺乏必要的同步措施，会导致数据不一致和竞态条件。解决方案：
使用同步包装器：
Collections.synchronizedList方法可以将任何List实例包装成一个线程安全的列表。List list = Collections.synchronizedList(new ArrayList());使用并发集合：
CopyOnWriteArrayList适用于读多写少的场景，写操作时会复制整个底层数组，因此读操作不需要加锁。List list = new CopyOnWriteArrayList();手动同步：在操作列表时，可以在代码块外部使用
synchronized关键字或ReentrantLock来手动同步。public void addElement(Object element) { synchronized (list) { list.add(element); } }使用原子操作类：对于简单的添加和删除操作，可以使用原子操作类，如
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。Map map = Collections.synchronizedMap(new HashMap());使用使用并发集合：
ConcurrentHashMap是HashMap的线程安全替代品，它通过分段锁（Segment）来提高并发性能。Map map = new ConcurrentHashMap();手动同步：在操作
HashMap时，可以在代码块外部使用synchronized关键字或ReentrantLock来手动同步。public void putElement(Object key, Object value) { synchronized (map) { map.put(key, value); } }
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 class Shape { // 基类 void draw() { System.out.println("Drawing a shape"); } } class Circle extends Shape { // 派生类 @Override void draw() { System.out.println("Drawing a circle"); } } ```
平台无关性：
Java代码可以“一次编写，到处运行”（Write Once, Run Anywhere，简称WORA）。
Java源代码被编译成平台无关的字节码文件，这些字节码可以在任何安装了JVM的设备上运行。
- JVM负责将字节码转换为特定平台的机器码，从而实现跨平台运行。
健壮性：
Java的设计目标之一是创建一种能够自动检测程序错误和异常的语言。
Java还有自动垃圾回收机制，帮助开发者管理内存，减少了内存泄漏和其他内存管理错误。
异常处理机制允许程序在遇到错误时优雅地恢复，而不是直接崩溃。
4.2.4.6 String \ StringBuilder \ StringBuffer 有什么区别？
String是不可变的，每次修改都会生成新的字符串对象。StringBuilder是可变的，可以在原有基础上进行修改，是非线程安全的。StringBuffer也是可变的，但它是线程安全的。
4.2.4.7 Java 类的初始化，父类与子类，静态成员？
1. Java 如何初始化一个类？
通过创建对象或访问静态成员来初始化类。
MyClass myObject = new MyClass();System.out.println(MyClass.staticVar);2. 父类、子类哪个先初始化？
父类先于子类初始化。
class Parent { static {System.out.println("Parent static block is called");} }class Child extends Parent { static {System.out.println("Child static block is called");} }3. 静态代码块、构造函数哪个先执行？
静态代码块先于构造函数执行，静态代码块在类加载时执行，而构造函数在创建对象时执行。
public class MyClass { static {System.out.println("Static block is called");} public MyClass() {System.out.println("Constructor is called");} }
