面试题（拓展知识）

自己在准备面试/复习的时候，整理了一些高频面试题的拓展题部分，如有错误欢迎指正哦。

1. 为什么链表转红黑树的阈值是8？链表长度为8就一定会变成红黑树吗？

链表转红黑树的阈值设定为8并不意味着链表长度达到8时一定会转为红黑树。

1. 阈值8的设计原因

• 时间复杂度的考虑：在哈希冲突发生时，HashMap 会将多个键值对存储在同一个桶中（即同一个链表）。链表的查找时间复杂度是 O(n)，而红黑树的查找时间复杂度是 O(log n)。当链表长度较小时，链表操作的开销比较小，直接遍历即可；但当链表长度较大时，红黑树的查找效率更高。
• 统计分析：在大多数应用场景中，哈希冲突导致的链表长度通常不会很长。研究和实践表明，链表长度超过8的情况非常少见。如果链表长度超过8，说明哈希冲突较为严重，此时使用红黑树替代链表。

2. 链表长度为8就一定会变成红黑树吗？

不一定。链表长度达到8只是触发链表转红黑树的条件之一，但还需要满足以下两个条件：

• HashMap容量扩容条件：当链表长度达到阈值8时，HashMap 会首先判断当前的哈希表容量是否大于或等于 64。如果小于 64，则优先进行扩容操作，而不是直接转换为红黑树。这是因为扩容可以减少哈希冲突的发生，从而缩短链表长度。因此，只有在容量达到64且链表长度超过8时，链表才会真正转换为红黑树。
• 操作类型：在实际操作中，HashMap 会在插入新元素时检查链表的长度。如果链表长度达到阈值8，并且经过扩容后冲突仍然存在，则会将该链表转换为红黑树。

2. 解决Hash冲突的方法有哪些？

1. 开放地址法（Open Addressing）

开放地址法通过寻找哈希表中下一个可用位置来解决冲突。

• 线性探测法（Linear Probing）：

  • 当冲突发生时，直接检查哈希表中下一个位置（即当前索引+1的位置），直到找到一个空位置。
  • 优点：实现简单。
  • 缺点：当冲突多时容易导致“聚集”现象，即多个冲突的元素集中在一起，导致查找效率下降。

• 二次探测法（Quadratic Probing）：

  • 当冲突发生时，按照二次方间隔来寻找下一个位置（例如，+1、+4、+9……）。
  • 优点：减少了线性探测法的“聚集”现象。
  • 缺点：实现稍复杂，如果装载因子较高，仍然可能出现冲突。

• 双重散列法（Double Hashing）：

  • 使用两个不同的哈希函数来计算索引，如果第一个哈希函数发生冲突，使用第二个哈希函数计算步长进行探测。
  • 优点：减少了聚集效应，提高了查找效率。
  • 缺点：实现较为复杂，需要设计两个合适的哈希函数。

2. 链地址法（Separate Chaining）

链地址法通过为每个桶存储一个链表（或其他数据结构）来解决冲突。

• 基本原理：所有哈希到同一位置的元素都被存储在同一个链表中，发生冲突时，新的元素直接追加到链表的末尾。
• 优点：
  • 容量不受哈希表大小限制，可以处理较大的数据集。
  • 实现简单，容易扩展和管理。
• 缺点：
  • 在哈希冲突较多的情况下，链表的查找效率会下降到 O(n)。
  • 需要额外的指针空间存储链表节点。

3. 再哈希法（Rehashing）

再哈希法使用一系列不同的哈希函数来处理冲突。

• 基本原理：当初始哈希函数计算的索引发生冲突时，使用另一个哈希函数重新计算新的索引位置。
• 优点：减少了冲突的可能性，可以有效避免聚集现象。
• 缺点：需要设计多个哈希函数，增加了实现复杂度。

4. 建立公共溢出区

将所有发生冲突的元素存储到一个单独的溢出区中。

• 基本原理：哈希表和溢出区相结合，哈希表中发生冲突的元素不再放在哈希表中，而是放到溢出区的一个链表或数组中。
• 优点：处理简单，适用于冲突较多但溢出元素较少的场景。
• 缺点：溢出区可能成为性能瓶颈，因为所有冲突元素都在同一个区域，查找效率可能下降。

5. 扩展的线性探测法

扩展线性探测法是线性探测法的扩展和改进版本。

• 基本原理：类似于线性探测法，但探测步长不是固定的1，而是以某种规律变化，例如步长按某种递增规律变化（如1, 3, 7, 15…）。
• 优点：减少聚集效应，提高查找效率。
• 缺点：实现复杂，需要设计合理的步长规则。

6. Cuckoo Hashing（布谷鸟哈希）

一种较为现代的冲突解决方法，利用两个或更多的哈希表和哈希函数。

• 基本原理：每个元素通过两个不同的哈希函数映射到两个不同的哈希表中。如果插入一个新元素时，某个位置已经被占用，则将被占用位置上的元素“踢出”，并重新放入另一个哈希表，依此类推。
• 优点：查找时间复杂度为 O(1)，哈希表使用率较高。
• 缺点：可能需要频繁“踢出”元素，导致插入操作复杂度较高。

