终于等到，腾讯来了...

2024-08-09 13:48:34 浏览数 (2)

图解学习网站：https://xiaolincoding.com

大家好，我是小林。

昨天看到腾讯和字节都开展秋招了，这下互联网公司基本都全部进入到正式的秋招了。

比较有意思的是，腾讯的今年的秋招面向的校招是 2024 年 1 月份之后毕业的，也就是说即使是 24 届的同学也是可以参加今年的腾讯秋招，不过字节不一样，字节是面向 25 届的校招。

我们来看看去年的腾讯校招薪资：

腾讯年总包构成 = 月薪 x 16 签字费 房补 股票

  • 普通 offer：19k～22k x 16 4k x 12（房补） 签字费 3w（部分有），年包：35w～43w
  • sp offer：23k～24kx 16 4k 12（房补） 签字费 3w 股票6w/2 年，年包：44w～49w
  • ssp offer：26k～28kx 16 4k 12（房补） 签字费 5w 股票6w/2 年，年包：50w～58w

股票是明年和后年分波到账，比如 6w 分两年的股票，工作满一年后就可以先拿到 3w，房补一个月 4k 是大厂里面给的最高的，一个人在深圳租房，4k 可以租个环境很不错的房子了。

不过今年腾讯的校招薪资估计会有变化，因为今年腾讯的薪资改个了，把第 13 个月的薪资平摊到每个月，以及房补也算到 base 上，调整之后，腾讯的 base 就会提高了不少，虽然总数没变，但是每个月能拿到的钱变多的了。

既然腾讯校招已经开始，直接来一个同学腾讯提前批时候的面经，面的部门是主 Go 的，而同学的技术栈是 Java，所以面试过程中对于语言这一块没有问题，重点深入拷打了 MySQL、网络、操作系统、算法这四大块。

大家觉得拷打深度如何？

MySQL

熟悉什么数据库?

比较熟悉 mysql 和 redis 数据库，对 mysql 熟悉多一些，项目中都有运用。

Innodb 和 MyIsam 引擎有什么异同，分析一下优缺点?

  • 事务：InnoDB 支持事务，MyISAM 不支持事务，这是 MySQL 将默认存储引擎从 MyISAM 变成 InnoDB 的重要原因之一。
  • 索引结构：InnoDB 是聚簇索引，MyISAM 是非聚簇索引。聚簇索引的文件存放在主键索引的叶子节点上，因此 InnoDB 必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而 MyISAM 是非聚簇索引，数据文件是分离的，索引保存的是数据文件的指针，主键索引和辅助索引是独立的。
  • 锁粒度：InnoDB 最小的锁粒度是行锁，MyISAM 最小的锁粒度是表锁。一个更新语句会锁住整张表，导致其他查询和更新都会被阻塞，因此并发访问受限。
  • count 的效率：InnoDB 不保存表的具体行数，执行 select count(*) from table 时需要全表扫描。而MyISAM 用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快。

Innodb怎么实现的事务?

  • 原子性（Atomicity）：一个事务中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节，而且事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样，就好比买一件商品，购买成功时，则给商家付了钱，商品到手；购买失败时，则商品在商家手中，消费者的钱也没花出去。
  • 一致性（Consistency）：是指事务操作前和操作后，数据满足完整性约束，数据库保持一致性状态。比如，用户 A 和用户 B 在银行分别有 800 元和 600 元，总共 1400 元，用户 A 给用户 B 转账 200 元，分为两个步骤，从 A 的账户扣除 200 元和对 B 的账户增加 200 元。一致性就是要求上述步骤操作后，最后的结果是用户 A 还有 600 元，用户 B 有 800 元，总共 1400 元，而不会出现用户 A 扣除了 200 元，但用户 B 未增加的情况（该情况，用户 A 和 B 均为 600 元，总共 1200 元）。
  • 隔离性（Isolation）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致，因为多个事务同时使用相同的数据时，不会相互干扰，每个事务都有一个完整的数据空间，对其他并发事务是隔离的。也就是说，消费者购买商品这个事务，是不影响其他消费者购买的。
  • 持久性（Durability）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

MySQL InnoDB 引擎通过什么技术来保证事务的这四个特性的呢？

  • 持久性是通过 redo log （重做日志）来保证的；
  • 原子性是通过 undo log（回滚日志） 来保证的；
  • 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
  • 一致性则是通过持久性 原子性 隔离性来保证；

