腾讯面经学习笔记

前言

‍ 参考地址

操作系统

1. 进程和线程的区别

• 本质区别
  • 进程是操作系统资源分配的基本单位
  • 线程是任务调度和执行的基本单位
• 开销方面
  • 每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；
  • 线程可以看作是轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小
• 稳定性方面
  • 进程中的子进程崩溃，并不会影响其他进程
  • 进程中某个线程崩了，整个进程可能也会崩掉
• 内存分配方面
  • 系统在运行的时候会为每个进程分配不同的内存空间
  • 而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源
• 包含关系
  • 没有线程的进程可以看做是单线程的，如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的
  • 线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程

2. 为什么进程崩溃不会对其他进程产生很大影响？

• 进程隔离性：每个进程都有自己独立的内存空间，当一个进程崩溃时，其内存空间会被操作系统回收，不会影响其他进程的内存空间。这种进程间的隔离性保证了一个进程崩溃不会直接影响其他进程的执行。
• 进程独立性：每个进程都是独立运行的，它们之间不会共享资源，如文件、网络连接等。因此，一个进程的崩溃通常不会对其他进程的资源产生影响。

数据结构

1. 排序算法 | 时间复杂度

• 冒泡排序
  • 通过相邻元素的比较和交换，每次将最大（或最小）的元素逐步“冒泡”到最后（或最前）。
  • ⏰时间复杂度：最好情况下O($n$)，最坏情况下O( n 2n^2 n2)，平均情况下O( n 2n^2 n2)
  • 空间复杂度：O(1)
• 插入排序
  • 将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。
  • ⏰时间复杂度：最好情况下O($n$)，最坏情况下O( n 2n^2 n2)，平均情况下O( n 2n^2 n2)
  • 空间复杂度：
• 选择排序
  • 通过不断选择未排序部分的最小（或最大）元素，并将其放置在已排序部分的末尾（或开头）。
  • ⏰时间复杂度：最好情况下O( n 2n^2 n2)，最坏情况下O( n 2n^2 n2)，平均情况下O( n 2n^2 n2)
  • 空间复杂度：O(1)
• 快速排序
  • 通过选择一个基准元素，将数组划分为两个子数组，使得左子数组的元素都小于（或等于）基准元素，右子数组的元素都大于（或等于）基准元素，然后对子数组进行递归排序。
  • ⏰时间复杂度：最好情况下O(nlo g 2nnlog_2n nlog2​n)，最坏情况下O( n 2n^2 n2)，平均情况下O(nlo g 2nnlog_2n nlog2​n)
  • 空间复杂度：最好情况下O(lo g 2nlog_2n log2​n)，最坏情况下O($n$)
• 归并排序
  • 将数组不断分割为更小的子数组，然后将子数组进行合并，合并过程中进行排序
  • ⏰时间复杂度：O(nlo g 2nnlog_2n nlog2​n)
  • 空间复杂度：O(n)
• 堆排序
  • 通过将待排序元素构建成一个大根堆（或小根堆），然后将堆顶元素与末尾元素交换，再重新调整堆，重复该过程直到排序完成。
  • ⏰时间复杂度：O(nlo g 2nnlog_2n nlog2​n)
  • 空间复杂度：O(1)

2. 归并排序和快速排序的使用场景

• 归并是稳定排序，适合需要排序稳定的场景
• 快速排序是不稳定排序，不适合需要排序稳定的场景。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短

3. 排序稳定是什么意思？

• 排序稳定指的是在排序过程中，对于具有相同排序关键字的元素，在排序后它们的相对位置保持不变。
• 换句话说，如果在排序前两个元素 A 和 B 的值相等，并且 A 在 B 的前面，那么在排序后 A 仍然在 B 的前面，这样的排序就是稳定排序。稳定排序保持了相同元素之间的顺序关系，适用于需要保持原始顺序的场景。

4. 稳定和不稳定排序算法有什么特点？

① 稳定

• 相同元素的相对位置不会改变，排序后仍然保持原始顺序
• 适用于需要保持元素间相对顺序关系的场景，如按照年龄排序后按姓名排序

② 不稳定

• 相同元素的相对位置可能会改变，排序后不保证原始顺序
• 可能会更快，但不适用于需要保持元素间相对顺序关系的场景

MySQL

1. MySQL 的存储引擎有哪些？为什么常用InnoDB？

① MySQL 常用的存储引擎

• InnoDB：

  • 支持事务，支持外键，支持崩溃修复和并发控制
  • 如果需要对事务的完整性要求比较高（比如银行），要求实现并发控制（比如秒杀抢购）
  • 如果需要频繁的更新、删除操作的数据库，也可以选择InnoDB，因为支持事务的提交（commit）和回滚（rollback）。

