阿里二面凉了，难蹦。。。

Posted on by hackdl

分享一位同学阿里巴巴的后端面经，共有 2 面，第一面很顺利过了，可惜挂在第二面。

这两面的知识点范围，我帮大家罗列一下：

  • 网络：TCP、HTTP

  • mysql：索引应用、索引结构、隔离级别、最左匹配

  • redis：zset、缓存一致性

  • java：HashMap、ConcurrntHashMap、ArrayList

  • 数据结构：b树、b+树、红黑树

  • 排序算法：快排、冒泡排序

  • 手撕算法：最长公共前缀 、无重复最长字串

虽然都是比较基础的知识，但是会问很细，没深入学习的话，很容易扛不住。

一面八股

ZSet用过吗 用过 zset 实现排行榜的功能。以博文点赞排名为例，小林发表了五篇博文，分别获得赞为 200、40、100、50、150。

#arcticle:1文章获得了200个赞
>ZADDuser:xiaolin:ranking200arcticle:1
(integer)1
#arcticle:2文章获得了40个赞
>ZADDuser:xiaolin:ranking40arcticle:2
(integer)1
#arcticle:3文章获得了100个赞
>ZADDuser:xiaolin:ranking100arcticle:3
(integer)1
#arcticle:4文章获得了50个赞
>ZADDuser:xiaolin:ranking50arcticle:4
(integer)1
#arcticle:5文章获得了150个赞
>ZADDuser:xiaolin:ranking150arcticle:5
(integer)1

文章 arcticle:4 新增一个赞，可以使用 ZINCRBY 命令（为有序集合key中元素member的分值加上increment）：

>ZINCRBYuser:xiaolin:ranking1arcticle:4
"51"

查看某篇文章的赞数，可以使用 ZSCORE 命令（返回有序集合key中元素个数）：

>ZSCOREuser:xiaolin:rankingarcticle:4
"50"

获取小林文章赞数最多的 3 篇文章，可以使用 ZREVRANGE 命令（倒序获取有序集合 key 从start下标到stop下标的元素）：

#WITHSCORES表示把score也显示出来
>ZREVRANGEuser:xiaolin:ranking02WITHSCORES
1)"arcticle:1"
2)"200"
3)"arcticle:5"
4)"150"
5)"arcticle:3"
6)"100"

获取小林 100 赞到 200 赞的文章，可以使用 ZRANGEBYSCORE 命令（返回有序集合中指定分数区间内的成员，分数由低到高排序）：

>ZRANGEBYSCOREuser:xiaolin:ranking100200WITHSCORES
1)"arcticle:3"
2)"100"
3)"arcticle:5"
4)"150"
5)"arcticle:1"
6)"200"

Zset 类型的底层数据结构是由压缩列表或跳表实现的：

  • 如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构；

  • 如果有序集合的元素不满足上面的条件，Redis 会使用跳表作为 Zset 类型的底层数据结构；

在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。

ConcurrntHashMap和HashMap的底层数据结构

  • HashMap：底层数据结构是数组+链表/红黑树。HashMap使用数组存储元素，每个数组元素对应一个桶（bucket），每个桶可以存放多个键值对。当发生哈希冲突时，采用链表或者红黑树来解决冲突，JDK 8之后，链表长度过长时会将链表转换为红黑树，以提高查找效率。

  • ConcurrentHashMap：底层数据结构是分段锁（Segment数组）+数组+链表/红黑树。ConcurrentHashMap将整个数据结构分成多个Segment（段），每个Segment相当于一个小的HashMap，拥有自己的锁。这样服务器托管在进行写操作时，只需要锁住对应的Segment，而其他Segment仍然可以并发读写，提高了并发性能。从JDK 8开始，ConcurrentHashMap的实现已经不再使用Segment，而是采用了更加高效的方式来实现并发操作。

ConcurrntHashMap怎么实现线程安全的

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。

Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。

JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap

在 JDK 1.7 中，ConcurrentHashMap 虽然是线程安全的，但因为它的底层实现是数组 + 链表的形式，所以在数据比较多的情况下访问是很慢的，因为要遍历整个链表，而 JDK 1.8 则使用了数组 + 链表/红黑树的方式优化了 ConcurrentHashMap 的实现，具体实现结构如下：