MVCC怎么实现的?

MVCC允许多个事务同时读取同一行数据，而不会彼此阻塞，每个事务看到的数据版本是该事务开始时的数据版本。这意味着，如果其他事务在此期间修改了数据，正在运行的事务仍然看到的是它开始时的数据状态，从而实现了非阻塞读操作。对于「读提交」和「可重复读」隔离级别的事务来说，它们是通过 Read View 来实现的，它们的区别在于创建 Read View 的时机不同，大家可以把 Read View 理解成一个数据快照，就像相机拍照那样，定格某一时刻的风景。

  • 「读提交」隔离级别是在「每个select语句执行前」都会重新生成一个 Read View；
  • 「可重复读」隔离级别是执行第一条select时，生成一个 Read View，然后整个事务期间都在用这个 Read View。

read view 有些啥内容，怎么工作的?

Read View 有四个重要的字段：

  • m_ids ：指的是在创建 Read View 时，当前数据库中「活跃事务」的事务 id 列表，注意是一个列表，“活跃事务”指的就是，启动了但还没提交的事务。
  • min_trx_id ：指的是在创建 Read View 时，当前数据库中「活跃事务」中事务 id 最小的事务，也就是 m_ids 的最小值。
  • max_trx_id ：这个并不是 m_ids 的最大值，而是创建 Read View 时当前数据库中应该给下一个事务的 id 值，也就是全局事务中最大的事务 id 值 1；
  • creator_trx_id ：指的是创建该 Read View 的事务的事务 id。

对于使用 InnoDB 存储引擎的数据库表，它的聚簇索引记录中都包含下面两个隐藏列：

  • trx_id，当一个事务对某条聚簇索引记录进行改动时，就会把该事务的事务 id 记录在 trx_id 隐藏列里；
  • roll_pointer，每次对某条聚簇索引记录进行改动时，都会把旧版本的记录写入到 undo 日志中，然后这个隐藏列是个指针，指向每一个旧版本记录，于是就可以通过它找到修改前的记录。

在创建 Read View 后，我们可以将记录中的 trx_id 划分这三种情况：一个事务去访问记录的时候，除了自己的更新记录总是可见之外，还有这几种情况：

  • 如果记录的 trx_id 值小于 Read View 中的 min_trx_id 值，表示这个版本的记录是在创建 Read View 前已经提交的事务生成的，所以该版本的记录对当前事务可见。
  • 如果记录的 trx_id 值大于等于 Read View 中的 max_trx_id 值，表示这个版本的记录是在创建 Read View 后才启动的事务生成的，所以该版本的记录对当前事务不可见。
  • 如果记录的 trx_id 值在 Read View 的 min_trx_id 和 max_trx_id 之间，需要判断 trx_id 是否在 m_ids 列表中：
  • 如果记录的 trx_id 在 m_ids 列表中，表示生成该版本记录的活跃事务依然活跃着（还没提交事务），所以该版本的记录对当前事务不可见。
  • 如果记录的 trx_id 不在 m_ids列表中，表示生成该版本记录的活跃事务已经被提交，所以该版本的记录对当前事务可见。

这种通过「版本链」来控制并发事务访问同一个记录时的行为就叫 MVCC（多版本并发控制）。

redo log 和 undo log 有什么区别?

redo log 和 undo log 这两种日志是属于 InnoDB 存储引擎的日志，它们的区别在于：

  • redo log 记录了此次事务「完成后」的数据状态，记录的是更新之后的值；
  • undo log 记录了此次事务「开始前」的数据状态，记录的是更新之前的值；

事务提交之前发生了崩溃，重启后会通过 undo log 回滚事务，事务提交之后发生了崩溃，重启后会通过 redo log 恢复事务，如下图：

redo log 怎么工作的?

Buffer Pool 是提高了读写效率没错，但是问题来了，Buffer Pool 是基于内存的，而内存总是不可靠，万一断电重启，还没来得及落盘的脏页数据就会丢失。为了防止断电导致数据丢失的问题，当有一条记录需要更新的时候，InnoDB 引擎就会先更新内存（同时标记为脏页），然后将本次对这个页的修改以 redo log 的形式记录下来，这个时候更新就算完成了。后续，InnoDB 引擎会在适当的时候，由后台线程将缓存在 Buffer Pool 的脏页刷新到磁盘里，这就是 WAL （Write-Ahead Logging）技术。WAL 技术指的是， MySQL 的写操作并不是立刻写到磁盘上，而是先写日志，然后在合适的时间再写到磁盘上。过程如下图：