• MyISAM：

  • 插入数据快，空间和内存使用比较低
  • 如果表主要是用于插入新记录和读出记录，那么选择MyISAM能实现处理高效率

• MEMORY

  • 所有的数据都在内存中，数据的处理速度快，但是安全性不高
  • 如果需要很快的读写速度，对数据的安全性要求较低，可以选择MEMOEY
  • 它对表的大小有要求，不能建立太大的表。所以，这类数据库只使用在相对较小的数据库表
  • 如果只是临时存放数据，数据量不大，并且不需要较高的数据安全性，可以选择将数据保存在内存中的Memory引擎，MySQL中使用该引擎作为临时表，存放查询的中间结果

② InnoDB的优势

• 支持事务
• 最小锁的粒度是行级锁

2. B+ 树 和 B 树

B 树 和 B+ 树 都是通过多叉树的形式，将树的高度变矮，都非常适用于检索磁盘中的数据。

但是 MySQL 默认的存储引擎 InnoDB 采用的是 B+ 作为索引的数据结构，原因如下：

• B+树非叶子节点不存放实际的记录数据，仅存放索引，因此在数据量相同的情况下，相比于非叶子节点既存索引又存记录的 B树，B+树的非叶子节点可以存放更多的索引，因此 B+树可以比 B树更加“矮胖”，查询底层节点的磁盘 IO次数会更少。
• B+树又大量的冗余节点（所有非叶子节点都是冗余索引），这些索引让B+ 树在插入和删除的效率都更高，比如删除根节点时，不会像 B树那样发生复杂的树的调整变化
• B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B树 要实现范围查询，只能通过树的遍历来完成，这会涉及到多个节点的磁盘IO操作，效率较低

3. 除了聚簇索引，还有什么索引？

• 二极索引（非聚簇索引）
• 联合索引
• 前缀索引
• 唯一索引

4. 二级索引存放的有哪些数据？

• 聚簇索引：叶子节点存放的是实际数据，所有完整的数据记录都存放在聚簇索引的叶子节点
• 二级索引：叶子节点存放的是主键值，而不是实际数据

5. 索引失效的情况

• 当我们使用左或者左右模糊匹配的时候，也就是 like %xx 或者 like %xx%这两种方式都会造成索引失效
• 查询条件中对索引列使用了函数
• 查询条件中对索引列使用了表达式计算
• 数据类型转换：MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。如果字符串是索引列，而条件语句中的输入参数是数字的话，那么索引列会发生隐式类型转换，由于隐式类型转换是通过 CAST 函数实现的，等同于对索引列使用了函数，所以就会导致索引失效。
• 联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配，否则就会导致索引失效。

6. 事务隔离级别有哪些？

四个隔离级别如下：

• 读未提交：指一个事务还没提交时，它做的变更就能被其他事务看到
• 读已提交：指一个事务提交之后，它做的变更才能被其他事务看到
• 可重复读：指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别
• 串行化：会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行

按隔离级别高低排序如下：

7. 什么情况下会出现幻读？

在一个事务内多次查询某个符合查询条件的「记录数量」，如果出现前后两次查询到的记录数量不一致的情况，就意味着发生了「幻读」现象。

8. 事务的 MVCC 是怎么实现的？

对于读提交」和「可重复读」隔离级别的事务来说，它们是通过 Read View 来实现的，它们的区别在于创建 Read View 的时机不同：

• 「读提交」隔离级别是在每个 select 都会生成一个新的 Read View，也意味着，事务期间的多次读取同一条数据，前后两次读的数据可能会出现不一致，因为可能这期间另外一个事务修改了该记录，并提交了事务
• 「可重复读」隔离级别是启动事务时生成一个 Read View，然后整个事务期间都在用这个 Read View，这样就保证了在事务期间读到的数据都是事务启动前的记录

这两个隔离级别实现是通过「事务的 Read View 里的字段」和「记录中的两个隐藏列」的比对，来控制并发事务访问同一个记录时的行为，这就叫 MVCC（多版本并发控制）。

‍ InnoDB行记录的三个隐藏字段

一个事务去访问记录的时候，除了自己的更新记录总是可见之外，还有这几种情况：

• 如果记录的 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（多版本并发控制）。

9. 事务之间怎么避免脏读的？

• 要解决脏读现象，就要升级到**「读提交」以上的隔离级别**，这样事务只能读到其他事务已经提交完成的数据，而不会读到未提交事务的数据，就避免脏读的问题。
  

Redis

1. Redis数据类型

① 常见的五种类型

• String（字符串）
• Hash（哈希）
• List（列表）
• Set（集合）
• Zset（有序集合）

随着 Redis 版本的更新，后面又支持了四种数据类型：BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）

