滴滴 一面总结

1.你能说一下 JAVA 有哪些集合吗？

2.HashMap 和 TreeMap 有什么区别？

3.解决哈希冲突的方法

4.那 TreeMap 底层是什么数据结构?

红黑树+HashMap

5.常见的树有哪些？

6.二叉搜索树、平衡树、红黑树区别是什么？二叉搜索树（Binary Search Tree, BST）、平衡树（Balanced Tree）和红黑树（Red-Black Tree）都是一种数据结构，用于快速地搜索、插入、删除数据。它们之间的区别如下：

1. 二叉搜索树（BST）是一种二叉树，它的左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。这个特性使得在 BST 上进行搜索、插入和删除操作非常高效。

2. 平衡树是指树中每个节点的左右子树高度相差不超过 1 的二叉搜索树。常见的平衡树有 AVL 树、红黑树等。由于 BST 可能会出现极端情况下的不平衡（如只插入递增或递减的数据），导致最坏情况下时间复杂度退化到 O(n)，因此出现了平衡树这种数据结构，它可以自动调整节点位置来保证树的平衡性，从而保证最坏情况下的时间复杂度依然是 O(log n)。

3. 红黑树是一种自平衡的二叉搜索树，它是一种近似平衡的二叉树，能够确保任何一个节点的左右子树的高度差不会超过两倍。红黑树的节点被标记为红色或黑色，每个节点的颜色是用来确保在插入、删除节点时，树的平衡性不被破坏的。红黑树的性质保证了它的最坏情况下的时间复杂度是 O(log n)，是一种高效的数据结构，广泛应用于编译器、操作系统、数据库等领域。

总之，BST 是最简单的搜索树，平衡树能够解决 BST 的不平衡问题，红黑树是一种高效的自平衡树。

7.Mysql 采用 B+树当索引的原因是什么？

MySQL 采用 B+树作为索引的原因有以下几点：

1. B+树支持高效的范围查询，适合于数据库中频繁进行的范围查询操作。

2. B+树具有较高的数据访问性能，能够快速定位到目标数据所在的位置，提高了数据库的查询效率。

3. B+树的叶子节点构成了一个有序链表，便于按照顺序遍历数据，支持 ORDER BY 操作。

4. B+树的节点通常被设计为一页大小，适合于现代操作系统的内存管理方式，能够最大化地利用内存资源，减少磁盘 IO 的次数。

5. B+树的平衡性良好，插入和删除操作不会导致树的结构失衡，保证了查询效率的稳定性和可靠性。

8.为什么 B+树可以顺序查找？

B+树可以顺序查找的原因是，B+树中的数据按照键值有序排列，并且相邻节点之间有指针相连，可以很快地遍历整个 B+树。在进行顺序查找时，可以从 B+树的最左叶子节点开始，依次遍历所有的叶子节点，完成整个 B+树的遍历。由于 B+树的节点可以存储多个键值，因此可以减少 I/O 操作，提高查找效率。

9.跳表的时间查询复杂度是多少？

跳表（Skip List）是一种支持快速查找的数据结构，它通过在原始有序链表上建立多级索引来加速查找操作。跳表的时间查询复杂度为 O(log n)，其中 n 是跳表中元素的个数。

在跳表中，每一层索引都是原始链表的一个子集，且每一层的索引节点数量是下一层索引节点数量的一半。因此，跳表的高度为 log n，其中 n 是元素的数量。

在进行查询操作时，从跳表的顶层索引开始遍历，找到第一个大于或等于要查找元素的索引节点，然后转到下一层索引进行查找。直到最后一层索引找到该元素或者该元素不存在为止。

由于跳表的高度是 log n，因此查找操作的时间复杂度为 O(log n)。与二叉搜索树相比，跳表的平均情况下查询操作的时间复杂度也为 O(log n)，但是跳表的实现相对简单，且在并发环境下具有较好的性能表现。

10.Mysql 索引有哪些索引？

Hash、B+树、Full-text 索引

11.假如我现在建了一个联合索引，abc，选 b 或者 c 不带 a，会用到索引吗？

12.select a 改为 select *，where 条件不变，会用到索引吗？

select * 走不走索引与结果集大小无关，而应该和结果集数量有关。

查询的结果集，超过了总行数 25%，优化器就会认为没有必要走索引了。

13.你知道覆盖索引吗？

1.就是 select 的数据列只用从索引中就能够取得，不必从数据表中读取，换句话说查询列要被所使用的索引覆盖。

2.高效找到行的一个方法，当能通过检索索引就可以读取想要的数据，那就不需要再到数据表中读取行了。如果一个索引包含了（或覆盖了）满足查询语句中字段与条件的数据就叫 做覆盖索引。

3.是非聚集组合索引的一种形式，它包括在查询里的 Select、Join 和 Where 子句用到的所有列（即建立索引的字段正好是覆盖查询语句[select 子句]与查询条件[Where 子句]中所涉及的字段，也即，索引包含了查询正在查找的所有数据）

14.为什么要主键索引和其他的索引联合使用？为什么要对其他字段设索引？