redo log 是物理日志，记录了某个数据页做了什么修改，比如对 XXX 表空间中的 YYY 数据页 ZZZ 偏移量的地方做了AAA 更新，每当执行一个事务就会产生这样的一条或者多条物理日志。在事务提交时，只要先将 redo log 持久化到磁盘即可，可以不需要等到将缓存在 Buffer Pool 里的脏页数据持久化到磁盘。当系统崩溃时，虽然脏页数据没有持久化，但是 redo log 已经持久化，接着 MySQL 重启后，可以根据 redo log 的内容，将所有数据恢复到最新的状态。有了 redo log，再通过 WAL 技术，InnoDB 就可以保证即使数据库发生异常重启，之前已提交的记录都不会丢失，这个能力称为 crash-safe（崩溃恢复）。可以看出来， redo log 保证了事务四大特性中的持久性。

写入 redo log 的方式使用了追加操作， 所以磁盘操作是顺序写，而写入数据需要先找到写入位置，然后才写到磁盘，所以磁盘操作是随机写。

磁盘的「顺序写 」比「随机写」 高效的多，因此 redo log 写入磁盘的开销更小。

针对「顺序写」为什么比「随机写」更快这个问题，可以比喻为你有一个本子，按照顺序一页一页写肯定比写一个字都要找到对应页写快得多。

可以说这是 WAL 技术的另外一个优点：MySQL 的写操作从磁盘的「随机写」变成了「顺序写」，提升语句的执行性能。这是因为 MySQL 的写操作并不是立刻更新到磁盘上，而是先记录在日志上，然后在合适的时间再更新到磁盘上 。

至此， 针对为什么需要 redo log 这个问题我们有两个答案：

  • 实现事务的持久性，让 MySQL 有 crash-safe 的能力，能够保证 MySQL 在任何时间段突然崩溃，重启后之前已提交的记录都不会丢失；
  • 将写操作从「随机写」变成了「顺序写」，提升 MySQL 写入磁盘的性能。

Mysql 主从同步过程是怎样的？

MySQL 的主从复制依赖于 binlog ，也就是记录 MySQL 上的所有变化并以二进制形式保存在磁盘上。复制的过程就是将 binlog 中的数据从主库传输到从库上。这个过程一般是异步的，也就是主库上执行事务操作的线程不会等待复制 binlog 的线程同步完成。

MySQL 集群的主从复制过程梳理成 3 个阶段：

  • 写入 Binlog：主库写 binlog 日志，提交事务，并更新本地存储数据。
  • 同步 Binlog：把 binlog 复制到所有从库上，每个从库把 binlog 写到暂存日志中。
  • 回放 Binlog：回放 binlog，并更新存储引擎中的数据。

具体详细过程如下：

  • MySQL 主库在收到客户端提交事务的请求之后，会先写入 binlog，再提交事务，更新存储引擎中的数据，事务提交完成后，返回给客户端“操作成功”的响应。
  • 从库会创建一个专门的 I/O 线程，连接主库的 log dump 线程，来接收主库的 binlog 日志，再把 binlog 信息写入 relay log 的中继日志里，再返回给主库“复制成功”的响应。
  • 从库会创建一个用于回放 binlog 的线程，去读 relay log 中继日志，然后回放 binlog 更新存储引擎中的数据，最终实现主从的数据一致性。

在完成主从复制之后，你就可以在写数据时只写主库，在读数据时只读从库，这样即使写请求会锁表或者锁记录，也不会影响读请求的执行。

buffer pool 中的数据什么时候刷盘？刷盘是怎样的流程？

引入了 Buffer Pool 后，当修改数据时，首先是修改 Buffer Pool 中数据所在的页，然后将其页设置为脏页，但是磁盘中还是原数据。

因此，脏页需要被刷入磁盘，保证缓存和磁盘数据一致，但是若每次修改数据都刷入磁盘，则性能会很差，因此一般都会在一定时机进行批量刷盘。

可能大家担心，如果在脏页还没有来得及刷入到磁盘时，MySQL 宕机了，不就丢失数据了吗？

