2023-08-29 11:36 门头沟学院 Java

关注

DW I · Java

一、算法与数据结构

剑指offer30：含有 min 函数的栈。

二、Java 基础

1 HashMap 的底层结构

答：1. Node 数组；2. put 过程；3. 扩容过程

追问：插入过程为什么从链表转换为红黑树？

答：时间复杂度从 O(n)->O(lgn)。红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 O(log(n))。

追问：是怎么从链表转换为红黑树的？

答：当链表长度大于 8 时，就从 Node 转换为 TreeNode。

正解：当链表长度大于或等于阈值（默认为 8）的时候，如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY（默认为 64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。

追问：为什么不一开始就用红黑树？

答：因为红黑树比较复杂。

正解：因为红黑树的节点大小是普通节点的两倍大，在节点数量比较少的情况下，效率可能还要比链表差一点。

如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。

参考 https://blog.51cto.com/u_13294304/3075723

追问：HashMap 线程安全吗？

答：不安全。ConcurrentHashMap 安全。

追问：锁住 HashMap 可以实现线程安全吗？

答：可以的，但是效率会低下。

2 JVM 的运行时数据区

答：共享区域包括堆和方法区（含有运行时常量池），私有区域包括PC、本地方法栈和虚拟机栈。

补充：JVM 的核心如下图

3 变量判活

答：1. 引用计数法（每一个对象都有一个引用计数器，当被引用一次时，它都会 +1，引用取消时 -1，当执行GC时，所有引用计数器为 0 的对象都会被视为“垃圾”。）；2. 可达性分析（以方法区的静态变量或栈帧变量表的变量为Root根节点,通过这个root去找其他下级节点，无法到达的对象在GC中会被清理。）。

4 垃圾回收算法及其优缺点

正解：

标记清除算法

把所有需要回收的对象作一个标记，GC回收的时候会把所有被标记的对象回收。

优点：简单

缺点：垃圾回收后内存会变得不连续，造成很大零散的内存区域。以后新创建的大对象可能会不够空间存储。

复制算法(大多JVM的GC都使用这个)

通俗点说，把原本存放对象的一块大区域拆分为 1个Eden和2个Survivor，创建新对象时仅使用其中一块区域Eden，当Eden满了后触发minorGC，清空Eden和其中一个Survivor1前把幸存的对象复制到Survivor2，然后再清空Eden和Survivor1(仅概念上简述，实际情况很复杂，请看其他文章详细分析)

优点：GC后的内存空间是连续的。

缺点：由于分出了Survivor2不存放对象，真正存放新对象的内存区域会变少，Eden:Survivor1:Survivor2比例为8:1:1，少了10%的可用内存。

标记-整理法

类似与标记清除法一样，第一步先把需要回收的对象标记，不同的是第二步把活动的对象(幸存)往内存一边移动。堆内存就像一列队伍，把所有要留下的对象都往前靠，后面剩下的都是即将回收的对象(垃圾)。

优点：避免了“标记清除法”和“复制算法”的缺点。

缺点：效率比较低。

分代收集法

书中把这个算法和垃圾收集算法放在了一起，但我觉得分代收集与上面的“垃圾收集算法”有一点本质区别。前者是GC的设计方式，后者是GC回收的具体思路。

堆内存被分为新生代和老年代，其中新生代一般分为eden和Survivor(上文简述过)。在新生代的gc成为 minorGC，老年代的称为majorGC/fullGC，新创建的对象属于新生代，在经历了N次minorGC后(N可调大小，默认15)，会转到老年代。

新生代的区域和老年代区域比例一般为1：2。两个区域的垃圾收集算法都可以不同，新生代一般为“复制算法”，老年代为“标记-整理法”。

为什么新生代使用“复制算法”，老年代使用“标记-整理法”？

因为在Java程序中，大部分对象都是“朝生夕死”，很快会被回收的，所以新生代的minorGC的触发频率要远大于老年代的majorGC，这就需要效率更高的“复制算法”，而老年代由于majorGC触发频率比较低，所以可以选择效率较低的“标记整理法”来节约内存。

此外，值得一提的是新生代的eden内存要大于Survivor内存，这样就会出现一个问题：当eden中有一部分对象生命周期一样并且占用的内存大于Survivors时，执行minorGC仍然幸存，Survivor将无法存放这么多的对象。这时老年代就会起到“担保”作用，那些存活的对象将直接晋升到老年代。同理“复制算法”需要有人来做担保，这也是老年代使用“标记整理法”的原因之一。

5 Redis 做缓存时，如何保证与数据库内容的一致性？

见 https://xiaolincoding.com/redis/architecture/mysql_redis_consistency.html#%E6%95%B0%E6%8D%AE%E5%BA%93%E5%92%8C%E7%BC%93%E5%AD%98%E5%A6%82%E4%BD%95%E4%BF%9D%E8%AF%81%E4%B8%80%E8%87%B4%E6%80%A7

无论是「先更新数据库，再更新缓存」，还是「先更新缓存，再更新数据库」，这两个方案都存在并发问题，当两个请求并发更新同一条数据的时候，可能会出现缓存和数据库中的数据不一致的现象。所以我们得增加一些手段来解决这个问题，这里提供两种做法：

