2023.7.27 百度 java 提前批一面题目以及答案

面试题目

题目：

1、网卡零拷贝。

2、说一下 TCP 的拥塞控制，知道慢启动吗？

3、项目中的你是如何设计包头的，内容有啥。 然后如果让你设计一个类似tcp/ip的包头，要有哪些字段？

4、TCP 的拆包粘包。 如果不提前知道包长，数据内又有/0这种分割包的特殊字符，应该怎么办？（转译，当时没答出来）

5、解释一下 hashmap 为什么用红黑树代替链表？ 为什么不用avl树？

6、concurrentskiplist是什么结构，如何查询的？如何回退的？

7、项目为什么用 concurrenthashmap？如何保证线程安全的？ hashmap多线程为什么不安全？（答了会链表回环，然后又问具体是怎么成环的，没打出出来。。。。）

8、hashmap扩容时如何进行挪移的？

9、解释一下list

10、concurrenthashmap 的size（）是怎么做的？

11、hashmap、hashtable、concurrenthashmap 比较

12、synchonize关键字。是不是公平锁？为什么是不公平锁？

13、LRU和LFU。

14、mysql事务隔离级别，有什么区别？有什么用？

15、表锁和行锁都是什么时候加？

16、什么是聚簇索引？

17、mybats介绍一下 $和#的区。

18、介绍一下redis ，说一下缓存击穿，穿透，雪崩。然后怎么避免。

19、说一下布隆过滤器，然后如何减少误判。

20、然后无序数组不排序如何查找中位数(类似快排)

答案解析

问题 1：网卡零拷贝

网卡零拷贝（Zero Copy Networking）是一种技术，旨在减少数据在计算机系统内部传输时的复制次数，从而提高网络性能和吞吐量。

在传统的网络数据传输中，数据需要从应用程序缓冲区复制到内核缓冲区，然后再复制到网卡的缓冲区，最后才能通过网络发送。这些复制操作会占用大量的 CPU 时间和内存带宽，降低系统性能。

而通过使用网卡零拷贝技术，数据可以直接从应用程序缓冲区传输到网卡缓冲区，而无需经过内核缓冲区。这样可以减少数据复制的次数，减少 CPU 和内存的负担，从而提高系统性能和吞吐量。

网卡零拷贝技术可以通过多种方式实现，例如使用 DMA（直接内存访问）引擎、RDMA（远程直接内存访问）等。在具体实现中，需要考虑网络协议的支持、硬件设备的兼容性等因素。

问题 2：说一下 TCP 的拥塞控制，知道慢启动吗？

TCP 通过拥塞控制来避免网络拥塞，保证网络的稳定性和可靠性

拥塞控制过程中涉及到四个算法：慢开始算法、拥塞避免算法、快重传算法、快恢复算法

在发送方维护三个变量：

1. cwnd 表示拥塞窗口大小
2. swnd 表示发送窗口大小，等于 cwnd
3. ssthresh 表示结束慢开始算法的阈值

看下图来说明拥塞控制过程：

当 TCP 建立链接后，执行慢开始算法，先将 swnd = cwnd = 1，然后发送报文，每次收到一个确认报文，那么拥塞窗口 cwnd 会指数级增长，比如：

• 首先发送 1 个报文，然后收到确认报文，然后 cwnd + 1 = 2
• 然后，可以发送 2 个报文，收到确认报文后，cwnd + 2 = 4
• 然后，可以发送 4 个报文，收到确认报文后，cwnd + 4 = 8
• .......

在慢开始算法阶段，拥塞窗口的大小是指数级增长的，直到达到一个阈值 (ssthresh) 为止，就执行拥塞避免算法

拥塞避免算法每次发送完报文，收到确认报文后，拥塞窗口自动 +1，这个是线性增长

当发生超时重传，也就意味着网络出现了拥塞，这个时候会做两件事：

1. 将 ssthresh 阈值更新为当前拥塞窗口的一半
2. 将拥塞窗口设置为 1，开始慢开始算法

当拥塞窗口值达到了 ssthresh 阈值后，又开始拥塞避免算法

在执行拥塞避免算法时，如果收到了 3 个重复确认报文的话，则执行快重传算法，就是将相应的报文立刻重传，而不是等到超时重传

这样，对于个别丢失的报文段，发送方不会出现超时重传，也就不会误认为出现了拥塞，进而不会将拥塞窗口降低为 1，使用快重传可以使整个网络的吞吐量提高约 20%

执行完快重传算法后，立即执行快恢复算法，即：将发送方慢开始阈值 ssthresh 和拥塞窗口 cwnd 调整为当前窗口的一半，然后开始执行拥塞避免算法