这个不用担心，InnoDB 的更新操作采用的是 Write Ahead Log 策略，即先写日志，再写入磁盘，通过 redo log 日志让 MySQL 拥有了崩溃恢复能力。

下面几种情况会触发脏页的刷新：

  • 当 redo log 日志满了的情况下，会主动触发脏页刷新到磁盘；
  • Buffer Pool 空间不足时，需要将一部分数据页淘汰掉，如果淘汰的是脏页，需要先将脏页同步到磁盘；
  • MySQL 认为空闲时，后台线程会定期将适量的脏页刷入到磁盘；
  • MySQL 正常关闭之前，会把所有的脏页刷入到磁盘；

刷盘的流程就是调用 write 将Buffer Pool 中的数据写入到操作系统的 pagecache，然后再调用 fasyn 将 pagecache 中的数据写入到磁盘。

redolog 和 binlog 的两阶段提交怎么工作的？为什么这么设计？

事务提交后，redo log 和 binlog 都要持久化到磁盘，但是这两个是独立的逻辑，可能出现半成功的状态，这样就造成两份日志之间的逻辑不一致。

在 MySQL 的 InnoDB 存储引擎中，开启 binlog 的情况下，MySQL 会同时维护 binlog 日志与 InnoDB 的 redo log，为了保证这两个日志的一致性，MySQL 使用了内部 XA 事务（是的，也有外部 XA 事务，跟本文不太相关，我就不介绍了），内部 XA 事务由 binlog 作为协调者，存储引擎是参与者。

当客户端执行 commit 语句或者在自动提交的情况下，MySQL 内部开启一个 XA 事务，分两阶段来完成 XA 事务的提交，如下图：

从图中可看出，事务的提交过程有两个阶段，就是将 redo log 的写入拆成了两个步骤：prepare 和 commit，中间再穿插写入binlog，具体如下：

  • prepare 阶段：将 XID（内部 XA 事务的 ID） 写入到 redo log，同时将 redo log 对应的事务状态设置为 prepare，然后将 redo log 持久化到磁盘（innodb_flush_log_at_trx_commit = 1 的作用）；
  • commit 阶段：把 XID 写入到 binlog，然后将 binlog 持久化到磁盘（sync_binlog = 1 的作用），接着调用引擎的提交事务接口，将 redo log 状态设置为 commit，此时该状态并不需要持久化到磁盘，只需要 write 到文件系统的 page cache 中就够了，因为只要 binlog 写磁盘成功，就算 redo log 的状态还是 prepare 也没有关系，一样会被认为事务已经执行成功；

我们来看看在两阶段提交的不同时刻，MySQL 异常重启会出现什么现象？下图中有时刻 A 和时刻 B 都有可能发生崩溃：

不管是时刻 A（redo log 已经写入磁盘， binlog 还没写入磁盘），还是时刻 B （redo log 和 binlog 都已经写入磁盘，还没写入 commit 标识）崩溃，此时的 redo log 都处于 prepare 状态。在 MySQL 重启后会按顺序扫描 redo log 文件，碰到处于 prepare 状态的 redo log，就拿着 redo log 中的 XID 去 binlog 查看是否存在此 XID：

  • 如果 binlog 中没有当前内部 XA 事务的 XID，说明 redolog 完成刷盘，但是 binlog 还没有刷盘，则回滚事务。对应时刻 A 崩溃恢复的情况。
  • 如果 binlog 中有当前内部 XA 事务的 XID，说明 redolog 和 binlog 都已经完成了刷盘，则提交事务。对应时刻 B 崩溃恢复的情况。

可以看到，对于处于 prepare 阶段的 redo log，即可以提交事务，也可以回滚事务，这取决于是否能在 binlog 中查找到与 redo log 相同的 XID，如果有就提交事务，如果没有就回滚事务。这样就可以保证 redo log 和 binlog 这两份日志的一致性了。

所以说，两阶段提交是以 binlog 写成功为事务提交成功的标识，因为 binlog 写成功了，就意味着能在 binlog 中查找到与 redo log 相同的 XID。

操作系统

Linux怎么做虚拟内存管理？

用户态和内核态的区别是什么？