3. 什么样的对象算垃圾？如果对象被标记成了垃圾，还能逃逸吗？

在Java中，垃圾收集（Garbage Collection, GC）是自动管理内存的一种机制，它会自动识别并清理不再使用的对象，以释放内存资源。

1. 什么样的对象算是垃圾？

一个对象被认为是垃圾，通常是指该对象不再被任何活动的线程或其他对象引用，即在程序的运行中已经无法再访问到这个对象。

2. 对象被标记为垃圾后还能逃逸吗？

对象被标记为垃圾后，理论上它应该被回收，不能再逃逸。但在特殊情况下，对象可能会暂时“逃逸”：

Finalize方法：如果一个类重写了 finalize() 方法，垃圾收集器在标记对象为垃圾后，可能会在回收前调用 finalize() 方法。如果在 finalize() 方法中，重新建立了对象与根对象之间的引用链，理论上该对象就从“垃圾”状态“逃逸”了，变得不可回收。不过，在实际应用中，依赖 finalize() 机制是很不安全的做法，而且Java 9以后也逐渐废弃了这一机制，建议使用try-with-resources或Cleaner来替代。

3. 简洁回答：

垃圾对象：无法再被任何引用链访问到的对象，被认为是垃圾。
逃逸的可能性：被标记为垃圾的对象在正常情况下会被回收，但在特殊情况下（如 finalize() 方法），对象可能会暂时逃逸。不过，这种情况并不常见，且不推荐依赖此机制。

4. 讲讲CAS的原理？什么是ABA问题？怎么解决？

1. CAS（Compare-And-Swap）的原理

Compare-And-Swap（CAS） 是一种用于实现同步原子操作的硬件级别指令，在并发编程中被广泛应用。CAS操作包括以下三个操作数：

• V：表示需要读写的内存值。
• A：表示进行比较的值。
• B：表示需要写入的新值。

CAS操作的原理，简单描述为：

1. 读取当前值 V。
2. 比较 V 和 A：
   • 如果 V == A，则将 B 写入到 V，并返回 true，表示操作成功。
   • 如果 V != A，则不进行任何操作，返回 false，表示操作失败。

CAS操作具有原子性，即在执行CAS时不会被其他线程打断，因此它常用于实现无锁（lock-free）的线程安全操作。CAS是现代多处理器系统中原子操作的核心基础，通常被用来实现乐观锁（Optimistic Locking）等机制。

2. ABA问题

ABA问题是在使用CAS操作时可能出现的一个经典问题。

问题描述：

• 线程 T1 读取变量 V 的值为 A。
• 在 T1 准备使用 CAS 更新 V 时，线程 T2 把 V 的值从 A 变成了 B，然后又变回 A。
• 现在 T1 继续执行，CAS 操作发现 V 的值仍然是 A，认为没有变化，于是成功地将 V 的值更新为 B。

从 T1 的视角来看，V 的值似乎一直是 A，而实际上它已经被其他线程修改过。这种情况下，虽然CAS操作成功了，但实际上 T1 并不知道变量 V 的值已经经历过了变化。

3. 如何解决ABA问题

1. 使用版本号/时间戳

一种简单有效的解决办法是在变量 V 中附加一个版本号或时间戳，进行每次更新时，版本号都会增加。这样即使 V 的值从 A 变成 B 又变回 A，版本号也会发生变化，因此可以有效识别出变量是否经历了其他变化。

示例：

• 初始状态：V = A1 （其中 1 是版本号）
• 线程 T2 把 V 从 A1 改成 B2，再改回 A3。
• 线程 T1 再次检查时，发现版本号从 1 变成了 3，知道 V 已经被修改过，因此不会执行错误的 CAS 操作。

在Java中，java.util.concurrent.atomic.AtomicStampedReference 就是这种解决方案的实现。它通过引入“时间戳”来解决ABA问题。

2. 使用 Lock-Free 数据结构

现代的JDK提供了一些无锁的、带有对ABA问题处理的数据结构，例如 AtomicMarkableReference，可以在对象的引用中附加一个标记位，以区分对象的状态变化。这种方式类似于版本号的策略。

3. 增加CAS重试机制

尽管增加重试机制不能根本解决ABA问题，但在某些特定的应用场景中，通过增加CAS操作的重试次数来降低ABA问题发生的概率。该机制的基本思想是在检测到可能的ABA问题时，再次进行CAS操作，从而使系统达到预期的正确状态。

5. Java 和 Golang 的区别

1. ​设计理念​：
   • ​Java​：是一种面向对象的编程语言，强调类和对象的使用，通过Java虚拟机（JVM）实现跨平台运行。它拥有丰富且成熟的标准库，适合开发大型企业级应用。
   • ​Go​：注重简洁和高效，减少了复杂的语法和特性。Go内置对并发的支持，通过goroutine和channel实现轻量级并发，编译速度非常快，适合快速开发和部署。