JDK 1.8 ConcurrentHashMap JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

  • 如果为空则使用 volatile 加 CAS 来初始化

  • 如果容器不为空，则根据存储的元素计算该位置是否为空。

    • 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；

    • 如果根据存储的元素计算结果不为空，则使用 synchronized ，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。

三次握手说一下

TCP 三次握手过程

  • 一开始，客户端和服务端都处于 CLOSE 状态。先是服务端主动监听某个端口，处于 LISTEN 状态

  • 客户端会随机初始化序号（client_isn），将此序号置于 TCP 首部的「序号」字段中，同时把 SYN 标志位置为 1，表示 SYN 报文。接着把第一个 SYN 报文发送给服务端，表示向服务端发起连接，该报文不包含应用层数据，之后客户端处于 SYN-SENT 状态。

  • 服务端收到客户端的 SYN 报文后，首先服务端也随机初始化自己的序号（server_isn），将此序号填入 TCP 首部的「序号」字段中，其次把 TCP 首部的「确认应答号」字段填入 client_isn + 1, 接着把 SYN 和 ACK 标志位置为 1。最后把该报文发给客户端，该报文也不包含应用层数据，之后服务端处于 SYN-RCVD 状态。

  • 客户端收到服务端报文后，还要向服务端回应最后一个应答报文，首先该应答报文 TCP 首部 ACK 标志位置为 1 ，其次「确认应答号」字段填入 server_isn + 1 ，最后把报文发送给服务端，这次报文可以携带客户到服务端的数据，之后客户端处于 ESTABLISHED 状态。

  • 服务端收到客户端的应答报文后，也进入 ESTABLISHED 状态。

四次挥手说一下

TCP 四次挥手过程

具体过程：

  • 客户端主动调用关闭连接的函数，于是就会发送 FIN 报文，这个 FIN 报文代表客户端不会再发送数据了，进入 FIN_WAIT_1 状态；

  • 服务端收到了 FIN 报文，然后马上回复一个 ACK 确认报文，此时服务端进入 CLOSE_WAIT 状态。在收到 FIN 报文的时候，TCP 协议栈会为 FIN 包插入一个文件结束符 EOF 到接收缓冲区中，服务端应用程序可以通过 read 调用来感知这个 FIN 包，这个 EOF 会被放在已排队等候的其他已接收的数据之后，所以必须要得继续 read 接收缓冲区已接收的数据；

  • 接着，当服务端在 read 数据的时候，最后自然就会读到 EOF，接着read() 就会返回 0，这时服务端应用程序如果有数据要发送的话，就发完数据后才调用关闭连接的函数，如果服务端应用程序没有数据要发送的话，可以直接调用关闭连接的函数，这时服务端就会发一个 FIN 包，这个 FIN 报文代表服务端不会再发送数据了，之后处于 LAST_ACK 状态；

  • 客户端接收到服务端的 FIN 包，并发送 ACK 确认包给服务端，此时客户端将进入 TIME_WAIT 状态；

  • 服务端收到 ACK 确认包后，就进入了最后的 CLOSE 状态；

  • 客户端经过 2MSL 时间之后，也进入 CLOSE 状态；

为什么四次挥手之后要等2MSL?

MSL 是 Maximum Segment Lifetime，报文最大生存时间，它是任何报文在网络上存在的最长时间，超过这个时间报文将被丢弃。因为 TCP 报文基于是 IP 协议的，而 IP 头中有一个 TTL 字段，是 IP 数据报可以经过的最大路由数，每经过一个处理他的路由器此值就减 1，当此值为 0 则数据报将被丢弃，同时发送 ICMP 报文通知源主机。

MSL 与 TTL 的区别：MSL 的单位是时间，而 TTL 是经过路由跳数。所以MSL 应该要大于等于 TTL 消耗为 0 的时间，以确保报文已被自然消亡。

TTL 的值一般是 64，Linux 将 MSL 设置为 30 秒，意味着 Linux 认为数据报文经过 64 个路由器的时间不会超过 30 秒，如果超过了，就认为报文已经消失在网络中了。

TIME_WAIT 等待 2 倍的 MSL，比较合理的解释是：网络中可能存在来自发送方的数据包，当这些发送方的数据包被接收方处理后又会向对方发送响应，所以一来一回需要等待 2 倍的时间。