内核态和用户态是操作系统中的两种运行模式。它们的主要区别在于权限和可执行的操作：

  • 内核态（Kernel Mode）：在内核态下，CPU可以执行所有的指令和访问所有的硬件资源。这种模式下的操作具有更高的权限，主要用于操作系统内核的运行。
  • 用户态（User Mode）：在用户态下，CPU只能执行部分指令集，无法直接访问硬件资源。这种模式下的操作权限较低，主要用于运行用户程序。

内核态的底层操作主要包括：内存管理、进程管理、设备驱动程序控制、系统调用等。这些操作涉及到操作系统的核心功能，需要较高的权限来执行。分为内核态和用户态的原因主要有以下几点：

  • 安全性：通过对权限的划分，用户程序无法直接访问硬件资源，从而避免了恶意程序对系统资源的破坏。
  • 稳定性：用户态程序出现问题时，不会影响到整个系统，避免了程序故障导致系统崩溃的风险。
  • 隔离性：内核态和用户态的划分使得操作系统内核与用户程序之间有了明确的边界，有利于系统的模块化和维护。

内核态和用户态的划分有助于保证操作系统的安全性、稳定性和易维护性。

什么时候会从用户态到内核态？

这里细分为3种情况。：

  • 发生系统调用时：这是处于用户态的进程主动请求切换到内核态的一种方式。用户态的进程通过系统调用申请使用操作系统提供的系统调用服务例程来处理任务。而系统调用的机制，其核心仍是使用了操作系统为用户特别开发的一个中断机制来实现的，即软中断。
  • 产生异常时：当CPU执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行的进程切换到处理此异常的内核相关的程序中，也就是转到了内核态，如缺页异常。
  • 外设产生中断时：中断当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作的完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

可以看到上述三种由用户态切换到内核态的情况中，只有系统调用是进程主动请求发生切换的，中断和异常都是被动的。

Linux文件系统讲一下？

文件系统的种类众多，而操作系统希望对用户提供一个统一的接口，于是在用户层与文件系统层引入了中间层，这个中间层就称为虚拟文件系统（_Virtual File System，VFS_）。

VFS 定义了一组所有文件系统都支持的数据结构和标准接口，这样程序员不需要了解文件系统的工作原理，只需要了解 VFS 提供的统一接口即可。

在 Linux 文件系统中，用户空间、系统调用、虚拟机文件系统、缓存、文件系统以及存储之间的关系如下图：

Linux 支持的文件系统也不少，根据存储位置的不同，可以把文件系统分为三类：

  • _磁盘的文件系统_，它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统。
  • _内存的文件系统_，这类文件系统的数据不是存储在硬盘的，而是占用内存空间，我们经常用到的 /proc 和 /sys 文件系统都属于这一类，读写这类文件，实际上是读写内核中相关的数据数据。
  • _网络的文件系统_，用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等。

文件系统首先要先挂载到某个目录才可以正常使用，比如 Linux 系统在启动时，会把文件系统挂载到根目录。

软链接和硬链接的区别？

硬链接是多个目录项中的「索引节点」指向一个文件，也就是指向同一个 inode，但是 inode 是不可能跨越文件系统的，每个文件系统都有各自的 inode 数据结构和列表，所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode，那么只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。

软链接相当于重新创建一个文件，这个文件有独立的 inode，但是这个文件的内容是另外一个文件的路径，所以访问软链接的时候，实际上相当于访问到了另外一个文件，所以软链接是可以跨文件系统的，甚至目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了而已。

image.png

什么命令可以查看各个进程占用的资源？

可以通过 ps 命令或者 top 命令来查看进程的状态。比如我想看 nginx 进程的状态，可以在 linux 输入这条命令：

top 命令除了能看进程的状态，还能看到系统的信息，比如系统负载、内存、cpu 使用率等等

top命令显示出来的各个字段都是啥意思？

主要会展示：

  • Load average（平均负载）：显示系统在最近1分钟、5分钟和15分钟内的平均负载情况。
  • Tasks（任务）：显示当前运行、睡眠、停止和僵尸状态的进程数量。
  • CPU usage（CPU使用情况）：显示CPU的总体使用率以及每个CPU核心的使用率。
  • Memory usage（内存使用情况）：显示物理内存的总量、已使用量、空闲量、缓冲区和缓存区的使用量。
  • Swap usage（交换空间使用情况）：显示交换空间的总量、已使用量和剩余量。
  • 进程列表：显示当前运行的进程列表，包括进程的PID、用户、CPU占用率、内存占用率、进程状态、启动时间和进程命令。

怎么查看某个端口是否被占用？

可以通过 lsof 或者 netstate 命令查看，比如查看 80 端口。lsof ：

代码语言：javascript复制
[root@xiaolin ~]# lsof -i :80
COMMAND     PID  USER   FD   TYPE   DEVICE SIZE/OFF NODE NAME
nginx       929  root    6u  IPv4    15249      0t0  TCP *:http (LISTEN)
nginx       929  root    7u  IPv6    15250      0t0  TCP *:http (LISTEN)
nginx       934 nginx    6u  IPv4    15249      0t0  TCP *:http (LISTEN)
nginx       934 nginx    7u  IPv6    15250      0t0  TCP *:http (LISTEN)
AliYunDun 16507  root   10u  IPv4 40212783      0t0  TCP xiaolin:41830->100.100.30.26:http (ESTABLISHED)

netstate：

代码语言：javascript复制
[root@xiaolin ~]# netstat -napt | grep 80
tcp        0      0 0.0.0.0:80       0.0.0.0:*       LISTEN      929/nginx: master p

网络

CLOSE_WAIT状态，讲一下这个状态是什么时候出现的？

首先要明白close_wait状态是在tcp通信四次握手时的一个中间状态：

即当被动关闭方发送完ACK后进入的状态。这个状态的结束，即要达到下一个状态LASK_ACK需要在发无端发送完剩余的数据后(send)、调用close函数之后。close_wait状态出现的原因是被动关闭方未关闭socket造成，如果将大量CLOSE_WAIT的解决办法总结为一句话那就是：查代码，因为问题出在服务器程序中。

TIME_WAIT什么时候出现？有什么作用？

TIME_WAIT 是指在TCP 连接关闭后，为了保证数据的可靠传输，TCP 协议需要等待一段时间（通常是2MSL，即两倍的最大报文段生存时间），以确保对方接收到了最后一个ACK 报文段，同时也为了防止已经失效的连接请求报文段被传到下一个连接中。在这段等待时间内，TCP 连接处于TIME_WAIT 状态。TIME_WAIT 作用主要有两个：

  • **可靠地实现TCP全双工连接的终止**：保证客户端发送的最后一个ACK报文能够到达服务器，因为这个ACK报文可能丢失，站在服务器的角度看来，我已经发送了FIN ACK报文请求断开了，客户端还没有给我回应，应该是我发送的请求断开报文它没有收到，于是服务器又会重新发送一次，而客户端就能在这个2MSL时间段内收到这个重传的报文，接着给出回应报文，并且会重启2MSL计时器。
  • **允许老的报文在网络中消逝**：防止类似与“三次握手”中提到了的“已经失效的连接请求报文段”出现在本连接中。客户端发送完最后一个确认报文后，在这个2MSL时间中，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失。这样新的连接中不会出现旧连接的请求报文。

算法

写个快排排序

快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。快排的过程简单的说只有三步：

  • 首先从序列中选取一个数作为基准数
  • 将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 partition）
  • 然后分别对基准的左右两边重复以上的操作，直到数组完全排序

具体按以下步骤实现：

  • 1，创建两个指针分别指向数组的最左端以及最右端
  • 2，在数组中任意取出一个元素作为基准
  • 3，左指针开始向右移动，遇到比基准大的停止
  • 4，右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
  • 5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
  • 6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序

注意这里的基准该如何选择？最简单的一种做法是每次都是选择最左边的元素作为基准，但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 Math.random() 来随机选取一个数作为基准。

代码实现：

代码语言：javascript复制
public class QuickSort {
    // 快速排序算法
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            // 递归排序左半部分
            quickSort(arr, low, pi - 1);
            // 递归排序右半部分
            quickSort(arr, pi   1, high);
        }
    }

    // 划分函数，用于找到基准元素的正确位置
    int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // 初始化较小元素的索引

        for (int j = low; j < high; j  ) {
            if (arr[j] < pivot) {
                i  ;
                // 交换元素
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准元素放到正确的位置
        int temp = arr[i   1];
        arr[i   1] = arr[high];
        arr[high] = temp;

        return i   1; // 返回基准元素的位置
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value   " ");
        }
    }
}
文件系统 磁盘 事务 数据 腾讯

0 人点赞