2. ​语法和类型系统​：
   • ​Java​：是强类型语言，支持复杂的面向对象特性，如继承、多态、接口和泛型。异常处理通过try-catch块进行。
   • ​Go​：也是静态类型语言，但语法更简洁。没有类的概念，使用结构体和接口来实现面向对象编程，错误处理通过返回值而不是异常机制。
3. ​内存管理​：
   • ​Java​：使用JVM的垃圾回收机制自动管理内存，有复杂的内存模型和对象生命周期管理。
   • ​Go​：也有垃圾回收机制，但设计更简单高效，内存分配和管理更加直接。
4. ​并发模型​：
   • ​Java​：使用操作系统的线程来实现并发，线程的创建和管理开销较大。提供了丰富的并发工具类，如java.util.concurrent包。
   • ​Go​：使用goroutine实现轻量级并发，创建和切换开销非常小，通过channel实现goroutine之间的通信和同步，简化了并发编程。
5. ​应用场景​：
   • ​Java​：广泛应用于大型企业级应用开发，如银行系统、电信系统等。也是Android应用开发的主要语言，并在大数据领域有广泛应用，如Hadoop生态系统。
   • ​Go​：在云计算和微服务领域非常流行，许多现代云原生项目使用Go开发，如Docker和Kubernetes。适用于系统编程和网络编程，因其高效的性能和并发模型。

6. 雪花算法

雪花算法（Snowflake Algorithm）是一种用于生成全局唯一 ID 的算法。

雪花算法原理

雪花算法生成的 ID 是一个 64 位的长整型数：

• 符号位（1 位）： 总是 0，表示正数。
• 时间戳部分（41 位）： 当前时间戳（毫秒）减去一个固定的起始时间。这个部分提供了大约 69 年的时间范围。
• 工作机器 ID（10 位）： 分布式系统中每个节点的唯一标识。通常是机器 ID 或进程 ID。可以支持最多 1024 个节点。
• 序列号（12 位）： 每毫秒内生成的序列号，支持每毫秒生成 4096 个唯一 ID。

7. 二叉搜索树思想，如何快速看出是不是二叉搜索树

二叉搜索树是一个满足以下条件的二叉树：

1. 每个节点的值都大于其左子树所有节点的值。
2. 每个节点的值都小于其右子树所有节点的值。
3. 左右子树也必须是二叉搜索树。

可以使用中序遍历来初步判断，如果是升序就可能是二叉搜索树。

8. 常见的服务器负载均衡方法

1. 轮询 (Round Robin)

• 原理：将请求按顺序分配给服务器池中的每个服务器，轮流处理请求。
• 优点：简单易实现，适用于服务器性能相似的场景。
• 缺点：不考虑服务器负载或健康状况，可能导致性能不均衡。

2. 加权轮询 (Weighted Round Robin)

• 原理：与轮询类似，但为每台服务器分配不同的权重，权重较高的服务器会处理更多的请求。
• 优点：可以根据服务器性能调整负载分配。
• 缺点：需要手动设置权重，可能需要监控服务器性能来调整权重。

3. 最少连接 (Least Connections)

• 原理：将请求分配给当前连接数最少的服务器。
• 优点：适用于请求处理时间不均的场景，可以平衡服务器负载。
• 缺点：需要监控每台服务器的连接数，可能增加负载均衡器的复杂度。

4. 加权最少连接 (Weighted Least Connections)

• 原理：与最少连接类似，但结合了服务器的权重。服务器的权重和当前连接数共同决定负载分配。
• 优点：可以更精确地平衡负载，适用于服务器性能差异较大的场景。
• 缺点：需要管理和计算服务器的权重。

5. IP 哈希 (IP Hash)

• 原理：通过对客户端的 IP 地址进行哈希运算，将请求分配到特定的服务器。相同 IP 地址的请求会被分配到同一台服务器。
• 优点：可以保持会话的粘性，适用于需要会话保持的场景。
• 缺点：客户端 IP 地址变更时会导致请求分配改变。

6. 会话粘性 (Session Persistence 或 Sticky Sessions)

• 原理：确保来自同一客户端的请求始终分配给同一台服务器。可以通过 cookie、会话 ID 或其他标识符实现。
• 优点：适用于需要保持用户会话状态的应用场景。
• 缺点：可能导致负载不均，特别是在某些服务器承担较多会话的情况下。

7. 基于内容的路由 (Content-Based Routing)

• 原理：根据请求的内容（如 URL、HTTP 头部、请求参数）将请求路由到不同的服务器或服务器池。
• 优点：可以根据请求内容优化处理流程，适用于需要不同处理逻辑的应用。
• 缺点：需要额外的处理和配置，可能增加系统复杂性。

8. 资源使用 (Resource-Based)

• 原理：根据服务器的资源使用情况（如 CPU、内存、磁盘 I/O）来分配请求。
• 优点：可以动态平衡负载，适应服务器负载的变化。
• 缺点：需要实时监控资源使用情况，并且对负载均衡器要求较高。

9. 地理位置 (Geographic-Based)

• 原理：根据客户端的地理位置将请求分配到离客户端最近的服务器。
• 优点：可以减少网络延迟，提高用户体验。
• 缺点：需要地理位置的检测和配置，可能增加系统的复杂性。