问题三：项目中的你是如何设计包头的，内容有啥。 然后如果让你设计一个类似 tcp/ip 的包头，要有哪些字段？

在网络通信中，包头通常包含了与数据传输相关的各种信息，例如数据长度、协议版本、数据类型、数据校验和、传输编码方式等。在项目中，设计包头需要考虑以下几个方面：

• 协议版本：包头需要包含协议版本号，以便接收方能够正确识别协议版本并进行相应的处理。
• 数据类型：包头还需要指定数据的类型，例如请求数据、响应数据等，以便接收方能够正确地解析数据。
• 数据长度：包头需要包含数据长度信息，以便接收方能够正确地处理数据。
• 校验和：包头还可以包含校验和信息，以便接收方能够检验数据的完整性和准确性。
• 其他附加信息：根据具体需求，包头还可以包含其他附加信息，例如数据传输编码方式、数据压缩方式等。

在设计包头时，还需要考虑到包头大小的问题，如果包头太大，将会占用过多的网络带宽，降低数据传输的速度。因此，需要根据具体情况设计最小的包头大小，以便在保证数据传输可靠性的同时，尽可能减少网络带宽的占用

让你设计一个类似 tcp/ip 的包头，这个问题其实就是问你 tcp、ip 包头中的常用字段及其含义了

以下是 ip 首部字段：

以下是 tcp 首部字段：

问题 4：TCP 的拆包粘包。 如果不提前知道包长，数据内又有/0这种分割包的特殊字符，应该怎么办？

TCP 是面向字节流的，而一个消息包可能包含多个字节，所以当使用 TCP 传输消息包的时候，就会出现：

1. TCP 接受者一下子接收到了多个消息包的所有字节，将多个消息包看成一个消息包，这个就是粘包问题
2. TCP 接受者只接收到了一个消息包的一部分字节，这个就是半包问题

不管是粘包问题，还是半包问题，都会使得接受者解析消息包失败，应用进程无法从一个粘包、半包中解析出完整的消息

出现粘包半包问题的根本原因就是：TCP 时面向字节流的，消息没有边界

要解决粘包含半包问题的根本手段是：找出消息的边界

有以下三种方式可以找出消息的边界：

• 固定长度，就是事先规定固定长度的字节作为一个消息，比如一个消息 10 字节，那当接收者每收到 10 个字节，就可以解析成一个消息，这种方式简单，但是浪费空间，比如规定 10 个字节一个消息，但是发送端发送的消息只有 1 个字节，那么剩余的字节就是浪费的，需要补空或者补 0，这种方式一般不推荐使用
• 分隔符，就是可以使用特殊的字符 (比如回车符 \n) 作为分隔符，发送端每次发送完一个消息，就在这个消息后面拼接上分隔符，接收端每次遇到这个分隔符就可以解析一个消息。这种方式即简单，也不会浪费空间，推荐使用

分隔符也有个缺点：数据内容本身出现分隔符时，需要对这个分隔符进行转义

所以每次发送消息时，需要扫描一遍消息，看看有没有出现分隔符，有的话则将其转义

• 使用固定长度字段存储消息内容的长度信息，比如规定使用 4 个字节来存储消息的长度，发送端发送消息的时候，需要事先知道这个消息的长度，然后将这个消息的长度使用 4 个字节存储起来，拼接到消息的前面，接收端接收消息时，事先接收并解析前 4 个字节，然后得到消息内容的长度，再根据长度解析接下来收到的字节

这种方法的优点：精确定位消息内容，内容不需要额外的转义

缺点：消息内容长度有限制，需要提前知道可能的最长的消息的字节数

这个问题我在我的 B 站中有视频讲解：资深程序员老汤

问题 5：解释一下 hashmap 为什么用红黑树代替链表？ 为什么不用avl树？

这道题目的是问你红黑树和 AVL 树的区别，各自的使用场景是什么

红黑树和 AVL 树都是一种常用的自平衡二叉搜索树，它们的主要目的是保证树的高度平衡，从而保证搜索、插入和删除等操作的时间复杂度都是 O(log n) 级别的。

红黑树和 AVL 树的主要区别包括以下几点：

1. 平衡性的要求不同：

AVL 树要求任何节点的左右子树的高度差（平衡因子）不超过 1，因此它的高度更加严格地控制在 O(log n) 级别，搜索效率更高。而红黑树则只要求黑色节点的数量相等，因此它的高度可以略微超过 O(log n) 级别，但是因为旋转操作的次数更少，所以它的插入和删除操作通常比 AVL 树更快。

2. 节点结构不同：