联合索引指的是其他字段和主键索引一起做了一个索引，此时在进行查询的时候，会走向左匹配原则，不会回表查询。

因为有些字段的查询如果通过主键索引，难以查找到真实数据。

15.做过 sql 分析吗？假如给你一个慢查询的 sql，你怎么分析？1.定义慢查询

2.数据库开启慢查询日志

3.找到慢查询日志-查找查询时间最慢的 sql

4.explain 分析，explain 各个字段的解释

5.profile 分析，Show profile 是 mysql 提供可以用来分析当前会话中语句执行的资源消耗情况--看到是磁盘 IO 还是网络 IO 的问题

16.explain 语句你看的话，你会看什么字段？id、type、key、rows、Extra

id：每个执行计划都有一个 id，如果是一个联合查询 union，这里还将有多个 id。

select_type：表示 SELECT 查询类型，常见的有四种

SIMPLE（普通查询，即没有联合查询、子查询）、

PRIMARY（主查询）、UNION（UNION 中后面的查询）、SUBQUERY（子查询）等。

table：当前执行计划查询的表，如果给表起别名了，则显示别名信息。

partitions：访问的分区表信息。

type：这是重要的列，显示连接使用了何种类型。从最好到最差的连接类型为：system > const > eq_ref > ref > range > index > ALL。

system/const：表中只有一行数据匹配，此时根据索引查询一次就能找到对应的数据。如果是 B + 树索引，我们知道此时索引构造成了多个层级的树，当查询的索引在树的底层时，查询效率就越低。const 表示此时索引在第一层，只需访问一层便能得到数据。

eq_ref：使用唯一索引扫描，常见于多表连接中使用主键和唯一索引作为关联条件。

ref：非唯一索引扫描，还可见于唯一索引最左原则匹配扫描。

range：索引范围扫描，比如，<，>，between 等操作。

index：索引全表扫描，此时遍历整个索引树。

ALL：表示全表扫描，需要遍历全表来找到对应的行。

possible_keys：可能使用到的索引。

key：实际使用到的索引。

key_len：实际使用的索引的长度。

ref：关联 id 等信息。

rows：查找到记录所扫描的行数。

filtered：查找到所需记录占总扫描记录数的比例。

Extra：额外的信息。

17.两个表 join 有什么需要注意的吗？你怎么判断哪个是主表呢？Left join 可以和 Right join 做转换吗？

18.你知道 Join 的时候，哪个作为主表会有什么影响吗

19.事务具有哪些性质？

20.这几个性质是怎么保证的呢？

21.以 InnoDB 为例，可以设置为行锁或者表锁吗？

22.什么时候会表锁？

23.幻读和可重复读的区别？

24.Redis 了解的怎么样？

25.Redis 存在事务吗？

26.Redis 中开启一个事务的命令你知道吗 Multi：开启事务

开启一个事务(相当于数据库事务中的 begin trasication)，总是返回 OK。

Exec (execute): 提交事务

命令负责触发并执行事务中的所有命令（相当于数据库事务中的 commit）

Discard: 回滚事务

回滚事务(相当于数据库事务中的 rollback)。 当执行 DISCARD 命令时， 事务会被放弃， 事务队列会被清空， 并且客户端会从事务状态中退出。

Watch：

redis 使用关键字实现乐观锁（check-and-set）。被 WATCH 的键会被监视，并会发觉这些键是否被改动过了。 如果有至少一个被监视的键在 EXEC 执行之前被修改了， 那么整个事务都会被取消， EXEC 返回 nil-reply 来表示事务已经失败。

27.Redis 的数据结构

28.Zset 底层的数据结构是怎么样的？

• 压缩表 ziplist

• 跳表 skiplist

29.只有跳表吗？还有其他的吗？

压缩表 ziplist

30.get 一个 key 时间复杂度是多少？

时间复杂度 O(log(n))，n 为当前成员个数

31.Zset 查询命令是 S

32.事务有个持久性，Redis 的事务持久化怎么保证的？

1、单独的隔离操作

事务中的所有命令都会序列化、按顺序执行，事务执行过程中不会被其他客户端发来的命令打断。

2、没有隔离级别的概念

队列中的命令在没有被提交之前都不会被实际执行，事务提交前任何命令都不会被执行

3、不保证原子性

队列中如果有一个命令执行失败，其他命令仍会被执行 不会回滚。

33.你知道 RDB 和 AOF 的区别是什么吗？

RDB:缺点是可能会丢失从上次快照到当前时间点之间未做快照的数据,默认 5 分钟

AOF:默认为每秒钟 fsync 一次，即将执行的命令保存到 AOF 文件当中，这样即使 redis 服务器发生故障最多只丢失 1 秒钟之内的数据

34.AOF 可以一分钟刷一次吗？可以一秒刷一次吗？AOF 保存的时候，是同步还是异步的？

aof 默认每秒执行一次记录，可能会丢失这 1s 的数据，默认大小 64mb.

35.怎么异步执行的？

被写入 AOF 文件的所有命令都是以 Redis 的命令请求协议格式保存的（Redis 的请求协议是纯文本的）。

36.过期是怎么做到的？Redis 的源码

Redis 通过一个保存在 redisDb 中的 expires 字典来保存数据过期的时间。

过期键判定

通过过期字典，程序可以用以下步骤检查一个给定键是否过期：

检查给定键是否存在于过期字典:如果存在，那么取得键的过期时间。

检查当前 UNIX 时间截是否大于键的过期时间:如果是的话，那么键已经过期;否则的话，键未过期。

过期键删除策略

如果假设你设置了一批 key 只能存活 1 分钟，那么 1 分钟后，Redis 是怎么对这批 key 进行删除的呢？

常用的过期数据的删除策略就两个（重要！自己造缓存轮子的时候需要格外考虑的东西）：

定时删除:在设置键的过期时间的同时，创建一个定时器( timer )，让定时器在键的过期时间来临时，立即执行对键的删除操作。

惰性删除 ：只会在取出 key 的时候才对数据进行过期检查。这样对 CPU 最友好，但是可能会造成太多过期 key 没有被删除。

定期删除 ： 每隔一段时间抽取一批 key 执行删除过期 key 操作。并且，Redis 底层会通过限制删除操作执行的时长和频率来减少删除操作对 CPU 时间的影响。

定时删除对内存友好，但对 CPU 最不友好。惰性删除对 CPU 更加友好。而定期删除是前两种的整合和折中，但是间隔时间不好控制，如果执行间隔太过频繁，就会变成定时删除，如果执行间隔较长，就会变成惰性删除。

Redis 采用的是 定期删除+惰性/懒汉式删除 。

但是，仅仅通过给 key 设置过期时间还是有问题的。因为还是可能存在定期删除和惰性删除漏掉了很多过期 key 的情况。这样就导致大量过期 key 堆积在内存里，然后就 Out of memory 了。

怎么解决这个问题呢？答案就是： Redis 内存淘汰机制。

37.你用过消息队列吗？

38.你了解它的机制吗？

39.操作系统你了解过吗？

40.进程、线程和协程的区别

一、进程

进程是程序一次动态执行的过程，是程序运行的基本单位。

每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。

进程占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、页表、文件句柄等）比较大，但相对比较稳定安全。协程切换和协程切换

总结：保存在硬盘上的程序运行以后，会在内存空间里形成一个独立的内存体，这个内存体有自己独立的地址空间，有自己的堆，上级挂靠单位是操作系统。操作系统会以进程为单位，分配系统资源（CPU 时间片、内存等资源），进程是资源分配的最小单位。

二、线程

线程又叫做轻量级进程，是 CPU 调度的最小单位。

线程从属于进程，是程序的实际执行者。一个进程至少包含一个主线程，也可以有更多的子线程。

多个线程共享所属进程的资源，同时线程也拥有自己的专属资源。

程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。

总结：线程从属于进程，是程序的实际执行者。一个进程可以有多个线程，最少有一个线程，但一个线程只能有一个进程。

三、协程

协程是一种用户态的轻量级线程，协程的调度完全由用户控制。

一个线程可以拥有多个协程，协程不是被操作系统内核所管理，而完全是由程序所控制。

与其让操作系统调度，不如我自己来，这就是协程

总结：协程最主要的作用是在单线程的条件下实现并发的效果，但实际上还是串行的(像 yield 一样)一个线程可以拥有多个协程，协程不是被操作系统内核所管理，而完全是由程序所控制。

41.进程是怎么管理线程的？

42.操作系统管理的时候是调度线程还是进程？

调度包含了进程及线程，除此外还包括进程组。

43.一段程序加载到内存当中，会有哪些东西分别放在哪里？

有四个部分,分别是:代码段、数据段、栈、堆。

代码段为源程序编译后的机器指令;

数据段为程序中的全局或具永久生命期的数据;

栈为函数调用使用的可变大小内存区;

堆为程序中动态分配内存使用。

44.虚拟机栈和堆有什么区别？

45.你说垃圾清理大部分发生在堆里，那小部分是清理什么？

方法区也是一种常见的垃圾清理区域，主要用于存储类的元数据信息、静态变量、常量等数据。Java 虚拟机会根据不同的垃圾清理算法和收集策略，对这些内存区域进行定期或不定期的垃圾清理。

46.Java new 一个东西，放在堆里还是栈里？

在 Java 中，通过关键字 new 创建的对象实例通常会被分配到 Java 堆内存中。

47.它一定是在堆里面吗？

Java 中使用 new 关键字创建的对象一般都是在堆（heap）中分配内存空间的，但是也有一些例外。

首先，如果对象的大小比较小，编译器可能会将它们分配在栈（stack）中，而不是在堆中。这种情况下，对象的生命周期受到限制，因为一旦离开了它们的作用域，它们就会被销毁。

其次，Java 中还有一些特殊的对象，如字符串常量（String literals）和基本类型的包装类（Wrapper classes），它们是由 Java 虚拟机在运行时从字符串常量池和永久代（permanent generation）中创建和管理的，而不是在堆中分配内存空间。

因此，虽然大多数情况下 Java 中使用 new 关键字创建的对象都是在堆中分配内存空间的，但是也有一些例外需要注意。