比如，如果被动关闭方没有收到断开连接的最后的 ACK 报文，就会触发超时重发 FIN 报文，另一方接收到 FIN 后，会重发 ACK 给被动关闭方， 一来一去正好 2 个 MSL。

可以看到2MSL时长这其实是相当于至少允许报文丢失一次。比如，若 ACK 在一个 MSL 内丢失，这样被动方重发的 FIN 会在第 2 个 MSL 内到达，TIME_WAIT 状态的连接可以应对。

HTTP进行TCP连接之后，在什么情况下会中断

  • 当服务端或者客户端执行 close 系统调用的时候，会发送FIN报文，就会进行四次挥手的过程

  • 当发送方发送了数据之后，接收方超过一段时间没有响应ACK报文，发送方重传数据达到最大次数的时候，就会断开TCP连接

  • 当HTTP长时间没有进行请求和响应的时候，超过一定的时间，就会释放连接

HTTP、SOCKET和TCP的区别

HTTP是应用层协议，定义了客户端和服务器之间交换的数据格式和规则；Socket是通信的一端，提供了网络通信的接口；TCP是传输层协议，负责在网络中建立可靠的数据传输连接。它们在网络通信中扮演不同的角色和层次。

  • HTTP是一种用于传输超文本数据的应用层协议，用于在客户端和服务器之间传输和显示Web页面。

  • Socket是计算机网络中的一种抽象，用于描述通信链路的一端，提供了底层的通信接口，可实现不同计算机之间的数据交换。

  • TCP是一种面向连接的、可靠的传输层协议，负责在通信的两端之间建立可靠的数据传输连接。

说说MySQL索引

可以按照四个角度来分类索引。

  • 按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。

  • 按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。

  • 按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。

  • 按「字段个数」分类：单列索引、联合索引。

    聚簇索引数据结构

聚簇索引数据结构是B+树，B+Tree 是一种多叉树，叶子节点才存放数据，非叶子节点只存放索引，而且每个节点里的数据是按主键顺序存放的。每一层父节点的索引值都会出现在下层子节点的索引值中，因此在叶子节点中，包括了所有的索引值信息，并且每一个叶子节点都有两个指针，分别指向下一个叶子节点和上一个叶子节点，形成一个双向链表。

聚簇索引的 B+Tree 如图所示：

对于聚簇索引，它的数据存放在哪

数据存储到叶子节点，非叶子节点只有索引。

你使用索引有什么经验吗？

索引最大的好处是提高查询速度，但是索引也是有缺点的，比如：

  • 需要占用物理空间，数量越大，占用空间越大；

  • 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增大；

  • 会降低表的增删改的效率，因为每次增删改索引，B+ 树为了维护索引有序性，都需要进行动态维护。

所以，索引不是万能钥匙，它也是根据场景来使用的。

什么时候适用索引？

  • 字段有唯一性限制的，比如商品编码；

  • 经常用于 WHERE 查询条件的字段，这样能够提高整个表的查询速度，如果查询条件不是一个字段，可以建立联合索引。

  • 经常用于 GROUP BY 和 ORDER BY 的字段，这样在查询的时候就不需要再去做一次排序了，因为我们都已经知道了建立索引之后在 B+Tree 中的记录都是排序好的。

什么时候不需要创建索引？

  • WHERE 条件，GROUP BY，ORDER BY 里用不到的字段，索引的价值是快速定位，如果起不到定位的字段通常是不需要创建索引的，因为索引是会占用物理空间的。

  • 字段中存在大量重复数据，不需要创建索引，比如性别字段，只有男女，如果数据库表中，男女的记录分布均匀，那么无论搜索哪个值都可能得到一半的数据。在这些情况下，还不如不要索引，因为 MySQL 还有一个查询优化器，查询优化器发现某个值出现在表的数据行中的百分比很高的时候，它一般会忽略索引，进行全表扫描。

  • 表数据太少的时候，不需要创建索引；

  • 经常更新的字段不用创建索引，比如不要对电商项目的用户余额建立索引，因为索引字段频繁修改，由于要维护 B+Tree的有序性，那么就需要频繁的重建索引，这个过程是会影响数据库性能的。

说说最左匹配原则，给你一个联合索引（a,b,c） a, ab , abc , bc , ac走索引吗