在更新缓存前先加个分布式锁，保证同一时间只运行一个请求更新缓存，就会不会产生并发问题了，当然引入了锁后，对于写入的性能就会带来影响。
在更新完缓存时，给缓存加上较短的过期时间，这样即时出现缓存不一致的情况，缓存的数据也会很快过期，对业务还是能接受的。

旁路缓存策略

在更新数据时，不更新缓存，而是删除缓存中的数据。然后，到读取数据时，发现缓存中没了数据之后，再从数据库中读取数据，更新到缓存中。

但是，先删除缓存，再更新数据库，在「读 + 写」并发的时候，还是会出现缓存和数据库的数据不一致的问题。

读+写的情况下，「先更新数据库 + 再删除缓存」+过期时间的方案，是可以保证数据一致性的。

缓存删除失败

在删除缓存（第二个操作）的时候失败了，导致缓存还是旧值，而数据库是最新值，造成数据库和缓存数据不一致的问题，会对敏感业务造成影响。

问题原因知道了，该怎么解决呢？有两种方法：

重试机制。引入消息队列，将第二个操作（删除缓存）要操作的数据加入到消息队列，由消费者来操作数据。
订阅 MySQL binlog，再操作缓存。负责更新缓存的服务，把自己伪装成一个 MySQL 的从节点，从 MySQL 接收 Binlog，解析 Binlog 之后，可以得到实时的数据变更信息，然后根据这个变更信息去更新 Redis 缓存。这种收 Binlog 更新缓存的方案，和刚刚我们讲到的，收 MQ 消息更新缓存的方案，其实它们的实现思路是一样的，都是异步订阅实时数据变更信息，去更新 Redis。只不过，直接读取 Binlog 这种方式，它的通用性更强。不要求订单服务再发订单消息了，订单更新服务也不用费劲去解决「发消息失败怎么办？」这种数据一致性问题了。

这两种方法本质上都是采用异步操作缓存。

6 Redis 除了做缓存还能做什么？

正解：除了作为缓存，Redis（Remote Dictionary Server）还可以用于许多其他用途，它是一个功能丰富的开源内存数据存储系统。以下是一些 Redis 可以用于的常见用途：

数据存储： Redis 可以用作键值存储数据库，将数据存储在内存中，以提供快速的读写访问。它支持多种数据结构，如字符串、哈希、列表、集合、有序集合等，使其适用于不同类型的数据存储需求。
消息队列： Redis 的发布-订阅（Pub/Sub）功能允许多个客户端通过订阅特定的频道来接收消息。这使得 Redis 可以用作简单的消息队列系统，用于异步通信和事件驱动架构。
实时统计和计数器： Redis 的数据结构能够支持高性能的计数和统计操作。例如，可以使用 Redis 的有序集合来存储和排名一些数据，比如用户分数、文章点赞数等。
会话存储：在 Web 应用中，可以使用 Redis 存储会话数据，以支持分布式环境下的会话管理，提供高性能和可扩展性。
缓存击穿保护： Redis 支持设置数据的过期时间，这可以用于防止缓存击穿。在缓存中设置短暂的过期时间，避免在数据库查询未命中时，大量请求直接访问数据库，从而分散数据库压力。
地理空间索引： Redis 的地理空间数据结构可以用于存储和查询地理位置信息，如坐标和位置名称，以支持附近位置的搜索和查找。
分布式锁：使用 Redis 的原子性操作，可以实现分布式锁来协调多个节点之间的资源访问。
缓存预热：在系统启动或高峰期之前，可以使用 Redis 提前加载一些热门数据，以避免在实际请求到来时发生缓存未命中。
数据持久化： Redis 支持将数据持久化到磁盘，以便在重启后恢复数据。它提供了两种持久化方式：快照（snapshotting）和追加文件（append-only file）。
分布式应用的共享数据：在分布式系统中，不同节点之间可以使用 Redis 共享数据，比如配置信息、状态信息等。

总之，Redis 是一个多用途的数据存储系统，通过其灵活的数据结构和高性能的特性，可以满足许多不同类型的数据处理需求。

作者：JoseKnife链接：https://www.nowcoder.com/discuss/525087413178204160?sourceSSR=users

7 Redis 为什么高效？

答：1. 底层数据结构；2. 单线程。

正解：之所以 Redis 采用单线程（网络 I/O 和执行命令）那么快，有如下几个原因：

Redis 的大部分操作都在内存中完成，并且采用了高效的数据结构，因此 Redis 瓶颈可能是机器的内存或者网络带宽，而并非 CPU，既然 CPU 不是瓶颈，那么自然就采用单线程的解决方案了；
Redis 采用单线程模型可以避免了多线程之间的竞争，省去了多线程切换带来的时间和性能上的开销，而且也不会导致死锁问题。
Redis 采用了 I/O 多路复用机制处理大量的客户端 Socket 请求，IO 多路复用机制是指一个线程处理多个 IO 流，就是我们经常听到的 select/epoll 机制。简单来说，在 Redis 只运行单线程的情况下，该机制允许内核中，同时存在多个监听 Socket 和已连接 Socket。内核会一直监听这些 Socket 上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个 IO 流的效果。