AVL 树的节点需要记录平衡因子，因此它的节点结构比红黑树更加庞大。而红黑树只需要记录颜色信息，因此节点结构相对更为简单，可以节省内存空间。

3. 插入和删除操作的实现不同：

AVL 树在插入和删除节点时需要通过旋转操作来保持平衡，因此它的操作相对复杂。而红黑树通过颜色变换和旋转操作来保持平衡，操作相对简单。

可以看出，红黑树和 AVL 树都是自平衡二叉搜索树，它们的实现方式不同，各有优缺点。红黑树适用于插入、删除操作较多的场景，而 AVL 树适用于搜索操作较多的场景。而 HashMap 会用于插入和删除较多场景，并且从空间的角度来看的话，使用红黑树比较合适

问题 6：concurrentskiplist 是什么结构？如何查询的？如何回退的？

在 Java 中，好像没有 concurrentskiplist，只有 concurrentskiplistMap 和 concurrentskiplistSet

我们可以把 concurrentskiplistMap 和 concurrentskiplistSet 都看成 concurrentskiplist 结构

concurrentskiplist 底层是跳表，而且是一个并发安全的跳表

跳表其实就是一个有序的链表，为了高效的保证链表有序，在链表上加了几层索引

查询的时候， 先比对跳表中的索引，根据索引来定位需要查找的数据在链表中的位置

concurrentskiplistMap 和 concurrentskiplistSet 都没有回退的 API 哈，不知道面试官问这个是什么意思

问题 7：项目为什么用concurrenthashmap？如何保证线程安全的？ hashmap多线程为什么不安全？

答：用 concurrenthashmap 的目的是为了保证线程安全

在 JDK 1.7 中，ConcurrentHashMap 使用了分段锁，即将哈希表分成多个段，每个段拥有一个独立的锁。这样可以在多个线程同时访问哈希表时，只需要锁住需要操作的那个段即可，而不是锁整个哈希表

这种分段锁虽然可以减少锁竞争，但是在高并发场景下，仍然会出现锁竞争，从而导致性能下降，所以在 JDK 1.8 中，对 ConcurrentHashMap 的实现进行了优化，采用 CAS + Synchronized 的机制来保证线程安全

在 JDK 1.8 中，ConcurrentHashMap 会在添加或者删除元素时，首先使用 CAS 操作来尝试修改元素，如果 CAS 失败，则使用 Synchronized 锁住当前的槽，再次尝试调加或者修改，这样锁的粒度减少，锁的竞争也变少，提高了并发性

HashMap 多线程为什么不安全呢？以下四个原因：

1. 多个线程 put 不同键值对时，会导致键值对被覆盖，从而丢失键值对数据
2. 多个线程 put 键值对，导致实际的键值对数量和 size() 返回的数量对不上，因为 size 变量是一个全局的变量
3. 一个线程 get，另一个线程进行扩容，会导致 get 不到键值对，因为有可能刚好这个键值对扩容换了桶
4. 在 JDK 1.7 及以前，在多线程下进行扩容，或产生循环引用的问题，从而使得 CPU 100%，不过在 1.8 后没这个问题了

问题 8：hashmap 扩容时如何进行挪移的？

答：假设扩容前的数组是 oldTab，它容量是 oldCap，扩容后的数组是 newTab，它的容量是 newCap = 2 * oldCap

遍历 oldTab 的所有的桶，假设这个桶在数组中的索引是 j

然后，判断每个桶，分三种情况：

1. 如果当前桶中只有一个键值对，那么直接将这个键值对哈希映射到新的桶中：newTab[e.hash & (newCap - 1)] = e
2. 如果当前桶是一个红黑树，那么将这个红黑树切分成两部分，切分的条件是看 key 的哈希值与 oldCap 取余，即 e.hash & oldCap
3. 如果当前桶是一个链表，那么将这个链表切分成两部分，切分的条件是看 key 的哈希值与 oldCap 取余，即 e.hash & oldCap

问题 9：解释下 list

List 是一种线性集合，实现了 Collection 接口，它具有如下特点：

1. 允许存储重复的元素
2. 元素的存储顺序就是添加元素的顺序，第一个添加的元素肯定在 List 的第一个位置上
3. 支持根据索引下标的操作方法
4. List 是接口，使用数组来实现 List，就是 ArrayList，使用链表来实现 List，就是 LinkedList 了

问题 10：concurrenthashmap 的 size（）是怎么做的？

以下说的是 JDK 8 及其后面版本的 size() 的实现

在 ConcurrentHashMap 中维护了两个成员变量：

• volatile long baseCount
• volatile CounterCell[] counterCells