使用联合索引时，存在最左匹配原则，也就是按照最左优先的方式进行索引的匹配。在使用联合索引进行查询的时候，如果不遵循「最左匹配原则」，联合索引会失效，这样就无法利用到索引快速查询的特性了。

(a, b, c) 联合索引，是先按 a 排序，在 a 相同的情况再按 b 排序，在 b 相同的情况再按 c 排序。所以，b 和 c 是全局无序，局部相对有序的，这样在没有遵循最左匹配原则的情况下，是无法利用到索引的。

  • where a=?，符合最左匹配原则，能走索引。

  • where a = ? and b = ?，符合最左匹配原则，能走索引。

  • where a = ? and b = ? and c = ?， 符合最左匹配原则，能走索引。

  • where b = ? and c = ? ，不符合最左匹配原则，不能走索引。

  • whe服务器托管re a = ? and c = ? ，能走走索引，但是只有 a 字段能走索引，c 字段无法走索引，不过 c 字段可以利用索引下推。

数据库和缓存的一致性如何保证

对于读数据，我会选择旁路缓存策略，如果 cache 不命中，会从 db 加载数据到 cache。

对于写数据，我会选择更新 db 后，再删除缓存。

针对删除缓存异常的情况，我还会对 key 设置过期时间兜底，只要过期时间一到，过期的 key 就会被删除了。

除此之外，还有两种方式应对删除缓存失败的情况。

消息队列方案

我们可以引入消息队列，将第二个操作（删除缓存）要操作的数据加入到消息队列，由消费者来操作数据。

  • 如果应用删除缓存失败，可以从消息队列中重新读取数据，然后再次删除缓存，这个就是重试机制。当然，如果重试超过的一定次数，还是没有成功，我们就需要向业务层发送报错信息了。

  • 如果删除缓存成功，就要把数据从消息队列中移除，避免重复操作，否则就继续重试。

举个例子，来说明重试机制的过程。

订阅 MySQL binlog，再操作缓存

「先更新数据库，再删缓存」的策略的第一步是更新数据库，那么更新数据库成功，就会产生一条变更日志，记录在 binlog 里。

于是我们就可以通过订阅 binlog 日志，拿到具体要操作的数据，然后再执行缓存删除，阿里巴巴开源的 Canal 中间件就是基于这个实现的。

Canal 模拟 MySQL 主从复制的交互协议，把自己伪装成一个 MySQL 的从节点，向 MySQL 主节点发送 dump 请求，MySQL 收到请求后，就会开始推送 Binlog 给 Canal，Canal 解析 Binlog 字节流之后，转换为便于读取的结构化数据，供下游程序订阅使用。

下图是 Canal 的工作原理：

所以，如果要想保证「先更新数据库，再删缓存」策略第二个操作能执行成功，我们可以使用「消息队列来重试缓存的删除」，或者「订阅 MySQL binlog 再操作缓存」，这两种方法有一个共同的特点，都是采用异步操作缓存。

算法

  • 最长公共前缀

  • 无重复最长字串

二面八股

说说聚簇索引和非聚簇索引的区别？

  • 聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点；

  • 非聚簇索引的叶子节点存放的是主键值，而不是实际数据。

如果某个查询语句使用了二级索引（非聚簇索引），但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作「回表」，也就是说要查两个 B+ 树才能查到数据。

不过，当查询的数据是主键值时，因为只在二级索引（非聚簇索引）就能查询到，不用再去聚簇索引查，这个过程就叫作「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据。

说说B+树和B树的区别

  • 在B+树中，数据都存储在叶子节点上，而非叶子节点只存储索引信息；而B树的非叶子节点既存储索引信息也存储部分数据。

  • B+树的叶子节点使用链表相连，便于范围查询和顺序访问；B树的叶子节点没有链表连接。

  • B+树的查找性能更稳定，每次查找都需要查找到叶子节点；而B树的查找可能会在非叶子节点找到数据，性能相对不稳定。

说说B+树非叶子节点分裂流

InnoDB 创建主键索引默认为聚簇索引，数据被存放在了 B+Tree 的叶子节点上。也就是说，同一个叶子节点内的各个数据是按主键顺序存放的，因此，每当有一条新的数据插入时，数据库会根据主键将其插入到对应的叶子节点中。