② 五种基本数据类型的应用场景

• String 类型的应用场景：缓存对象、常规计数、分布式锁、共享 session 信息等。
• List 类型的应用场景：消息队列（但是有两个问题：1. 生产者需要自行实现全局唯一 ID；2. 不能以消费组形式消费数据）等。
• Hash 类型：缓存对象、购物车等。
• Set 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等。
• Zset 类型：排序场景，比如排行榜、电话和姓名排序等。

③ 新增的数据类型应用场景

• BitMap（2.2 版新增）：二值状态统计的场景，比如签到、判断用户登陆状态、连续签到用户总数等；
• HyperLogLog（2.8 版新增）：海量数据基数统计的场景，比如百万级网页 UV 计数等；
• GEO（3.2 版新增）：存储地理位置信息的场景，比如滴滴叫车；
• Stream（5.0 版新增）：消息队列，相比于基于 List 类型实现的消息队列，有这两个特有的特性**：自动生成全局唯一消息ID，支持以消费组形式消费数据。**

2. 热 key 是什么？怎么解决？

Redis 热key是指呗频繁访问的key，可能会导致单个key的访问量过大，影响系统性能。解决方案包括：

• 使用二级缓存，即JVM本地缓存，减少Redis的读请求
• 对热点key进行分片，将数据分散存储在不同的节点上，减轻单个key的压力
• 开启内存淘汰机制，并选择使用LRU（least recently used，最近最少使用算法）算法来淘汰不常用的key，保证内存中存储的是最热门的数据。
• 设置key的过期时间，确保key在一段时间后自动删除，防止长时间占用内存

3. String 是使用什么存储的” />

• len：记录了字符串的长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。
• alloc：分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。
• flags：用来表示不同类型的SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。
• buf[]：字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。

总的来说，Redis 的 SDS 结构在原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决 C 语言字符串的缺陷。

优点如下：

• O（1）复杂度获取字符串

  • C 语言的字符串长度获取 strlen 函数，需要通过遍历的方式来统计字符串长度，时间复杂度是 O(N)。
  • 而 Redis 的 SDS 结构因为加入了 len 成员变量，那么获取字符串长度的时候，直接返回这个成员变量的值就行，所以复杂度只有O(1)

• 二进制安全

  • 因为 SDS 不需要用 “\0” 字符来标识字符串结尾了，而是有个专门的 len 成员变量来记录长度，所以可存储包含 “\0” 的数据。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 “\0” 字符。

  • 因此， SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据，程序不会对其中的数据做任何限制，数据写入的时候时什么样的，它被读取时就是什么样的。

  • 通过使用二进制安全的 SDS，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，也可以保存任意格式的二进制数据。

• 不会发生缓冲区溢出

  • C 语言的字符串标准库提供的字符串操作函数，大多数（比如 strcat 追加字符串函数）都是不安全的，因为这些函数把缓冲区大小是否满足操作需求的工作交由开发者来保证，程序内部并不会判断缓冲区大小是否足够用，当发生了缓冲区溢出就有可能造成程序异常结束。
  • 所以，Redis 的 SDS 结构里引入了 $alloc和len$ 成员变量，这样 SDS API 通过 $alloc-len$ 计算出剩余可用的空间大小，这样在对字符串做修改操作的时候，就可以由程序内部判断缓冲区大小是否足够用。
  • 而且，当判断出缓冲区大小不够用时，Redis 会自动将扩大 SDS 的空间大小，以满足修改所需的大小。

Java

1. 编译型语言和解释型语言的区别？

• 编译型语言：在程序执行之前，整个源代码会被编译成机器码或者字节码，生成可执行文件。执行时直接运行编译后的代码，速度快，但跨平台性较差。

• 解释型语言：在程序执行时，逐行解释执行源代码，不生成独立的可执行文件。通常由解释器动态解释并执行代码，跨平台性好，但执行速度相对较慢。

• 典型的编译型语言如 C、C++，典型的解释型语言如Python、JavaScript

2. 动态数组的实现有哪些？

ArrayList和Vector都支持动态扩容，都属于动态数组。

3. ArrayList 和 Vector 的比较

• 线程安全性
  • Vector 是线程安全的
  • ArrayList 不是线程安全的
• 扩容策略
  • Vector是扩展1倍
  • ArrayList在底层数组不够用时在原来的基础上扩展0.5倍

4. HashMap 的扩容条件是什么？

Java7 的 HashMap 扩容必须满足两个条件：

• 当前存储的元素个数大小必须 大于等于阈值
• 当前加入的数据是否发生了 hash 冲突

Java8 中扩容只需要满足一个条件：

• 当前存放新值的时候已有元素的个数大于等于阈值