其中，CounterCell 的源码是这样的：

@jdk.internal.vm.annotation.Contended 
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

在往 ConcurrentHashMap put 键值对成功后：

1. 首先，使用 CAS 对 baseCount 加 1，如果成功，则结束，否则，做第 2 步
2. 在 counterCells 数组中，随机找一个 CounterCell 类型的元素，然后使用 CAS 对这个 CounterCell 元素的 value 加 1，如果成功，则结束，否则，不断尝试 CAS ，直到 value 加 1 成功

那么，在 size() 方法中，计算键值对数量等于：baseCount 的值和 counterCells 中所有元素的 value 值累加

问题 11：hashmap、hashtable、concurrenthashmap 比较

三者的比较如下：

1. HashMap 是线程不安全的，而 HashTable 和 ConcurrentHashMap 是线程安全的，HashTable 中的方法都是 synchronized 的，而 ConcurrentHashMap 使用 cas + synchronized 来实现高性能并发
2. 从继承关系来看，三者都实现了 Map 接口，但是 HashTable 继承了 Dictionary 抽象类，而 HashMap 和 ConcurrentHashMap 都继承了 AbstractMap 抽象类
3. HashMap 中，键和值都可以是 null；HashTable 和 ConcurrentHashMap 中， 键和值都都不可以是 null
4. HashTable 的默认初始容量是 11，默认的加载因子是 0.75，扩容时，容量扩大为原来的两倍再加 1；HashMap 和 ConcurrentHashMap 的默认初始容量都是 16，默认的加载因子都是 0.75，扩容时，容量都是扩大为原来的两倍
5. HashMap 支持 fail-fast，即在遍历 HashMap 过程中，如果 HashMap 的结构被修改 (添加或删除元素)，则会抛出 ConcurrentModificationException；HashTable 不支持 fail-fast，HashTable 使用 Enumeration 来遍历，在遍历的过程中，如果 HashTable 结构发生变化，那么 Enumeration 会失效；ConcurrentHashMap 是 fail-safe 的，也就是说在遍历的过程中，如果 ConcurrentHashMap 结构发生变化，不会抛出 ConcurrentModificationException，但是在遍历时可能会出现数据不一致的情况

问题 12：synchronized 关键字。是不是公平锁？为什么是不公平锁？

synchronized 关键字主要用来加锁，从而保证程序的同步，线程安全，synchronized 添加锁有以下几个特点：

1. 互斥性；同一时间点，只有一个线程可以获得锁
2. 阻塞性：未获得锁的线程只能阻塞，等到锁释放
3. 可重入性：如果一个线程已经获得锁，在锁未释放之前，再次请求锁的时候，是可以获得锁的

synchronized 的使用方法比较简单，主要可以用来修饰方法和代码块

synchronized 加的锁是不公平的，因为 synchronized 获取锁的行为是不公平的，并非是按照申请对象锁的先后时间分配锁的，每次对象锁被释放时，每个线程都有机会获得对象锁，这样有利于提高执行性能，但是也会造成线程饥饿现象

问题 13：LRU 和 LFU。

LRU 是 Least Recently Used 的缩写，意思是最近最少使用，也可以理解成最久未使用

LFU 是 Least Frequently Used 的缩写，意思是最不常用

LRU 和 LFU 一般作为缓存淘汰算法，在缓存满了的时候：

• 如果使用 LRU 的话，那么优先从缓存中淘汰最久未使用的数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”
• 如果使用 LFU 的话，则优先淘汰最不常用数据，如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰，这就是LFU的核心思想

对于 LRU 算法，我们可以使用 HashMap + 双向链表来实现，HashMap 存储数据，双向链表维护键值对的顺序，对于被访问的数据放到双向链表的表头，那么链表表尾的数据就是最久不常用的数据了，可以优先淘汰掉

对于 LFU 算法，我们可以使用 3 个 HashMap 来实现，他们的作用分别是：

1. 第一个 HashMap 存储键值对数据
2. 第二个 HashMap 记录每个 key 使用的次数
3. 第三个 HashMap 记录每个使用相同次数的所有的 key，即使用的次数作为 key，使用次数相等的所有的 key 作为 value，这些 key 用 LinkedHashSet 来维护，这样就可以很容易的找到最久未使用的 key 了

我们还需要有一个变量 minUsedCount 来记录目前最小使用次数，根据 minUsedCount 就可以去第三个 HashMap 中找到使用次数为 minUsedCount 的所有 key，然后找到最久未使用的 key ，淘汰即可

问题 14：mysql事务隔离级别，有什么区别？有什么用？