如果我们使用自增主键，那么每次插入的新数据就会按顺序添加到当前索引节点的位置，不需要移动已有的数据，当页面写满，就会自动开辟一个新页面。因为每次插入一条新记录，都是追加操作，不需要重新移动数据，因此这种插入数据的方法效率非常高。

如果我们使用非自增主键，由于每次插入主键的索引值都是随机的，因此每次插入新的数据时，就可能会插入到现有数据页中间的某个位置，这将不得不移动其它数据来满足新数据的插入，甚至需要从一个页面复制数据到另外一个页面，我们通常将这种情况称为页分裂。页分裂还有可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率。

举个例子，假设某个数据页中的数据是1、3、5、9，且数据页满了，现在准备插入一个数据7，则需要把数据页分割为两个数据页：

出现页分裂时，需要将一个页的记录移动到另外一个页，性能会受到影响，同时页空间的利用率下降，造成存储空间的浪费。

而如果记录是顺序插入的，例如插入数据11，则只需开辟新的数据页，也就不会发生页分裂：

因此，在使用 InnoDB 存储引擎时，如果没有特别的业务需求，建议使用自增字段作为主键。

select * from xxx where a = x b= x order by c 怎么建立索引

可以建立（a，b，c）联合索引，这样三个字段都能利用索引，并且 c 字段还能利用索引的有序性，避免了额外排序。

数据库事务隔离级别

  • 读未提交，指一个事务还没提交时，它做的变更就能被其他事务看到；

  • 读提交，指一个事务提交之后，它做的变更才能被其他事务看到；

  • 可重复读，指一个事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，MySQL InnoDB 引擎的默认隔离级别；

  • 串行化；会对记录加上读写锁，在多个事务对这条记录进行读写操作时，如果发生了读写冲突的时候，后访问的事务必须等前一个事务执行完成，才能继续执行；

按隔离水平高低排序如下：

针对不同的隔离级别，并发事务时可能发生的现象也会不同。

说说幻读

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

假设有 A 和 B 这两个事务同时在处理，事务 A 先开始从数据库查询账户余额大于 100 万的记录，发现共有 5 条，然后事务 B 也按相同的搜索条件也是查询出了 5 条记录。

接下来，事务 A 插入了一条余额超过 100 万的账号，并提交了事务，此时数据库超过 100 万余额的账号个数就变为 6。

然后事务 B 再次查询账户余额大于 100 万的记录，此时查询到的记录数量有 6 条，发现和前一次读到的记录数量不一样了，就感觉发生了幻觉一样，这种现象就被称为幻读。

说说快排流程，时间复杂度

快速排序的流程如下：

  • 从数组中选择一个基准元素（通常是数组中间位置的元素）。

  • 将数组分成两部分，小于基准元素的放在左边，大于基准元素的放在右边。

  • 递归地对左右两部分进行快速排序。

快速排序的时间复杂度为O(n log n)，其中n为数组的长度。最坏情况下时间复杂度为O(n^2)，发生在每次选择的基准元素都是最大或最小值时。平均情况下时间复杂度为O(n log n)，效率较高。

快排为什么时间复杂度最差是O（n^2）

主要是因为在每次划分时选择的基准元素不合适导致的。当每次选择的基准元素都是当前子数组中的最大或最小元素时，就会导致每次划分只能减少一个元素，而不是均匀地分成两部分，从而造成时间复杂度达到O(n^2)。

这种情况通常发生在数组已经有序或基本有序的情况下。为了避免最坏情况发生，可以通过随机选择基准元素或者使用三数取中法等策略来提高快速排序的性能。

快排这么强，那冒泡排序还有必要吗？

冒泡排序在一些特定场景下仍然有其优势，比如：

  • 对于小规模数据或基本有序的数据，冒泡排序可能比快速排序更简单、更直观。

  • 冒泡排序是稳定排序算法，相对于快速排序的不稳定性，在某些情况下可能更适合要求稳定性的场景。

  • 冒泡排序是原地排序算法，不需要额外的空间，适合空间复杂度要求严格的场景。

说说红黑树

红黑树是一种自平衡的二叉查找树，

具有以下特点：

  1. 每个节点要么是红色，要么是黑色。

  2. 根节点是黑色。

  3. 每个叶子节点（NIL节点）是黑色。

  4. 如果一个节点是红色，则其子节点必须是黑色。

  5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

