新浪面试

链表判环，找入口

思路：

判断是否有环：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果它们相遇，说明有环。
找出环入口：当判断出有环后，将慢指针重新指向头节点，然后快慢指针同时以相同速度移动，再次相遇的节点就是环的入口。

以下是判断链表是否有环以及找出环入口的 Java 代码：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}
 
public class LinkedListCycle {
    // 判断链表是否有环
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
 
    // 找出环的入口
    public ListNode findCycleEntry(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        if (!hasCycle) {
            return null;
        }
        slow = head;
        while (slow!= fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
 
    public static void main(String[] args) {
        // 创建一个有环的链表
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;
 
        LinkedListCycle solution = new LinkedListCycle();
        boolean hasCycle = solution.hasCycle(node1);
        System.out.println("是否有环: " + hasCycle);
        ListNode entry = solution.findCycleEntry(node1);
        if (entry!= null) {
            System.out.println("环的入口节点值: " + entry.val);
        } else {
            System.out.println("无环");
        }
    }
}

Linux 中的进程和线程有什么区别，请详细说明

资源分配：进程是系统进行资源分配和调度的基本单位，每个进程都有独立的地址空间、内存、数据栈等资源。比如一个应用程序启动就是一个进程，它有自己独立的资源环境。而线程是进程中的执行单元，同一进程内的线程共享进程的资源，如地址空间、打开的文件等，它们可以直接访问进程中的数据和代码。
调度：进程调度开销较大，因为涉及到切换进程的资源环境等。而线程调度开销相对较小，主要是切换线程的上下文，如寄存器的值、程序计数器等。
并发性：进程之间可以并发执行，通过进程调度实现多个进程在 CPU 上轮流执行。线程也可以并发执行，而且同一进程内的多个线程之间的并发执行效率更高，因为它们共享资源，不需要进行大量的资源切换。
独立性：进程具有较高的独立性，一个进程的崩溃通常不会影响其他进程，除非有特殊的共享资源等情况。而线程的独立性相对较弱，一个线程崩溃可能会导致整个进程崩溃，因为线程是在进程的资源环境中运行的。
创建和销毁：创建和销毁进程的开销较大，需要分配和释放大量的资源。而创建和销毁线程的开销较小，只是在进程的资源空间内进行一些简单的操作。

用户态、核心态，切换过程耗费资源吗？

在操作系统中，CPU 运行时存在用户态和核心态两种状态。

用户态：是应用程序运行的状态，在用户态下，应用程序只能访问受限的资源，不能直接访问硬件等底层资源，只能通过系统调用等方式请求操作系统提供服务。
核心态：是操作系统内核运行的状态，在内核态下，CPU 可以访问所有的硬件资源，执行特权指令，完成如进程调度、内存管理等重要操作。

用户态和核心态的切换过程是耗费资源的。当应用程序需要进行系统调用等操作时，会触发从用户态到核心态的切换。这个过程需要保存当前进程的上下文信息，包括寄存器的值、程序计数器等，然后加载内核的相关信息，执行内核代码。切换完成后，还需要恢复之前保存的上下文信息，将 CPU 控制权交还给应用程序，回到用户态。虽然现代操作系统通过各种优化技术来尽量减少切换的开销，但切换过程仍然需要一定的时间和 CPU 资源，尤其是频繁的切换会对系统性能产生一定的影响。

上下文切换过程

上下文切换是指 CPU 从一个进程或线程切换到另一个进程或线程时，需要保存当前进程或线程的状态，以便后续能够恢复继续执行，同时加载要切换到的进程或线程的状态。具体过程如下：

当发生上下文切换时，首先 CPU 会将当前进程或线程的寄存器值、程序计数器的值等上下文信息保存到内存中的特定区域，这些信息记录了当前进程或线程执行到的位置和相关数据状态。
然后，CPU 会根据调度算法选择下一个要执行的进程或线程，并从内存中读取该进程或线程的上下文信息，将其加载到 CPU 的寄存器等硬件资源中。
最后，CPU 根据加载的程序计数器的值，开始执行新的进程或线程的代码，从而实现了上下文的切换。

在多任务操作系统中，上下文切换是非常频繁的，它使得多个进程或线程能够看似同时运行，提高了系统的并发性和资源利用率，但过多的上下文切换也会带来一定的开销，降低系统性能，所以操作系统需要通过合理的调度算法等方式来平衡并发性和性能。

CPU 调度算法，选择标准

CPU 调度算法的选择标准主要有以下几个方面：

CPU 利用率：目标是让 CPU 尽可能地处于忙碌状态，充分利用 CPU 资源，减少 CPU 空闲时间。例如，通过合理的调度算法，让 CPU 在一个进程或线程等待 I/O 等操作时，及时切换到其他可执行的任务，提高 CPU 的利用率。
系统吞吐量：指单位时间内系统完成的任务数量。调度算法应能使系统在单位时间内处理更多的任务，提高系统的整体性能。比如短作业优先算法，对于一些执行时间较短的任务优先调度，有助于提高系统的吞吐量。
周转时间：是指从任务提交到任务完成所经历的时间。调度算法应尽量减少任务的周转时间，让用户提交的任务能够尽快得到处理和完成。
等待时间：是指任务在就绪队列中等待被调度执行的时间。调度算法要尽量减少任务的等待时间，避免任务长时间处于等待状态，提高用户体验。
响应时间：对于交互式系统来说，响应时间很重要，是指从用户提交请求到系统给出响应的时间。调度算法应确保系统能够快速响应用户的请求，让用户感觉系统是即时响应的。

先来先服务的调度算法，哪个任务先进来，就为哪个任务先服务

先来先服务（First Come，First Served，FCFS）调度算法是一种最简单的 CPU 调度算法。

工作原理：它按照任务到达就绪队列的先后顺序来进行调度，先进入就绪队列的任务先被调度到 CPU 上执行，直到该任务完成或者因为某些原因（如等待 I/O 等）主动放弃 CPU，才会调度下一个任务。
优点：算法实现简单，不需要复杂的计算和判断，只需要维护一个先进先出的队列即可。对于长任务来说，如果没有其他特殊要求，采用 FCFS 算法可以保证其按照顺序得到执行，不会出现被其他短任务频繁抢占的情况。
缺点：FCFS 算法没有考虑任务的执行时间等因素，可能会导致一些短任务需要长时间等待长任务执行完成，从而增加了短任务的周转时间和等待时间。例如，有一个长任务先到达队列，后面跟着多个短任务，那么这些短任务就需要等待长任务执行完才能得到调度，这在一定程度上降低了系统的效率和响应速度。

FCFS 算法适用于一些对任务执行顺序有严格要求，或者任务执行时间相对比较均匀的场景，但在大多数现代操作系统中，通常会结合其他更复杂的调度算法来提高系统性能。

SJF (Short Job First，短作业优先)（就是哪个任务的服务时间短就先调度哪个）

短作业优先（SJF）调度算法是一种 CPU 调度算法，它会优先调度预计执行时间最短的任务。

工作原理：系统会根据任务的预计执行时间对就绪队列中的任务进行排序，时间最短的任务排在最前面，优先获得 CPU 资源进行执行。比如，在一个有多个任务的系统中，任务 A 预计执行时间为 2 毫秒，任务 B 预计执行时间为 5 毫秒，任务 C 预计执行时间为 3 毫秒，那么按照 SJF 算法，任务 A 会先被调度执行，然后是任务 C，最后是任务 B。
优点：从平均周转时间的角度来看，SJF 算法能有效减少任务的平均等待时间和平均周转时间，提高系统的整体效率。因为它优先处理短任务，使得短任务能快速完成，减少了它们在系统中的停留时间。
缺点：SJF 算法需要事先知道每个任务的执行时间，这在实际中往往很难准确预估。而且，如果不断有短任务进入系统，可能会导致长任务长时间得不到调度，出现 “饥饿” 现象。比如，一个长任务进入系统后，不断有新的短任务加入，那么长任务可能会一直等待，无法获得 CPU 资源。

RR 算法 (按时间片来轮转调度)（选择标准：平均周转时间、任务类型时 IO 密集还是 CPU 密集、任务是否以短作业为主...）

时间片轮转（RR）调度算法是将 CPU 的时间划分成固定大小的时间片，每个任务轮流在一个时间片内占用 CPU。

工作原理：系统为每个就绪任务分配一个时间片，任务在获得 CPU 后，只能在这个时间片内运行。如果时间片结束时任务还未完成，它就会被暂停，放回就绪队列末尾，等待下一次调度。比如，时间片设置为 10 毫秒，任务 A 运行了 5 毫秒后时间片用完，那么它会被暂停，任务 B 接着运行 10 毫秒，以此类推。
选择标准
- 平均周转时间：合理设置时间片大小可以使平均周转时间保持在一个较优水平。如果时间片过大，RR 算法就近似于先来先服务算法，平均周转时间可能会变长；时间片过小，又会导致过多的上下文切换，增加系统开销，也会影响平均周转时间。
- 任务类型：对于 I/O 密集型任务，由于它们经常需要等待 I/O 操作完成，不会长时间占用 CPU，所以 RR 算法能很好地满足它们的需求，让它们及时得到调度去进行 I/O 操作。而对于 CPU 密集型任务，可能需要多个时间片才能完成，不过 RR 算法也能保证它们在一定时间内得到执行。
- 任务是否以短作业为主：如果系统中以短作业为主，较小的时间片就能让短作业快速完成，提高系统的响应速度和吞吐量。但如果有大量长作业，时间片太小会导致上下文切换过于频繁，反而降低效率。

Java 基本类型和占的字节

Java 中有 8 种基本数据类型，它们占用的字节数各不相同：

整数类型
- byte：占用 1 个字节，取值范围是 - 128 到 127，常用于存储较小的整数或者处理字节数据，比如在网络编程中处理字节流。
- short：占用 2 个字节，取值范围是 - 32768 到 32767，适用于需要节省内存空间且数据范围不大的情况。
- int：占用 4 个字节，取值范围较大，是最常用的整数类型，一般的整数运算都可以使用 int 类型。
- long：占用 8 个字节，取值范围比 int 更大，用于处理超出 int 范围的大整数，比如在处理时间戳等场景中经常会用到。
浮点类型
- float：占用 4 个字节，用于表示单精度浮点数，能表示的精度有限，适用于对精度要求不特别高且需要节省内存的情况。
- double：占用 8 个字节，是双精度浮点数，精度比 float 高，在科学计算、金融计算等对精度要求较高的场景中常用。
字符类型
- char：占用 2 个字节，用于表示单个字符，采用 Unicode 编码，可以表示各种语言中的字符。
布尔类型
- boolean：理论上占用 1 个字节，但在实际的 Java 虚拟机实现中，可能会根据具体情况进行优化，它只有 true 和 false 两个值，用于逻辑判断。

无序数组，偶数奇数分成两组。思路就是一次快排操作。

对于将无序数组中的偶数和奇数分成两组，可以利用类似快速排序的思想来实现。基本思路是设置两个指针，一个从数组头部开始，一个从数组尾部开始。

从头部开始的指针寻找奇数，从尾部开始的指针寻找偶数，当两个指针都找到目标数字后，交换这两个数字的位置，然后继续向中间移动指针，直到两个指针相遇。以下是示例代码：

public class Main {
    public static void partitionArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            // 从左向右找奇数
            while (left < right && arr[left] % 2 == 0) {
                left++;
            }
            // 从右向左找偶数
            while (left < right && arr[right] % 2!= 0) {
                right--;
            }
            // 交换找到的奇数和偶数
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 3, 8, 1};
        partitionArray(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

HTTP 和 HTTPS 的区别（HTTPS 与 HTTP 的区别，请详细说明。为什么说 HTTP 是无状态的？）

HTTP 和 HTTPS 存在多方面的区别：

连接方式与端口
- HTTP：连接相对简单，客户端向服务器发送请求，服务器响应请求后连接就结束了。默认使用 80 端口。
- HTTPS：在 HTTP 的基础上加入了 SSL/TLS 协议，使得数据传输更安全，连接过程相对复杂，需要先进行 SSL/TLS 握手等操作。默认使用 443 端口。
数据安全性
- HTTP：数据以明文形式传输，包括请求内容、用户信息等，容易被窃取、篡改和监听，存在安全风险。
- HTTPS：对数据进行加密处理，通过 SSL/TLS 协议的加密算法，将数据变成密文传输，只有合法的接收方才能解密数据，大大提高了数据的安全性。
证书
- HTTP：不需要数字证书来验证身份。
- HTTPS：服务器需要拥有由权威证书颁发机构颁发的数字证书，客户端可以通过验证证书来确认服务器的身份是否可信。

HTTP 被称为无状态的，是因为它在不同请求之间不会记住之前的请求信息或状态。每个请求都是独立的，服务器在处理完一个请求后，不会保存与该请求相关的上下文信息。比如，用户在一个电商网站上浏览了商品 A，又去浏览商品 B，服务器并不知道这两个请求是同一个用户发出的，也不会记住用户之前浏览过商品 A。这就导致如果需要实现一些需要状态记录的功能，比如用户登录后的购物车功能等，就需要通过其他方式，如使用 Cookie、Session 等来实现状态的跟踪和记录。

https 的加密过程

HTTPS 的加密过程综合了对称加密和非对称加密的优点，以实现安全的数据传输。具体过程如下：

客户端发起请求：客户端向服务器发送一个 HTTPS 请求，其中包含客户端支持的加密算法列表等信息。
服务器响应：服务器收到请求后，从客户端提供的加密算法列表中选择一组加密算法，并将自己的数字证书发送给客户端。数字证书包含服务器的公钥等信息，由权威的证书颁发机构（CA）签名认证。
客户端验证证书：客户端收到服务器的数字证书后，会使用本地的 CA 根证书来验证服务器证书的合法性。如果证书验证通过，客户端就可以从证书中提取出服务器的公钥。
生成随机密钥：客户端生成一个随机的对称密钥，用于后续的数据加密。这个密钥只有客户端和服务器知道，保证了数据的安全性。
加密密钥传输：客户端使用服务器的公钥对生成的对称密钥进行加密，并将加密后的密钥发送给服务器。因为只有服务器拥有对应的私钥，所以只有服务器能够解密并获取这个对称密钥。
数据加密传输：客户端和服务器都使用这个对称密钥对传输的数据进行加密和解密。对称加密算法速度快，适合大量数据的加密传输，从而保证了数据在传输过程中的保密性和完整性。

https 流程、介绍中间人攻击，如何防范

HTTPS 的流程大致如下：首先客户端发起请求，服务器返回证书，客户端验证证书并生成随机密钥，用服务器公钥加密后传给服务器，双方再用这个对称密钥进行数据加密传输。

中间人攻击是指攻击者在客户端和服务器之间插入自己，拦截、篡改或窃取双方通信的数据。比如攻击者拦截客户端请求，伪装成服务器向客户端发送假证书，客户端若没识别出来，就会与攻击者建立连接，攻击者就能获取或篡改传输的数据。

防范中间人攻击可以采取以下措施：

验证证书合法性：客户端要严格验证服务器证书，检查证书是否由可信的 CA 颁发、证书是否过期、证书中的域名是否与访问的域名一致等。
使用 HSTS：服务器可以配置 HTTP 严格传输安全（HSTS），强制客户端只能通过 HTTPS 连接，防止客户端被诱导使用 HTTP 而遭受中间人攻击。
定期更新证书和密钥：服务器应定期更新数字证书和加密密钥，降低密钥被破解或证书被冒用的风险。
监测网络：通过网络监测工具，及时发现异常的网络流量和连接，如发现有中间人攻击的迹象，及时采取措施。

DNS 使用什么传输层协议（DNS 流程，使用什么传输层协议）

DNS（域名系统）在传输层主要使用 UDP 协议，在某些情况下也会使用 TCP 协议。

DNS 的流程一般是这样的：当用户在浏览器中输入一个域名时，首先，客户端会向本地 DNS 服务器发送查询请求，询问该域名对应的 IP 地址。本地 DNS 服务器如果缓存中有该域名的记录，就会直接返回 IP 地址给客户端。如果没有，本地 DNS 服务器会向根 DNS 服务器发送查询请求，根 DNS 服务器会根据域名的顶级域名，告诉本地 DNS 服务器应该去询问哪个顶级域名服务器。本地 DNS 服务器再向对应的顶级域名服务器发送请求，顶级域名服务器会根据域名的二级域名等信息，告诉本地 DNS 服务器应该去询问哪个权威 DNS 服务器。最后，本地 DNS 服务器向权威 DNS 服务器发送请求，权威 DNS 服务器返回该域名对应的 IP 地址给本地 DNS 服务器，本地 DNS 服务器再将 IP 地址返回给客户端。

DNS 通常使用 UDP 协议，因为 UDP 具有传输速度快、开销小的特点，适合 DNS 这种对实时性要求较高、数据量相对较小的查询请求。但是，当 DNS 查询的结果数据量较大，超过了 UDP 数据包的最大长度（一般为 512 字节）时，就会使用 TCP 协议进行传输，因为 TCP 支持可靠的、面向连接的传输，能够保证数据的完整性和准确性。

tcp 为什么要三次握手。两次握手会出现什么情况

编辑

TCP 三次握手的目的是为了在客户端和服务器之间建立可靠的连接，确保双方都能正常发送和接收数据。

第一次握手：客户端向服务器发送一个 SYN（同步）包，告诉服务器客户端想要建立连接，这个包中包含了客户端的初始序列号。

第二次握手：服务器收到客户端的 SYN 包后，向客户端发送一个 SYN+ACK 包，其中 SYN 是服务器的同步请求，ACK 是对客户端 SYN 包的确认，同时也包含了服务器的初始序列号。

第三次握手：客户端收到服务器的 SYN+ACK 包后，向服务器发送一个 ACK 包，对服务器的 SYN 进行确认。至此，双方都确认了对方的存在和发送接收能力，连接建立成功。

如果只有两次握手，可能会出现以下问题：当客户端发送的第一个 SYN 包因为网络延迟等原因在网络中滞留，客户端以为服务器没有收到，就会重新发送 SYN 包，服务器正常响应并建立连接。但之后，之前滞留的 SYN 包到达服务器，服务器会认为这是客户端又一次发起的连接请求，于是又发送 SYN+ACK 包给客户端，而客户端此时已经认为连接建立完成，不会对这个包进行正确处理，导致服务器资源浪费，而且可能会造成数据传输混乱等问题。

TCP 的拥塞控制机制（说说 TCP 的拥塞避免（滑动窗口））

TCP 的拥塞控制机制是为了防止网络出现拥塞，确保网络的稳定性和数据传输的效率，其中拥塞避免是通过滑动窗口机制来实现的。

滑动窗口的基本原理是：发送方和接收方都维护一个窗口，发送方的窗口大小表示可以发送但尚未收到确认的数据量，接收方的窗口大小表示可以接收的数据量。在数据传输过程中，发送方根据接收方反馈的确认信息和网络状况来动态调整窗口大小。

在拥塞避免阶段，TCP 采用了一种较为保守的策略来调整窗口大小。开始时，拥塞窗口大小通常为一个较小的值，比如 1 个最大段长度（MSS）。随着数据的发送和确认，每收到一个新的确认，拥塞窗口就增加一个 MSS 大小。当拥塞窗口达到慢启动阈值时，进入拥塞避免阶段。在这个阶段，每经过一个往返时间（RTT），拥塞窗口才增加 1 个 MSS。这样可以避免窗口增长过快导致网络拥塞。

如果发送方发现网络出现拥塞，比如出现了超时重传或者收到了重复的确认，就会认为网络拥塞了。这时，发送方会降低拥塞窗口的大小，通常是将慢启动阈值设置为当前拥塞窗口的一半，同时将拥塞窗口重置为 1 个 MSS，然后重新开始慢启动过程，逐渐增加窗口大小，探测网络的拥塞情况。通过这种动态调整窗口大小的方式，TCP 能够在网络状况良好时充分利用网络带宽，又能在网络出现拥塞时及时调整，避免网络崩溃。

TCP 数据完整性的验证过程

TCP 通过多种机制来验证数据完整性。首先是校验和机制，发送方在发送数据时，会根据数据内容计算一个校验和，并将其放入 TCP 首部的校验和字段。接收方收到数据后，会对数据重新计算校验和，并与首部中的校验和进行对比，如果两者不一致，就说明数据在传输过程中可能出现了错误。

其次是序列号和确认号机制，TCP 为每个字节都分配一个序列号，发送方发送数据时会在首部中填写序列号，接收方收到数据后，会根据序列号来判断数据是否有序、是否有缺失。接收方通过发送确认号告诉发送方哪些数据已经正确接收，发送方根据确认号来确定哪些数据需要重传。

还有数据重传机制，当发送方发送数据后，如果在规定时间内没有收到接收方的确认，就会认为数据传输失败，重新发送数据。另外，滑动窗口机制也有助于保证数据完整性，它允许发送方在收到确认之前发送多个数据段，接收方通过窗口大小来告知发送方可以发送的数据量，确保数据不会因为接收方处理不过来而丢失或乱序。

TCP、UDP 的区别

TCP 和 UDP 是两种不同的传输层协议，它们有很多区别。从连接特性来看，TCP 是面向连接的协议，就好像打电话一样，在数据传输前需要先建立连接，传输结束后要释放连接；而 UDP 是无连接的，类似写信，不需要事先建立连接就可以直接发送数据。

可靠性方面，TCP 提供可靠的传输服务，通过序列号、确认号、校验和、重传机制等保证数据无差错、不丢失、不重复且按序到达；UDP 则是不可靠的传输协议，它不保证数据一定能正确到达，也不保证顺序和不重复，但是 UDP 的传输速度相对较快，延迟低。

从数据传输方式看，TCP 是流式传输，数据就像水流一样连续发送，没有边界；UDP 是数据报传输，每个数据报都是独立的，有明确的边界。

应用场景上，TCP 适用于对数据准确性要求高的场景，如文件传输、HTTP 协议等；UDP 适用于对实时性要求高、能容忍一定数据丢失的场景，像视频直播、实时游戏等。

HTTP2.0 的特性

HTTP2.0 相比 HTTP1.0 和 HTTP1.1 有很多显著特性。首先是二进制分帧，HTTP1.x 是文本格式，而 HTTP2.0 采用二进制格式，将数据分解为帧，以二进制的方式进行传输，这样更高效，也更易于解析和处理。

还有多路复用，HTTP1.x 每个连接只能处理一个请求，而 HTTP2.0 可以在一个连接上同时发送多个请求和响应，并且不会发生堵塞，大大提高了连接的利用率，减少了连接建立和关闭的开销。

首部压缩也是 HTTP2.0 的重要特性，HTTP1.x 的首部字段往往比较大，会占用不少带宽，HTTP2.0 采用 HPACK 算法对首部进行压缩，减少了首部的传输大小，提高了传输效率。

服务器推送功能也很实用，服务器可以主动向客户端推送资源，而不需要客户端先发起请求，比如服务器可以在发送 HTML 页面时，主动把相关的 CSS、JavaScript 等资源推送给客户端，加快页面的加载速度。

HashMap 底层实现

Java 中的 Map 结构有多种，常见的有 HashMap、TreeMap、LinkedHashMap 等。HashMap 的底层是基于哈希表实现的，它使用数组和链表（或红黑树）来存储数据。

当向 HashMap 中 put 键值对时，会根据键的哈希值计算出在数组中的索引位置。如果该位置没有元素，就直接将键值对存储在这个位置。如果该位置已经有元素了，就会发生哈希冲突，此时会将新的键值对以链表的形式挂在该位置的元素后面。当链表长度达到一定阈值（默认 8）时，链表会转换为红黑树，以提高查找效率。

当从 HashMap 中 get 元素时，同样会根据键的哈希值计算索引，然后在对应的位置查找。如果是链表结构，就需要遍历链表来找到对应的键值对；如果是红黑树结构，就通过红黑树的查找算法来查找。

TreeMap 的内部结构是红黑树，它会根据键的自然顺序或自定义比较器进行排序，所以 TreeMap 中的元素是有序的。LinkedHashMap 则是在 HashMap 的基础上，通过双向链表维护了元素的插入顺序或访问顺序。

HashMap 是不是线程同步的

HashMap 不是线程同步的，在多线程环境下使用 HashMap 可能会出现数据不一致等问题。比如多个线程同时向 HashMap 中 put 数据时，可能会导致哈希表的结构被破坏，出现数据丢失、覆盖或者死循环等情况。

举个例子，当两个线程同时对同一个 HashMap 进行扩容操作时，由于没有同步机制，可能会导致链表形成环，这样在遍历 HashMap 或者获取元素时就会陷入死循环。

如果需要在多线程环境下使用 Map，并且要求线程安全，可以使用 Hashtable，它是线程同步的，方法都是 synchronized 修饰的。或者使用 ConcurrentHashMap，它采用了更细粒度的锁机制，性能比 Hashtable 更好，在多线程环境下能提供更好的并发访问能力和数据安全性。

TCP 数据完整性的验证过程

TCP 通过多种机制来确保数据完整性。首先是序列号和确认号机制，发送方给每个字节数据都分配一个序列号，接收方收到数据后，会根据序列号来判断数据是否有序、有无缺失，并通过确认号告知发送方已成功接收的数据序列号，让发送方知道哪些数据已被正确接收。

其次是校验和机制，发送方在发送数据时会对数据和首部计算校验和，接收方收到数据后重新计算校验和，并与发送方的校验和进行对比，如果不一致，就说明数据在传输过程中出现了错误，会要求发送方重传。

还有重传机制，当发送方发送数据后，如果在规定时间内没有收到接收方的确认，就会认为数据传输失败，自动重传数据。另外，滑动窗口机制也有助于保证数据完整性，它允许发送方在未收到确认的情况下，发送多个数据段，接收方可以通过滑动窗口告知发送方自己的接收能力和已接收的数据情况，发送方根据这些信息来调整发送数据的速度和内容，避免数据丢失或重复。

Service 生命周期（Service 怎么保活，怎么提高自己的优先级，怎么在一个单独的进程里执行，IntentService 实现机制，Service 怎么把处理结果告诉主线程，Service 和 Activity 怎么通信）

Service 保活：可以通过在 Service 的onDestroy方法中重新启动 Service 来实现简单保活。还可以使用前台 Service，将 Service 设置为前台运行状态，系统会降低其被杀死的可能性，例如调用startForeground方法。也可以利用 JobScheduler 等机制，在合适的时机触发 Service 的执行。
提高优先级：将 Service 设置为前台 Service，会有较高的优先级。在 Manifest 文件中为 Service 设置较高的优先级属性android:priority。当 Service 与 Activity 等组件有绑定关系时，也能在一定程度上提高优先级。
在单独进程执行：在 AndroidManifest.xml 文件中给 Service 组件添加android:process属性，指定一个单独的进程名，这样 Service 就会在指定的单独进程中运行。
IntentService 实现机制：IntentService 是 Service 的子类，它内部有一个工作线程来处理所有启动请求。当启动 IntentService 时，它会将接收到的 Intent 放入队列，然后在工作线程中依次处理。处理完所有任务后，IntentService 会自动停止。
Service 把结果告诉主线程：可以通过广播BroadcastReceiver，Service 在处理完结果后发送广播，主线程注册相应的广播接收器来接收结果。也可以使用接口回调，在主线程中实现一个接口，将接口的实例传递给 Service，Service 处理完后调用接口方法将结果返回给主线程。
Service 和 Activity 通信：除了上述方法外，还可以使用Messenger，Service 中创建Messenger来接收 Activity 发送的消息，同时可以通过Messenger给 Activity 发送消息。也能使用AIDL来实现 Service 和 Activity 在不同进程间的通信，定义好接口和数据类型，实现双向通信。

Activity 生命周期（Activity 的四种启动模式与区别。Activity 启动模式，举例子。）

Activity 有四种启动模式，分别是standard、singleTop、singleTask和singleInstance。

standard：标准模式，每次启动 Activity 都会创建一个新的实例，不管这个 Activity 是否已经存在于栈中。例如，在一个应用中有多个界面 A、B、C，从 A 启动 B，再从 B 启动 A，这时会创建一个新的 A 的实例。
singleTop：栈顶复用模式，如果要启动的 Activity 已经位于栈顶，那么不会创建新的实例，而是复用栈顶的 Activity。比如在新闻详情页，如果不断刷新新闻，还是在同一个新闻详情页 Activity，不会创建新的。
singleTask：栈内复用模式，系统会检查栈中是否已经存在该 Activity 的实例，如果存在，则将该 Activity 之上的所有 Activity 出栈，使该 Activity 成为栈顶元素。例如，应用的主界面通常采用这种模式，无论从哪里回到主界面，都只会有一个主界面实例。
singleInstance：单实例模式，该 Activity 会在一个单独的任务栈中，并且整个系统中只有一个这样的实例。比如手机的拨号界面，它独立存在于一个任务栈中，方便随时调用，且不会与其他应用的 Activity 混淆。

面向对象的特征有哪些？

面向对象有四个主要特征，分别是封装、继承、多态和抽象。

封装：将数据和操作数据的方法封装在一个类中，对外隐藏内部的实现细节，只提供公共的接口供外部访问。就像一个电视机，用户只需要通过遥控器上的按钮来操作电视，而不需要知道电视内部的电路结构和工作原理。
继承：子类可以继承父类的属性和方法，实现代码的复用。比如，有一个动物类，猫类和狗类可以继承动物类的一些共同属性和方法，如吃东西、睡觉等，同时还可以有自己特有的属性和方法。
多态：同一操作作用于不同的对象，可以有不同的解释和表现。例如，同样是 “叫” 这个操作，猫叫和狗叫的声音是不同的，这就是多态的体现。在代码中，可以通过方法重载和方法重写来实现多态。
抽象：将现实世界中的事物进行概括和抽象，提取出共同的特征和行为，形成类。比如，将各种具体的交通工具抽象成一个交通工具类，只关注它们的共同属性和行为，如都能运输乘客或货物等。

事务有哪些特性？（一般什么时候用到事务）

事务具有 ACID 特性，即原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。

原子性：事务中的操作要么全部执行，要么全部不执行，就像一个原子一样不可分割。比如在银行转账中，从账户 A 扣除金额和向账户 B 增加金额这两个操作必须同时成功或同时失败。
一致性：事务执行前后，数据库的完整性约束没有被破坏。例如，转账前后，账户 A 和账户 B 的总金额应该保持不变。
隔离性：多个事务并发执行时，一个事务的执行不能被其他事务干扰。各个事务之间是相互隔离的，比如多个用户同时进行转账操作，彼此之间不会相互影响。
持久性：事务一旦提交，它对数据库的修改就应该永久保存下来。即使系统崩溃或出现其他故障，数据也不会丢失。事务一般在需要保证数据完整性和一致性的场景中使用，如银行系统中的转账、支付等操作，电商系统中的订单创建、库存扣减等操作，都需要使用事务来确保数据的正确性和可靠性。

静态内部类

静态内部类是定义在另一个类内部的类，并且使用static关键字修饰。

特点：静态内部类不依赖于外部类的实例，它可以直接通过外部类名来访问。例如有一个外部类Outer和它的静态内部类Inner，可以通过Outer.Inner来访问静态内部类。静态内部类不能直接访问外部类的非静态成员，只能访问外部类的静态成员。
作用：可以将一些相关的类组织在一起，提高代码的可读性和可维护性。比如在一个大型的工具类中，可以将一些相关的子功能封装在静态内部类中。还可以用于实现单例模式，在静态内部类中创建单例对象，利用静态内部类的特性来保证单例的唯一性和延迟加载。
与非静态内部类区别：非静态内部类依赖于外部类的实例，必须先创建外部类的实例才能创建非静态内部类的实例。非静态内部类可以直接访问外部类的所有成员，包括非静态成员。而静态内部类没有对外部类实例的引用，不能直接访问外部类的非静态成员。

协程（协程的概念）

协程是一种轻量级的异步编程模型，它允许在不阻塞主线程的情况下执行异步操作。简单来说，协程就像是一个可以暂停和恢复的函数，它能在执行过程中暂停，去做其他事情，然后再回来继续执行。

与传统的线程相比，协程更加轻量级，创建和切换的开销更小。线程的调度由操作系统内核来控制，而协程的调度是由程序自身来决定的。这使得协程在处理一些需要频繁切换上下文的异步任务时，性能更加出色。

在实际应用中，协程常用于处理网络请求、文件读取等异步操作。比如在 Android 开发中，使用协程可以很方便地在后台线程进行数据加载，然后在数据加载完成后，将结果切换到主线程进行 UI 更新，这样可以避免出现界面卡顿的情况，提升用户体验。

自定义 view 的三个方法（说下自定义 view 涉及的几个方法都有什么用）

onMeasure(int widthMeasureSpec, int heightMeasureSpec)：这个方法主要用于测量 View 的宽和高。在这个方法中，需要根据父容器传递过来的测量规格以及自身的需求，计算出合适的宽高尺寸，并通过 setMeasuredDimension (int measuredWidth, int measuredHeight) 方法来设置测量结果。比如，如果自定义一个圆形的 View，就需要在这个方法中根据给定的测量规格，计算出能够容纳这个圆形的最小正方形的边长作为 View 的宽高。
onLayout(boolean changed, int left, int top, int right, int bottom)：当 View 需要确定其子 View 的位置和大小时，就会调用这个方法。在这个方法中，可以根据子 View 的数量、大小和布局规则，为每个子 View 分配具体的位置和尺寸。例如，在实现一个线性布局的自定义 View 时，就需要在这个方法中根据子 View 的顺序和排列方向，依次计算每个子 View 的 left、top、right、bottom 参数，来确定它们在父 View 中的位置。
onDraw(Canvas canvas)：这个方法是用来绘制 View 的内容。在这个方法中，可以使用 Canvas 和 Paint 等类来绘制各种图形、文本等内容。比如绘制一个自定义的进度条，就可以在这个方法中根据当前的进度值，使用 Canvas 的 drawRect () 或 drawArc () 等方法来绘制进度条的背景和进度条的进度部分。

SQL 索引了解吗（索引为什么用 b + 树而不用二叉树。选择什么字段作为索引，有两个字段，姓和名，选择哪个比较合适最左匹配原则）

索引为什么用 B + 树而不用二叉树：B + 树和二叉树都是数据结构，在数据库索引中，B + 树更为常用。二叉树在数据量较大时，容易出现树的高度过高的情况，导致查询效率下降。而 B + 树所有数据都存储在叶子节点，并且叶子节点通过指针连接成有序链表，这使得范围查询和排序操作更加高效。同时，B + 树的每个节点可以存储多个键值对，相比二叉树能减少磁盘 I/O 次数，提高查询性能。
选择什么字段作为索引，有两个字段，姓和名，选择哪个比较合适：如果有姓和名两个字段，一般来说选择区分度高的字段作为索引更合适。如果姓的重复率相对较低，即不同的姓的数量较多，那么选择姓作为索引可能会更好，因为这样可以更快地定位到具体的数据记录。但如果名的重复率更低，或者在实际查询中经常根据名来进行精确查询，那么选择名作为索引可能更合适。另外，如果经常使用姓和名一起进行联合查询，那么可以考虑创建联合索引。
最左匹配原则：在使用联合索引时，最左匹配原则非常重要。它指的是在查询时，MySQL 会从联合索引的最左边的列开始匹配，如果查询条件中没有使用最左边的列，那么索引可能不会被使用。例如，有一个联合索引（col1, col2, col3），当查询条件是 where col1 = 'value1' and col2 = 'value2' 时，索引会被使用，因为是从最左边的列开始匹配的。但如果查询条件是 where col2 = 'value2' and col3 = 'value3'，索引可能就不会被使用，因为没有从最左边的列开始匹配。

Activity 间传递数据

在 Android 中，Activity 间传递数据有多种方式：

使用 Intent 传递基本数据类型和可序列化对象：可以通过 Intent 的 putExtra () 方法来传递数据，支持传递如 String、int、boolean 等基本数据类型以及实现了 Serializable 或 Parcelable 接口的对象。比如在一个 Activity 中启动另一个 Activity 并传递一个字符串：

Intent intent = new Intent(this, SecondActivity.class);
intent.putExtra("key", "value");
startActivity(intent);

在目标 Activity 中可以通过 getIntent ().getStringExtra ("key") 来获取传递的数据。

使用 Bundle 传递数据：Bundle 可以看作是一个键值对的集合，也可以用于在 Activity 间传递数据。可以先将数据放入 Bundle 中，然后再将 Bundle 放入 Intent 中。例如：

Bundle bundle = new Bundle();
bundle.putString("key", "value");
Intent intent = new Intent(this, SecondActivity.class);
intent.putExtras(bundle);
startActivity(intent);

使用静态变量传递数据：可以在一个类中定义静态变量，在一个 Activity 中给静态变量赋值，在另一个 Activity 中直接访问这个静态变量来获取数据。但这种方式不太推荐，因为可能会导致内存泄漏等问题，并且不利于代码的维护和扩展。
使用共享文件或数据库传递数据：如果需要传递大量的数据或者需要在多个 Activity 甚至多个应用之间共享数据，可以使用共享文件或者数据库来存储数据。一个 Activity 将数据写入文件或数据库，另一个 Activity 从文件或数据库中读取数据。

Intent 的显性与隐性

显性 Intent：明确指定了目标组件的 Intent 就是显性 Intent。在使用显性 Intent 时，需要在 Intent 中指定目标 Activity 的类名等信息，这样系统就能准确地找到要启动的组件。比如要启动一个名为 SecondActivity 的 Activity，可以这样写：

Intent intent = new Intent(this, SecondActivity.class);
startActivity(intent);

显性 Intent 主要用于在应用内部明确地启动特定的组件，开发者清楚地知道要启动哪个组件，这种方式非常直接和明确，适合在应用内部进行页面跳转等操作。

隐性 Intent：隐性 Intent 没有明确指定目标组件，而是通过设置一些动作（action）、类别（category）和数据（data）等信息来让系统根据这些条件去匹配合适的组件来启动。例如，要启动系统的浏览器来打开一个网页，可以这样写：

Intent intent = new Intent(Intent.ACTION_VIEW, Uri.parse("https://www.example.com"));
intent.addCategory(Intent.CATEGORY_BROWSABLE);
startActivity(intent);

隐性 Intent 主要用于与其他应用的组件进行交互，或者在应用内部实现一些灵活的组件启动方式，比如根据不同的条件启动不同的 Activity 等。系统会根据 Intent 中的信息在所有已注册的组件中寻找能够处理该 Intent 的组件来启动。

okhttp 的拦截器

OkHttp 的拦截器是其强大功能的重要组成部分哦😉 它可以对请求和响应进行拦截、处理和修改。

拦截器分为应用拦截器和网络拦截器。应用拦截器主要用于在应用层对请求和响应进行处理，比如添加请求头、记录请求日志等。它只会被调用一次，不会受到重定向或重试的影响。而网络拦截器则主要用于在网络层对请求和响应进行处理，例如可以观察网络请求的真实情况，包括重定向、连接池的使用等。

自定义拦截器需要实现 Interceptor 接口，重写 intercept 方法。在 intercept 方法中，可以拿到 Chain 对象，通过它可以获取到 Request 和 Response 等信息。比如下面这样：

public class LoggingInterceptor implements Interceptor {
    @Override
    public Response intercept(Chain chain) throws IOException {
        Request request = chain.request();
        // 记录请求信息
        long t1 = System.nanoTime();
        Response response = chain.proceed(request);
        // 记录响应信息
        long t2 = System.nanoTime();
        return response;
    }
}

拦截器还可以用于实现缓存策略、添加公共参数等功能，大大提高了网络请求的灵活性和可扩展性。

如何优化性能（讲讲 Android 性能优化）

2万字Android应用程序性能优化保姆级教程（持续更新）

Android 性能优化涉及多个方面呢。

首先是布局优化，减少布局的层级嵌套，可以使用 RelativeLayout、FrameLayout 等简单布局来替代复杂的 LinearLayout 嵌套。还可以使用 ViewStub 来按需加载布局，避免一开始就加载所有布局。

然后是内存优化，要注意避免内存泄漏，比如及时释放资源、正确使用 Context 等。对于大图片的处理，可以采用图片压缩、缓存策略等，使用 Glide 等图片加载框架能很好地处理图片相关的性能问题。

再就是代码优化，避免在主线程进行耗时操作，将网络请求、文件读取等操作放在子线程中进行。使用异步任务、线程池等技术来提高代码的执行效率。

还有卡顿优化，要关注帧率，通过 Profiler 工具分析卡顿的原因，可能是因为布局过于复杂、动画不流畅等。对于频繁刷新的界面，要考虑使用 RecyclerView 等高效的列表控件，并合理使用 ViewHolder 模式来复用视图。

另外，APK 的大小优化也很重要，删除不必要的资源文件，对资源进行压缩，使用混淆工具来减小代码体积，这样可以加快应用的下载和安装速度。

fragment 的生命周期

Fragment 的生命周期挺复杂但也很有趣哦😄

当 Fragment 被创建时，会调用 onAttach 方法，在这里可以获取到宿主 Activity 的相关信息。接着是 onCreate 方法，用于进行一些初始化操作，比如初始化数据等。然后是 onCreateView 方法，在这里创建 Fragment 的视图布局，返回一个 View 对象。

当 Fragment 的视图创建完成后，会调用 onViewCreated 方法，可以在这个方法中对视图进行进一步的操作，比如设置点击事件等。

当 Fragment 可见时，会调用 onStart 方法，然后是 onResume 方法，此时 Fragment 处于活跃状态，可以与用户进行交互。

当宿主 Activity 被暂停时，Fragment 会调用 onPause 方法，当 Activity 被停止时，Fragment 会调用 onStop 方法。

如果 Fragment 要被销毁，会先调用 onDestroyView 方法，用于销毁视图，然后是 onDestroy 方法，进行一些资源释放等操作，最后是 onDetach 方法，与宿主 Activity 分离。

需要注意的是，Fragment 的生命周期与宿主 Activity 的生命周期是紧密相关的，Activity 的状态变化会影响 Fragment 的状态变化。而且在嵌套 Fragment 的情况下，生命周期会更加复杂，需要更加小心地处理。

AsyncTask 原理

AsyncTask 是 Android 提供的一个轻量级异步任务类，用于在后台执行任务并更新 UI。

它的原理是基于线程池和 Handler 机制。AsyncTask 内部有一个线程池，用于执行后台任务。当调用 execute 方法时，会将任务提交到线程池中，在后台线程中执行 doInBackground 方法，这里可以进行耗时操作，比如网络请求、文件读取等。

当后台任务执行完成后，会通过 Handler 发送消息到主线程，在主线程中调用 onPostExecute 方法，在这里可以更新 UI，将后台任务的结果展示给用户。

AsyncTask 还提供了 onPreExecute 方法，在任务执行前会在主线程中调用，可以用于进行一些准备工作，比如显示加载对话框等。还有 onProgressUpdate 方法，当在 doInBackground 方法中调用 publishProgress 方法时，会在主线程中调用 onProgressUpdate 方法，可以用于更新任务的进度。

不过要注意哦，AsyncTask 在不同版本的 Android 系统中可能有一些差异，在使用时要根据具体情况进行处理，而且如果滥用 AsyncTask 可能会导致内存泄漏等问题，比如在 Activity 中使用 AsyncTask 时，如果 Activity 被销毁了，而 AsyncTask 还在执行，就可能出现问题，所以要合理管理 AsyncTask 的生命周期。

常见的设计模式，什么是装饰器模式？（Java 设计模式 Android 里面哪些地方用到了设计模式）

常见的设计模式有很多啦，比如单例模式、工厂模式、观察者模式、策略模式、装饰器模式等等。

装饰器模式是一种结构型设计模式，它允许在不改变现有对象结构的情况下，动态地给对象添加新的功能。它通过将对象包装在一个装饰器对象中，来扩展对象的功能。

在 Java 中，IO 流就是装饰器模式的典型应用。比如 BufferedInputStream 可以装饰 InputStream，给 InputStream 添加缓冲的功能，而不需要修改 InputStream 的代码。

在 Android 中，也有很多地方用到了设计模式哦。比如单例模式，在应用中经常会用到单例来管理一些全局的资源或状态，像数据库管理类、网络请求管理器等。观察者模式在 Android 的事件机制中很常见，比如 View 的点击事件，当用户点击 View 时，就相当于触发了一个事件，而注册了点击事件监听器的对象就相当于观察者，会收到事件通知并进行相应的处理。

策略模式在 Android 中可以用于根据不同的条件选择不同的算法或行为，比如根据网络状态选择不同的网络请求策略。

装饰器模式在 Android 中也有应用，比如可以通过装饰器来给 View 添加一些额外的功能，比如给 Button 添加点击音效、给 TextView 添加特殊的显示效果等，通过装饰器模式可以很灵活地实现这些功能，而不会使代码变得过于复杂和混乱。

MVP 模式和 MVC 模式的优缺点（MVP 模式中 M 和 V 如何直接通信，不经过 P 层）

MVP 模式
- 优点：将视图、业务逻辑和数据模型分离，使得代码结构清晰，易于维护和测试。视图层和模型层之间通过 Presenter 进行交互，降低了耦合度。
- 缺点：会导致代码复杂度增加，因为需要创建更多的类和接口。如果项目规模较小，使用 MVP 模式可能会显得过于繁琐。
- MVP 模式中 M 和 V 直接通信：在 MVP 模式中，通常 M 和 V 不应该直接通信，否则会破坏 MVP 的设计原则。但如果非要实现，可在 V 层中持有 M 层的引用，直接调用 M 层的方法获取数据。不过这种方式会增加耦合度，使代码的可维护性和可测试性降低。
MVC 模式
- 优点：模型、视图和控制器各司其职，视图负责展示，模型负责数据处理，控制器负责逻辑控制，层次分明。可以方便地进行代码的复用和扩展。
- 缺点：视图和模型之间存在一定的耦合度，比如视图可能需要直接访问模型的数据。在大型项目中，控制器可能会变得非常复杂，难以维护。

Android 线程间通信（Android 怎么把耗时操作放子线程，做完怎么把结果告诉主线程）

在 Android 中，将耗时操作放在子线程并把结果告诉主线程有多种方式：

使用 Handler：在主线程中创建 Handler，并重写handleMessage方法来处理子线程发送的消息。在子线程中通过Handler.sendMessage方法发送消息，主线程的Handler就会在handleMessage方法中接收到消息并处理结果。
使用 AsyncTask：AsyncTask是 Android 提供的一个轻量级异步任务类。可以在doInBackground方法中执行耗时操作，在onPostExecute方法中处理结果，onPostExecute方法会在主线程中执行，方便更新 UI。
使用线程池：通过ExecutorService创建线程池，将耗时任务提交到线程池中执行。当任务完成后，可通过Future获取结果，再在主线程中处理。

handler 机制（说下 handler 机制是做什么的，实现原理，能在子线程中创建 handler 吗，如何创建）

Handler 机制的作用：主要用于在 Android 中进行线程间的通信和消息处理，能将子线程中的操作切换到主线程中执行，比如更新 UI 等操作。
实现原理：Handler 机制主要由Handler、MessageQueue和Looper组成。Handler用于发送和处理消息，MessageQueue是消息队列，用于存储消息，Looper负责从MessageQueue中取出消息并分发给Handler处理。
在子线程中创建 Handler：可以在子线程中创建Handler，但需要先调用Looper.prepare()方法来准备Looper，然后创建Handler，最后调用Looper.loop()方法来启动Looper循环。不过要注意，在非主线程的子线程中使用Handler，当该子线程结束时，需要手动调用Looper.myLooper().quit()来停止Looper循环，否则会导致线程无法正常结束。

一个线程能有几个 handler，几个 looper

在 Android 中，一个线程可以有多个Handler，但只能有一个Looper。Looper是与线程绑定的，它负责管理该线程的MessageQueue。而多个Handler可以共享同一个Looper，它们可以向同一个MessageQueue中发送消息，并且各自处理自己感兴趣的消息。不同的Handler可以通过不同的消息类型或what字段来区分和处理消息。

事件分发机制说一下

Android 的事件分发机制主要涉及Activity、ViewGroup和View。当用户触摸屏幕时，事件首先会传递到Activity的dispatchTouchEvent方法，然后由Activity将事件传递给ViewGroup，ViewGroup再根据情况决定是否拦截事件，如果不拦截则将事件分发给子View，子View接收到事件后进行相应处理。

主要方法
- dispatchTouchEvent：用于分发事件，返回true表示事件已被处理，不再继续分发；返回false表示不处理该事件，会将事件传递给父容器的onTouchEvent方法。
- onInterceptTouchEvent：ViewGroup特有的方法，用于判断是否拦截事件，返回true表示拦截，事件将不再分发给子View，而是由ViewGroup的onTouchEvent方法处理；返回false表示不拦截。
- onTouchEvent：用于处理事件，返回true表示事件被处理了，返回false表示不处理，事件会向上传递给父容器的onTouchEvent方法。

自定义 View 说一下

自定义 View 是 Android 开发中很重要的一块内容哦😉 它允许开发者根据自己的需求创建独特的用户界面组件。

首先，自定义 View 通常需要重写一些方法。比如onMeasure()方法，这个方法主要是用来测量 View 的宽和高，确定它在布局中的大小。通过调用setMeasuredDimension()来设置测量后的宽高值。还有onLayout()方法，当 View 需要确定其子 View 的位置时就会调用这个方法，在里面可以通过计算来摆放子 View 的位置。onDraw()方法则是用于绘制 View 的内容，比如绘制图形、文字等，通过Canvas对象来进行具体的绘制操作。

在自定义 View 时，还需要考虑属性的定义。可以在res/values目录下的attrs.xml文件中定义自定义属性，然后在布局文件中使用这些属性来设置 View 的外观和行为。在代码中通过TypedArray来获取这些属性的值。

另外，自定义 View 还可以实现一些交互功能，比如触摸事件的处理。通过重写onTouchEvent()方法来处理用户的触摸操作，比如点击、滑动等，根据不同的触摸事件类型来实现相应的逻辑。

四大组件讲一下

Android 的四大组件分别是 Activity、Service、Broadcast Receiver 和 Content Provider。

Activity：它是 Android 中最基本的组件，主要用于实现用户界面。一个 Activity 通常对应一个屏幕的内容，用户可以在上面进行各种交互操作。它有自己完整的生命周期，包括onCreate()、onStart()、onResume()等方法，开发者可以在这些方法中进行相应的初始化和操作。

Service：用于在后台执行长时间运行的操作，不提供用户界面。比如音乐播放服务、文件下载服务等。Service 分为启动式服务和绑定式服务，启动式服务通过startService()启动，会一直运行直到stopService()被调用或者自己停止；绑定式服务通过bindService()绑定，与调用者有一个连接，当调用者解除绑定或者自己停止时，服务才会停止。

Broadcast Receiver：用于接收系统或应用发出的广播消息，比如电池电量变化、网络连接变化等广播。可以通过注册静态广播和动态广播来接收广播。静态广播在AndroidManifest.xml文件中注册，动态广播则是在代码中通过registerReceiver()方法注册。

Content Provider：用于在不同的应用之间共享数据。它可以将数据以一种标准的方式提供给其他应用访问，其他应用可以通过ContentResolver来访问Content Provider提供的数据，实现了数据的共享和安全访问。

为什么学 Android，怎么学的

选择学习 Android 有很多原因呀😄 一方面，Android 系统在全球拥有庞大的用户群体，市场需求非常大，学习 Android 开发有很好的就业前景。另一方面，Android 开发可以让开发者创造出各种各样实用又有趣的应用，满足人们不同的需求，能够将自己的想法通过代码实现并呈现在用户面前，是一件很有成就感的事情。

学习 Android 的话，首先要掌握 Java 或者 Kotlin 编程语言，它们是 Android 开发的基础。可以通过在线课程、书籍等资源来学习编程语言的基础知识，比如变量、数据类型、控制语句等。

然后就是学习 Android 的基础知识，包括四大组件、布局管理、视图控件等。可以参考官方文档，它非常全面和详细，是学习 Android 的重要资料。也可以跟着一些优秀的教程进行实践，通过做一些简单的项目来熟悉 Android 开发的流程和方法。

还有就是多逛技术论坛，比如 Stack Overflow、CSDN 等，在上面可以和其他开发者交流经验，解决遇到的问题。并且要不断地阅读优秀的开源代码，学习别人的设计思路和代码实现技巧，这样可以快速提升自己的开发水平。

看过那些开源框架

在 Android 开发中，有很多优秀的开源框架哦。比如Glide，它是一个强大的图片加载框架，使用起来非常方便，能够轻松地实现图片的加载、缓存等功能，还支持多种图片格式和不同的图片加载场景，大大提高了图片加载的效率和稳定性。

还有Retrofit，这是一个网络请求框架，它通过接口和注解的方式来简化网络请求的操作，让开发者可以很方便地发送各种类型的网络请求，并且能够很好地处理请求结果和错误。

RxJava也是很常用的框架，它基于响应式编程的思想，提供了一种简洁的方式来处理异步操作和事件流，通过操作符可以对数据进行各种变换和处理，让异步操作变得更加清晰和易于管理。

ButterKnife框架则是用于视图绑定，它可以通过注解的方式来替代传统的findViewById()方法，减少了很多样板代码，让代码更加简洁和易读。

另外还有EventBus，它是一个事件总线框架，用于在不同的组件之间进行事件传递和通信，使得组件之间的耦合度更低，代码更加模块化和可维护。

学过过机器学习？对于机器学习和移动端你选择哪一个？

如果有学过机器学习的话，会知道机器学习是一个很有趣且有广泛应用前景的领域呀。它涉及到数据的处理、模型的训练和优化等，能够让计算机自动从数据中学习规律并进行预测和决策，在图像识别、语音识别、自然语言处理等很多领域都有出色的表现。

至于在机器学习和移动端之间的选择，这其实要看个人的兴趣和职业规划啦。机器学习有着深厚的理论基础和广阔的研究空间，能够深入到人工智能的核心领域，创造出具有智能决策能力的系统和应用，对于喜欢研究算法、数据挖掘的人来说是个很好的方向。

而移动端开发呢，可以直接面向广大的用户，开发出各种实用的移动应用，给用户带来便捷和丰富的体验，并且移动端的技术也在不断发展，有很多新的特性和功能可以去探索和应用。

如果对算法和数据科学有更浓厚的兴趣，喜欢研究和创新，那么机器学习可能是个不错的选择；如果更倾向于开发具有交互性的应用，注重用户体验和界面设计，并且对移动设备的技术比较感兴趣，那移动端开发会更适合。当然啦，现在也有很多将机器学习应用到移动端的场景，两者也可以很好地结合起来，创造出更智能、更强大的移动应用呢。

数据库 Join

数据库中的 Join 操作是用于将两个或多个表中的数据根据它们之间的关联关系组合在一起。常见的 Join 类型有以下几种：

内连接（INNER JOIN）：只返回两个表中连接条件匹配的行。比如有学生表和成绩表，通过学生 ID 将两个表进行内连接，就只会返回在学生表和成绩表中都存在匹配 ID 的学生及其成绩信息。
左外连接（LEFT JOIN）：返回左表中的所有行，以及右表中与左表匹配的行。如果右表中没有匹配的行，则返回 NULL 值。例如，以学生表为左表，成绩表为右表进行左连接，即使某个学生没有成绩记录，也会在结果中显示该学生的信息，对应的成绩字段为 NULL。
右外连接（RIGHT JOIN）：与左外连接相反，返回右表中的所有行，以及左表中与右表匹配的行。
全外连接（FULL JOIN）：返回两个表中的所有行。如果某一行在另一个表中没有匹配的行，则对应的列返回 NULL 值。

数据库索引，机制

数据库索引就像是一本书的目录，能帮助数据库快速定位和查询数据。其机制主要基于以下原理：

数据结构：通常使用 B + 树等数据结构来存储索引。B + 树的特点是所有数据都存储在叶子节点，并且叶子节点通过指针连接成有序链表，这使得范围查询和顺序访问变得高效。相比之下，二叉树可能会因为数据分布不均匀而导致树的高度过高，查询性能下降。
索引创建：在创建索引时，数据库会根据指定的列或列组合，按照一定的算法构建索引结构。当有新数据插入或更新时，数据库会自动维护索引，确保索引的准确性和有效性。
查询优化：当执行查询语句时，数据库会根据查询条件判断是否可以使用索引。如果可以，就会利用索引快速定位到满足条件的数据所在的位置，而不必全表扫描，从而大大提高查询效率。

Java 垃圾回收

Java 的垃圾回收（Garbage Collection，GC）是 Java 虚拟机（JVM）自动管理内存的一种机制，主要负责回收不再被使用的对象所占用的内存空间，以避免内存泄漏和提高内存利用率。

垃圾回收算法：常见的有标记 - 清除算法、复制算法、标记 - 压缩算法和分代收集算法等。标记 - 清除算法会先标记出所有可回收的对象，然后统一回收这些被标记的对象；复制算法是将内存分为两块，每次只使用其中一块，当这块内存满了，就将存活的对象复制到另一块，然后清理当前这块内存；标记 - 压缩算法在标记完可回收对象后，会将存活的对象向一端移动，然后清理边界以外的内存；分代收集算法则是根据对象的存活周期将内存分为新生代和老年代，对不同代采用不同的回收算法。
垃圾回收器：JVM 中有多种垃圾回收器，如 Serial 收集器、Parallel 收集器、CMS 收集器、G1 收集器等。不同的垃圾回收器适用于不同的场景和应用需求。

Android 里面哪些用到了 LRU

在 Android 中，有很多地方会用到最近最少使用（Least Recently Used，LRU）算法：

内存缓存：比如图片加载框架中，经常会使用 LRU 缓存来管理内存中的图片资源。当缓存满了之后，会优先淘汰最近最少使用的图片，以腾出空间来缓存新的图片。这样可以确保在内存有限的情况下，能够高效地缓存和加载图片，避免内存溢出。
Activity 缓存：在一些应用中，可能会对 Activity 进行缓存管理，使用 LRU 算法可以根据 Activity 的使用频率和时间，来决定是否保留或销毁某个 Activity，从而提高应用的性能和响应速度。
数据库缓存：对于一些频繁访问的数据库数据，也可以采用 LRU 缓存策略。将最近使用过的数据保存在缓存中，下次访问时可以直接从缓存中获取，减少数据库的查询次数，提高数据访问效率。

线程并发，为什么要加锁

在多线程并发编程中，加锁是为了解决多个线程同时访问共享资源时可能出现的问题：

保证数据一致性：当多个线程同时访问和修改同一个共享数据时，如果不加锁，可能会导致数据的不一致性。比如两个线程同时对一个变量进行自增操作，由于线程执行的不确定性，可能会导致最终结果与预期不符。加锁后，同一时刻只有一个线程能够访问被保护的共享资源，从而保证数据的完整性和准确性。
避免资源冲突：多个线程可能会竞争使用同一个资源，如文件、网络连接等。加锁可以确保在任何时刻只有一个线程能够使用该资源，避免资源被多个线程同时访问而产生冲突或错误。
实现线程同步：通过加锁，可以使多个线程按照一定的顺序访问共享资源，实现线程之间的同步。这样可以避免线程之间的操作相互干扰，保证程序的正确性和稳定性。

项目中的自定义 View 是哪种，如何实现的。（讲下项目）

在实际项目中，自定义 View 的类型多种多样，比如可能会自定义一个图表 View 来展示数据，或者自定义一个带有特殊动画效果的按钮等。

假设在一个金融类项目中，需要自定义一个用于展示股票走势的图表 View。实现过程大致如下：首先，需要继承 View 或者 ViewGroup 类，如果图表比较简单，只是绘制一些线条和点，可能继承 View 类就足够了；如果图表比较复杂，包含多个子元素，可能就需要继承 ViewGroup 类来进行布局管理。然后，在自定义 View 的构造方法中，进行一些初始化操作，比如获取上下文、加载自定义属性等。接下来，重写 onMeasure 方法，用于测量 View 的大小，根据传入的测量模式和建议大小，计算出图表 View 合适的宽度和高度。再重写 onDraw 方法，这是绘制图表的核心部分，使用 Canvas 和 Paint 等类，根据数据来绘制出股票走势的线条、坐标轴、数据点等元素。还可能会重写 onTouchEvent 方法，来处理用户的触摸操作，比如缩放、平移图表等。最后，为了使自定义 View 更具通用性，可以提供一些方法来设置数据和样式，让其他开发者能够方便地使用这个自定义 View。

单例模式写一下，把会的都写了，了解枚举实现单例吗

单例模式有多种实现方式，常见的有饿汉式、懒汉式和双重检查锁（DCL）式等。

饿汉式

public class Singleton {
    // 私有静态实例，在类加载时就创建
    private static final Singleton instance = new Singleton();
 
    // 私有构造函数，防止外部实例化
    private Singleton() {}
 
    // 公共的获取实例方法
    public static Singleton getInstance() {
        return instance;
    }
}

懒汉式

public class Singleton {
    // 私有静态实例，初始化为null
    private static Singleton instance = null;
 
    // 私有构造函数，防止外部实例化
    private Singleton() {}
 
    // 公共的获取实例方法，在第一次调用时创建实例
    public static Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

枚举实现单例

public enum Singleton {
    // 定义唯一的实例
    INSTANCE;
 
    // 可以在这里添加其他方法和属性
    public void doSomething() {
        System.out.println("执行单例中的方法");
    }
}

枚举实现单例是一种简洁且线程安全的方式，在 Java 中，枚举类型在类加载时就会被初始化，并且保证每个枚举值都是唯一的，所以天然适合用来实现单例模式。

选择什么字段作为索引，有两个字段，姓和名，选择哪个比较合适

在选择索引字段时，需要考虑多个因素，比如字段的选择性、查询的频率等。如果有 “姓” 和 “名” 两个字段，一般来说选择 “姓” 作为索引可能更合适。因为通常情况下，“姓” 的重复度相对较高，但在一些查询场景中，比如按照姓氏来查找一批用户，使用 “姓” 作为索引可以快速定位到相关的记录。而 “名” 的重复度可能相对较低，但如果以 “名” 作为索引，在查询时可能会导致索引的范围过大，因为可能有很多不同的 “名”，这样在查询时可能需要扫描大量的索引记录，效率反而不高。

当然，如果在实际应用中，经常会有按照 “姓名” 精确查询的需求，那么可以考虑创建联合索引，将 “姓” 和 “名” 组合在一起作为索引，这样可以在精确查询时提高效率。另外，如果存在一些特殊情况，比如某些 “名” 的使用频率非常高，而相关的查询又很频繁，也可以根据具体情况考虑对 “名” 建立索引，但一般来说，在没有特殊需求的情况下，“姓” 作为索引更能满足大多数的查询场景，并且在性能上可能更有优势。

最左匹配原则

最左匹配原则是在使用联合索引时非常重要的一个概念。当创建了一个联合索引，例如（col1, col2, col3），那么这个索引可以用于满足对 col1 的查询，也可以用于满足对 col1 和 col2 的查询，还可以用于满足对 col1、col2 和 col3 的查询，这就是从最左边的列开始匹配。

例如，有一个查询语句SELECT * FROM table WHERE col1 = 'value1' AND col2 = 'value2' AND col3 = 'value3'，数据库会首先使用联合索引中 col1 列进行匹配，找到满足 col1 = 'value1' 的记录，然后在这些记录中再根据 col2 = 'value2' 进行筛选，最后再根据 col3 = 'value3' 进一步筛选。

如果查询语句是SELECT * FROM table WHERE col2 = 'value2' AND col3 = 'value3'，由于没有使用到联合索引的最左边的列 col1，那么这个联合索引就无法被有效利用，数据库可能需要进行全表扫描来获取数据。

即使查询语句是SELECT * FROM table WHERE col1 = 'value1' AND col3 = 'value3'，虽然使用了联合索引中的 col1 和 col3，但由于中间缺少了 col2 的条件，在这种情况下，数据库也只能使用 col1 列进行索引查找，而 col3 列无法利用索引进行快速筛选，可能会导致查询性能下降。所以在设计联合索引和编写查询语句时，要充分考虑最左匹配原则，以提高查询效率。

手写单例（DCL），为什么用 volatile

以下是使用双重检查锁（DCL）实现单例模式的代码：

public class Singleton {
    // 私有静态实例，使用volatile关键字修饰
    private static volatile Singleton instance = null;
 
    // 私有构造函数，防止外部实例化
    private Singleton() {}
 
    // 公共的获取实例方法，使用双重检查锁机制
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

在这里使用volatile关键字是非常重要的。在多线程环境下，当一个线程在创建单例实例时，可能会经历多个步骤，比如分配内存空间、初始化对象等。由于指令重排序的存在，可能会导致在对象还没有完全初始化完成时，就被其他线程访问到。而使用volatile关键字可以禁止指令重排序，保证在写操作完成之前，不会发生读操作，从而确保其他线程能够获取到完整初始化后的单例实例，避免出现空指针异常或其他数据不一致的问题，保证了单例模式在多线程环境下的正确性和稳定性。

手写快排

快速排序是面试时考察最多的排序算法。快速排序（Quick Sort）是一种常用的排序算法，采用分治法（Divide and Conquer）进行排序。其基本思路是通过选择一个基准元素（pivot），将待排序的数组分成两部分，一部分所有元素都小于基准元素，另一部分所有元素都大于基准元素。然后递归地对这两部分继续进行排序，最终达到排序整个数组的效果。

编辑

快速排序的步骤：

选择基准元素：选择数组中的一个元素作为基准元素（常见的选择有第一个元素、最后一个元素、随机选择等）。
分区操作：将数组分成两部分，小于基准的放左边，大于基准的放右边。基准元素最终的位置已经确定。
递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序，直到子数组的大小为1或0，排序完成。

时间复杂度：

最佳情况：O(n log n)，发生在每次分割时都能平衡地分成两部分。
最坏情况：O(n^2)，当数组已经有序或反向有序时，每次选择的基准元素都可能是最小或最大的元素，从而导致不均匀的分割。
平均情况：O(n log n)，在大多数情况下，快速排序的时间复杂度表现良好。

空间复杂度：

快速排序是原地排序，只需要 O(log n) 的栈空间来存储递归调用的状态。
空间复杂度主要取决于递归的深度，最坏情况下是 O(n)，但平均情况下是 O(log n)。

快速排序的Java实现代码：

public class QuickSort {
 
    // 主函数：调用快速排序
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSortHelper(arr, 0, arr.length - 1);
    }
 
    // 快速排序的核心递归函数
    private static void quickSortHelper(int[] arr, int left, int right) {
        if (left < right) {
            // 分区操作，返回基准元素的正确位置
            int pivotIndex = partition(arr, left, right);
            // 递归对基准元素左侧和右侧的子数组排序
            quickSortHelper(arr, left, pivotIndex - 1);
            quickSortHelper(arr, pivotIndex + 1, right);
        }
    }
 
    // 分区操作，返回基准元素的最终位置
    private static int partition(int[] arr, int left, int right) {
        // 选择最右边的元素作为基准元素
        int pivot = arr[right];
        int i = left - 1; // i 指向比基准小的元素区域的最后一个元素
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                // 交换 arr[i + 1] 和 arr[j]
                i++;
                swap(arr, i, j);
            }
        }
        // 将基准元素放到正确位置
        swap(arr, i + 1, right);
        return i + 1; // 返回基准元素的索引
    }
 
    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    // 主函数入口，打印排序后的结果
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 6, 3, 2};
        System.out.println("Original array: ");
        printArray(arr);
        
        quickSort(arr);
 
        System.out.println("Sorted array: ");
        printArray(arr);
    }
 
    // 打印数组的辅助函数
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

如何手写一个正则表达式的解析器，请完整说明

手写正则表达式解析器是一个较为复杂的任务，大致步骤如下：

词法分析：将输入的正则表达式字符串分解为一个个的词法单元，比如字符、字符类、量词、运算符等。可以使用有限自动机来实现，通过状态转移识别不同的词法单元。
语法分析：基于词法分析得到的词法单元，构建语法树来表示正则表达式的结构。例如，对于a*b，可以构建出一个表示*操作符的节点，其左右子节点分别是表示a和b的节点。可以使用递归下降分析法或自底向上的分析法来实现语法分析。
语义分析：对语法树进行遍历和处理，确定正则表达式的语义和逻辑。比如，计算量词的范围，确定字符类的具体字符集合等。
生成匹配算法：根据语法树和语义分析的结果，生成用于匹配输入字符串的算法。常见的有回溯算法和有限自动机算法。回溯算法会尝试所有可能的匹配路径，而有限自动机算法则通过状态转移来进行匹配，效率通常更高。

如何写一个 Shell 脚本，将一个变量转化为系统环境变量？

在 Shell 脚本中，可以使用export命令将一个变量转化为系统环境变量。以下是一个简单的示例：

#!/bin/bash
 
# 定义一个变量
my_variable="Hello World"
 
# 将变量转化为系统环境变量
export my_variable
 
# 执行一个子进程，在子进程中可以访问到这个环境变量
echo "In the main process, my_variable is: $my_variable"
bash -c 'echo "In the child process, my_variable is: $my_variable"'

在这个脚本中，首先定义了一个变量my_variable，然后使用export命令将其导出为系统环境变量。接着，通过执行一个子进程，并在子进程中输出这个环境变量的值，验证其是否能在子进程中被正确访问。

SQL 实现：查询欧洲杯小组积分最高的国家名称

假设存在一个表如下面这样：

teams (队伍表)：
1. team_name (队伍名称)
2. group_name (小组名称)
3. points (积分)

SELECT team_name
FROM teams
WHERE (group_name, points) IN (
    SELECT group_name, MAX(points)
    FROM teams
    GROUP BY group_name
);

解释：

内层查询：SELECT group_name, MAX(points) FROM teams GROUP BY group_name 会计算每个小组的最高积分。
外层查询：外层查询通过 WHERE (group_name, points) 来查找所有与内层查询结果匹配的队伍，从而返回每个小组积分最高的队伍名称。

如果存在多个队伍积分相同，但依然需要返回所有的积分最高队伍，这样的查询可以准确返回所有的符合条件的队伍。

实现链表反转

单链表反转是常见的面试题目之一，下面是关于如何反转一个单链表的思路、时间和空间复杂度分析以及完整的 Java 代码实现。

思路

单链表反转的关键在于改变每个节点的指向，使得原来指向下一个节点的指针指向前一个节点。为了做到这一点，我们可以通过迭代的方式来逐个调整节点的指针。

具体步骤：

初始化三个指针：
1. prev：指向前一个节点，初始化为 null。
2. curr：指向当前节点，初始化为链表的头节点。
3. next：指向当前节点的下一个节点，初始化为 null。
遍历链表：
1. 每次保存 curr 的下一个节点 (next = curr.next)。
2. 将当前节点的 next 指向 prev（反转指向）。
3. 将 prev 移动到 curr，将 curr 移动到 next，继续遍历。
完成遍历后，****prev 会指向新链表的头节点。

时间复杂度

时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历一次整个链表。
空间复杂度：O(1)，我们只用了常数空间来存储指针，不需要额外的空间。

Java 完整代码实现

public class Solution {
 
    // 定义链表节点
    static class ListNode {
        int val;
        ListNode next;
        
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
 
    // 反转链表的函数
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;  // 初始化前一个节点为null
        ListNode curr = head;  // 当前节点从头节点开始
        
        while (curr != null) {
            ListNode next = curr.next;  // 保存下一个节点
            curr.next = prev;  // 反转当前节点的指针
            prev = curr;  // 前一个节点移动到当前节点
            curr = next;  // 当前节点移动到下一个节点
        }
        
        return prev;  // prev最终会是新的头节点
    }
 
    // 打印链表的辅助函数
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
 
    public static void main(String[] args) {
        // 创建一个链表：1 -> 2 -> 3 -> 4 -> 5 -> null
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        
        // 打印原链表
        System.out.println("Original list:");
        printList(head);
        
        // 反转链表
        ListNode reversedHead = reverseList(head);
        
        // 打印反转后的链表
        System.out.println("Reversed list:");
        printList(reversedHead);
    }
}

怎么判断链表有没有相交

判断两个链表是否相交可以采用多种方法。

一种方法是使用双指针。首先分别遍历两个链表，得到两个链表的长度。然后让长链表的指针先走两个链表长度差的步数。之后，同时移动两个链表的指针，每次比较两个指针是否指向相同的节点。如果指向相同节点，那么这两个链表相交；如果直到指针都走到链表末尾还没有相同节点，那么这两个链表不相交。

  // ListNode 定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
 
    public boolean isIntersect(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return false;
        }
 
        // 1. 计算两个链表的长度
        int lenA = getLength(headA);
        int lenB = getLength(headB);
 
        // 2. 让较长的链表先走一段距离，使得两个链表剩余部分长度相同
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }
 
        // 3. 同时遍历两个链表，检查是否相交
        while (headA != null && headB != null) {
            if (headA == headB) {
                return true; // 相交
            }
            headA = headA.next;
            headB = headB.next;
        }
 
        return false; // 不相交
    }
 
    // 计算链表的长度
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

例如，有链表 A 长度为 m，链表 B 长度为 n（假设 m > n）。先让链表 A 的指针先走 m - n 步，然后同时移动 A 和 B 的指针。这种方法的时间复杂度是 O (m + n)，因为需要遍历两个链表来获取长度，然后再同时遍历一部分。

优化的方法可以是使用哈希表。遍历一个链表，将链表中的节点存入哈希表。然后遍历另一个链表，每次检查节点是否在哈希表中。如果在，那么两个链表相交；如果遍历完第二个链表都没有发现相同节点，那么两个链表不相交。这种方法的时间复杂度也是 O (m + n)，但是在平均情况下，哈希表的查找速度很快，可以更快地判断是否相交。

import java.util.HashSet;
 
public class Solution2 {
    // ListNode 定义
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
 
    public boolean isIntersect(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return false;
        }
 
        // 使用哈希集合来存储链表A的所有节点
        HashSet<ListNode> nodeSet = new HashSet<>();
 
        // 遍历链表A并将所有节点添加到哈希集合中
        ListNode currA = headA;
        while (currA != null) {
            nodeSet.add(currA);
            currA = currA.next;
        }
 
        // 遍历链表B，并检查是否存在与链表A中的节点相同的节点
        ListNode currB = headB;
        while (currB != null) {
            if (nodeSet.contains(currB)) {
                return true; // 相交
            }
            currB = currB.next;
        }
 
        return false; // 不相交
    }
 
    public static void main(String[] args) {
        // 创建测试用例
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = new ListNode(5);
 
        ListNode headB = new ListNode(6);
        headB.next = new ListNode(7);
        headB.next.next = headA.next.next; // 相交节点是节点 3
 
        Solution2 solution = new Solution2();
        System.out.println(solution.isIntersect(headA, headB));  // 输出 true
    }
}

海量数据找出前 100 大

对于海量数据找出前 100 大元素，可以使用最小堆的方法，以下是 Java 实现：

import java.util.PriorityQueue;
 
public class TopK {
    public static int[] findTopK(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int num : nums) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (num > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }
        int[] result = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            result[i++] = minHeap.poll();
        }
        return result;
    }
 
    public static void main(String[] args) {
        int[] nums = {1, 10, 5, 20, 15, 8, 30, 25, 12, 18, 22};
        int k = 3;
        int[] topK = findTopK(nums, k);
        for (int num : topK) {
            System.out.print(num + " ");
        }
    }
}

代码解释：

首先创建一个大小为k的最小堆（优先队列）。
遍历数组，如果堆的大小小于k，将元素添加到堆中；如果元素大于堆顶元素，先弹出堆顶元素，再将该元素添加到堆中。
最终堆中存储的就是前k大的元素。

以上代码和方法能够有效地解决相应的链表和海量数据问题，通过合理利用数据结构和算法，可以提高程序的性能和准确性。