MySQL 提供了不同的事务隔离级别，用于控制并发事务之间的互相影响程度。以下是MySQL中常见的四个事务隔离级别，按照严格程度递增排列：

1. 读未提交（Read Uncommitted）：最低级别的隔离级别，允许一个事务读取另一个事务尚未提交的数据。这可能导致脏读（Dirty Read）问题，即读取到了未经验证的无效数据。
2. 读已提交（Read Committed）：它确保一个事务只能读取到已经提交的数据。不会出现脏读问题，但可能出现不可重复读（Non-repeatable Read）问题，即同一事务中多次读取同一数据得到的结果可能不一致。
3. 可重复读（Repeatable Read）：这是 MySQL 的默认隔离级别。保证同一事务中多次读取同一数据时，结果始终一致。在可重复读隔离级别下，MySQL使用多版本并发控制（MVCC）来实现。其他事务对数据的修改只能在当前事务提交后才能看到。
4. 序列化（Serializable）：最高级别的隔离级别，确保事务串行执行，避免了脏读、不可重复读和幻读（Phantom Read）问题。幻读指的是在同一事务内多次执行同一查询，但返回的结果集不同。

选择适当的事务隔离级别取决于应用程序的需求和并发访问的特点。较低级别的隔离级别可以提供更高的并发性能，但可能导致数据不一致的问题。较高级别的隔离级别可以提供更严格的数据一致性，但可能牺牲一定的并发性能。

在实际应用中，可以根据具体情况选择合适的隔离级别。如果应用程序对数据一致性要求较高，可以考虑使用可重复读或序列化隔离级别。如果对并发性能要求较高，并且可以容忍一定程度的数据不一致，可以选择读已提交或读未提交隔离级别。

问题 15：表锁和行锁都是什么时候加？

表锁：表锁是在执行一些特定操作时（如 ALTER TABLE、TRUNCATE TABLE、RENAME TABLE等）或使用LOCK TABLES 语句时加上的。表锁会锁定整张表，阻塞其他事务对该表的读写操作，直到当前事务释放锁。表锁对并发性能的影响较大，因为其他事务无法同时访问相同的表。

行锁：行锁是在事务对表中的行进行修改或查询时加上的。行锁的引入是为了提高并发性能，只锁定需要修改或查询的行，而不是整张表。行锁可以防止其他事务修改或删除被锁定的行，但允许其他事务同时对其他行进行操作。

问题 16：什么是聚簇索引？

在 MySQL 中，聚簇索引决定了表中数据的物理存储顺序。聚簇索引的主要特点是数据行的物理顺序与索引的顺序一致。

当创建聚簇索引时，MySQL 会根据指定的列或列组织表的数据存储方式。这意味着具有相邻索引值的行将物理上存储在一起，形成一个数据页。这种存储方式使得数据库系统可以更高效地获取具有连续索引值的行，因为它们在物理上相邻，减少了磁盘I/O操作。

由于聚簇索引决定了数据的物理存储顺序，因此每个表只能有一个聚簇索引

问题 17：mybatis介绍一下 $和#的区别。

$ 和 # 是用于参数替换的两种不同的占位符符号

使用 $ 作为占位符时，MyBatis 会直接将参数的值替换到 SQL 语句中，不进行预编译处理。这意味着参数值直接嵌入到 SQL 语句中，可能存在 SQL 注入的风险。$占位符可以用于替换表名、列名、SQL表达式等

使用 # 作为占位符时，MyBatis 会将参数值以预编译参数的形式传递给数据库，从而提供了更好的安全性和可移植性。# 占位符可以用于替换查询条件、插入、更新等操作的参数

问题 18：介绍一下redis ，说一下缓存击穿，穿透，雪崩。然后怎么避免。

参考我的上一篇面经总结：

问题 19：说一下布隆过滤器，然后如何减少误判。

布隆过滤器本质上就是哈希函数 + 位图

减少误判的两种方法：① 增加哈希函数的数量；② 增加位图的长度

这个问题我在我的 B 站中有视频讲解：资深程序员老汤，找到【海量数据处理】的视频即可

20、然后无序数组不排序如何查找中位数

使用堆：大顶堆 + 小顶堆，大顶堆用于存储较小的一半元素，小顶堆用于存储较大的一半元素

• 如果元素个数是偶数的话，那么中位数就是大顶堆和小顶堆的堆顶元素相加再除以 2
• 如果元素个数是基数的话，可以将算法设计为：如果元素的个数是奇数的话，那么大顶堆中的元素个数比小顶堆中元素个数多 1，这个时候的中位数就是大顶堆中堆顶的元素了