红黑树的自平衡性质可以保证在进行插入、删除等操作后，树的高度保持在O(log n)内，从而保持了较高的查找、插入和删除效率。

下面是红黑树插入节点的过程，这左旋右旋的操作，就是为了自平衡。

说说红黑树怎么左旋右旋

左旋和右旋是两种基本的旋转操作，用于保持红黑树的平衡。下面简单描述一下左旋和右旋的操作步骤：

左旋操作：

  1. 将当前节点的右子节点作为新的根节点。

  2. 将新根节点的左子节点移动为当前节点的右子节点。

  3. 如果当前节点有父节点，将当前节点的父节点更新为新根节点的父节点；否则，将新根节点设置为树的根节点。

  4. 更新新根节点和其子节点的父节点关系。

接下来看下图片展示，首先断开节点PL与右子节点G的关系，同时将其右子节点的引用指向节点C2；然后断开节点G与左子节点C2的关系，同时将G的左子节点的应用指向节点PL。

接下来再放下 gif 图，希望能帮助大家更好地理解左旋

右旋操作与左旋操作对称，具体步骤如下：

  1. 将当前节点的左子节点作为新的根节点。

  2. 将新根节点的右子节点移动为当前节点的左子节点。

  3. 如果当前节点有父节点，将当前节点的父节点更新为新根节点的父节点；否则，将新根节点设置为树的根节点。

  4. 更新新根节点和其子节点的父节点关系。

首先断开节点G与左子节点PL的关系，同时将其左子节点的引用指向节点C2；然后断开节点PL与右子节点C2的关系，同时将PL的右子节点的应用指向节点G。

右旋的gif展示（图片来自网络）:

说说hashmap扩容，说说负载因子

hashmap扩容

HashMap 扩容的目的是为了减少哈希冲突，Java中hashmap扩容过程如下图：

当进行 put 操作导致整个哈希表的负载因子因此到达阈值后，会进入一个阻塞的扩容流程中，先通过复制一个两杯容量的entry数组，然后将原有entry中的元素进行遍历执行rehash，jdk1.8使用的是2次幂的扩展(指长度扩为原来2倍)。

所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。因此在执行rehash的时候只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

负载因子

HashMap 负载因子 loadFactor 的默认值是 0.75，当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。

默认负载因子为 0.75，是因为它提供了空间和时间复杂度之间的良好平衡。

负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

说说扩容之后的退化问题

HashMap在发生扩容时，会重新计算元素的存放位置，可能导致原本分布均匀的元素在新的容量下发生“退化”，即多个元素映射到同一个桶（bucket）上，使得链表长度过长，影响了HashMap的性能。这种情况下，HashMap的查找、插入和删除操作的时间复杂度可能会由原本的O(1)上升到O(n)，严重影响了HashMap的效率。

为了解决HashMap扩容后的退化问题，通常采用以下方法：

  1. 提高负载因子（load factor）：在发生扩容之前，可以提前扩容，使得哈希表中的元素数量与桶的数量的比值在扩容后不会过高，减少退化的可能性。

  2. 使用红黑树：在JDK 8中，当链表长度过长时，会将链表转换为红黑树，以减少查找时间，提高性能。

说说ArrayList的扩容

ArrayList在添加元素时，如果当前元素个数已经达到了内部数组的容量上限，就会触发扩容操作。ArrayList的扩容操作主要包括以下几个步骤：

  • 计算新的容量：一般情况下，新的容量会扩大为原容量的1.5倍（在JDK 10之后，扩容策略做了调整），然后检查是否超过了最大容量限制。

  • 创建新的数组：根据计算得到的新容量，创建一个新的更大的数组。

  • 将元素复制：将原来数组中的元素逐个复制到新数组中。

  • 更新引用：将ArrayList内部指向原数组的引用指向新数组。

  • 完成扩容：扩容完成后，可以继续添加新元素。

ArrayList的扩容操作涉及到数组的复制和内存的重新分配，所以在频繁添加大量元素时，扩容操作可能会影响性能。为了减少扩容带来的性能损耗，可以在初始化ArrayList时预分配足够大的容量，避免频繁触发扩容操作。

为什么ArrayList扩容是1.5倍

1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。

//新容量计算
intnewCapacity=oldCapacity+(oldCapacity>>1);

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: