当前位置：首页 > ai >正文

1. 【面试题】- 盒马鲜生（上）

ai 2025/7/18 17:58:12

1. 说说HashMap的底层实现原理

1.1. 解释

不同JDK版本中，HashMap底层实现是不一样的：在JDK1.7中，HashMap的底层是数组+链表；在JDK1.8中，HashMap的底层是数组+链表/红黑树。在数组长度大于等于64并且链表长度大于等于8时，会将链表转化为红黑树；当红黑树的元素数量小于等于6时，会将红黑树转化为链表。链表之所以要转化为红黑树，是因为当链表长度比较长时，查询的时间复杂度为O(n)，而红黑树的查询速度为O(logn)，查询速率要比链表高很多，所以数据量大时可以显著提升查询效率；红黑树之所以要转化为链表，是因为红黑树的查询效率虽然很快，但是其增删改时要维护的内容过多，所以数据量小时还是链表比较合适。并且，这里有一个值得注意的点就是链表长度大于8等于8时转为红黑树，而红黑树的元素小于等于6才转为链表，这是为了避免元素个数在7附近时频繁的树化/退化。

1.2. 扩展

1.2.1. hash源码

// JDK21源码
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

正常情况下，我们想要获取一个元素在数组中的位置，肯定是通过哈希出来的结果取余数组长度。但是在计算机中，取余和位运算相比，肯定是位运算的效率较高。并且通过一系列精密计算，发现取余的结果和位运算的结果相同（主要归功于数组长度设置为2的N次方），因此HashMap将hash方法修改为了位运算。

从JDK1.8开始，HashMap中的hash算法就发生了改变。对于这个hash算法来说，最大的好处就是resize方法中数据迁移时，不需要对链表中的数组进行hash，只需要执行 (n-1) & hash 从而获取到数据迁移时是在原始的位置不变还是迁移到旧数组长度 + 旧索引的位置。

在HashMap中，hash方法的作用就是用来做优化的。hash方法让数据的存放位置有了更大的随机性，让数据元素更加随机的分布，减少碰撞。如果直接使用key对应的hashcode方法来查找存放位置，那么可能由于hashcode方法很垃圾，导致哈希碰撞很频繁，从而出现较大的效率问题。

1.2.2. resize源码

    // JDK21源码final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

1.2.2.1. 准备扩容参数

Node<K,V>[] oldTab = table; // 将当前桶数组赋值给oldTabint oldCap = (oldTab == null) ? 0 : oldTab.length; // 将当前桶数组长度赋值给oldCapint oldThr = threshold; // 将当前阈值大小赋值给oldThr int newCap, newThr = 0; // 创建新数组长度和新阈值，并且赋值为0

1.2.2.2. 计算新数组长度和新阈值

        if (oldCap > 0) {// 旧数组的长度大于0，表示已经初始化过了if (oldCap >= MAXIMUM_CAPACITY) {// 旧数组的长度大于最大容量，表示超标了，不做任何处理threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// 新数组的长度小于最大容量 && 旧数组的长度大于等于初始化容量// 新阈值 = 旧阈值 * 2newThr = oldThr << 1;}else if (oldThr > 0)// 未被初始化 && 指定了初始容量// 新数组长度 = 旧阈值 * 2（用阈值暂存的设计，构造器传递的容量）newCap = oldThr;else {// 未被初始化 && 没有指定初始化容量// 使用默认初始化数据newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {// 处理未计算newThr的场景（CASE2和CASE1中oldCap<16的情况）float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 更新全局阈值threshold = newThr;

1.2.2.3. 创建新数组并且迁移数据

        // 创建新数组@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 更新全局数组table = newTab;if (oldTab != null) {// 遍历整个旧数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 当且仅当数组j位置不为null时进行操作if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)// 数组j位置有且仅有一个元素newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 数组j位置是一个红黑树结构((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else {// 数组j位置是一个链表结构，开始遍历                    Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {// (e.hash & oldCap)的结果为0，元素位置不变if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {// (e.hash & oldCap)的结果不为0，元素位置 = 当前位置 + 旧数组长度if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}

1.2.2.4. 总结

1. 准备扩容参数
2. 计算新容量和阈值2.1. 已经初始化过的HashMap2.1.1 容量超过上限，不作处理2.1.2. 常规扩容，容量翻倍2.2. 无初始化的HashMap，但是指定了初始容量2.3. 无初始化的HashMap，并且没有指定初始容量
3. 创建新数组并且迁移数据3.1. 数组内容为空，直接跳过3.2. 数组内容不为空，并且只有一个元素3.3. 数组内容不为空，并且为树节点3.4. 数组内容不为空，并且存在链表3.4.1. hash结果为0，数组内容位置不变3.4.2 hash结果不为0，数组内容位置 = 当前位置 + 旧数组长度

1.2.3. put源码

    // JDK21源码final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

1.2.3.1. 初始化数组

        /*如果全局数组为null || 全局数组的长度为0，调用resize扩容。也就是初始化数组（延迟初始化）*/if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;

1.2.3.2. 插入元素

        if ((p = tab[i = (n - 1) & hash]) == null)// 如果数组要存放数据的位置为null，直接插入新值tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))// 如果数组要存放数据的位置有值并且插入元素的key和其相同，那么直接替换e = p;else if (p instanceof TreeNode)// 如果数组要存放数据的位置存在一个树节点，那么调用树的存储方式e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 如果数组要存放数据的位置有元素，并且是链表，那么遍历操作for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {// 如果找到尾节点，那么插入尾部                        p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1)// 如果链表的长度大于等于8，调用树化方法，其中会判断数组长度是否大于等于64treeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 如果存在相同的节点，直接breakbreak;p = e;}}if (e != null) {// 处理已存在的key，解决链表过程中碰到的相同节点的情况             V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}

1.2.3.3. 判断是否需要扩容

        ++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;

1.2.3.4. 总结

1. 初始化数组（延迟初始化）
2. 插入元素2.1. 数组位置无元素，直接创建新节点插入2.2. 数组位置有元素，并且头节点就是要存的位置2.3. 数组位置有元素，并且头节点是树节点2.4. 数组位置有元素，并且是链表2.4.1. 找到尾节点，当链表长度大于等于8并且数组长度大于等于64时树化2.4.2. 如果有key相同的节点，直接替换
3. 判断是否需要扩容

2. 为什么要使用红黑树解决哈希冲突

1. 查询效率高：红黑树查询的时间复杂度是O(logn)，而链表查询的时间复杂度是O(n)，因此红黑树的效率更高；相比于普通的二叉搜索树来说，可能由于插入顺序导致退化为链表，从而致使操作的时间复杂度退化成O(n)，而红黑树可以避免这种情况，所以最差的情况下时间复杂度也是O(n)，查询效率更高。

2. 维护成本相对较低：红黑树相比于AVL完全平衡树来说，它的维护成本更低。AVL树要求每次插入或者删除操作后，左右子树的高度差绝对值不超过1，所以为了维护这个规则需要通过左旋和右旋来保证，维护成本相对较高。

3. ArrayList和LinkedList有什么区别？

1. 底层的数据结构不同：ArrayList底层的数据结构是数组；LinkedList底层的数据结构是链表。

2. 插入和删除的效率不同：ArrayList插入和删除的性能较低，因为需要对元素进行移动；LinkedList插入和删除的性能略高，只需要修改相邻元素的指针即可。

3. 随机访问效率不同：ArrayList可以通过索引获取元素位置，时间复杂度为O(1)；LinkedList需要遍历获取元素，时间复杂度为O(n)。

4. 内存要求和占用空间大小不同：ArrayList在内存中需要连续的存储空间，因此在存储大量数据时，需要大块的连续内存空间，对内存要求较高；LinkedList不要求有连续的内存空间，但是需要额外的空间来存储指针，所以会占用较多的空间。

4. 说说ConcurrentHashMap中CAS和synchronized各自使用场景

4.1. 解释

4.1.1. CAS使用场景

1. 数组初始化：在ConcurrentHashMap中，可能会有多个线程同时来初始化数组。为了避免重复初始化，JDK使用了CAS来确保只有一个线程能成功初始化数组。

2. 无锁并发更新：当没有哈希冲突时，ConcurrentHashMap会优先使用CAS操作来尝试更新节点。

4.1.2. synchronized使用场景

1. 哈希冲突时，ConcurrentHashMap会在put操作时对某一头节点进行加锁。

2. 数据迁移或者红黑树结构调整时，会对头节点进行加锁，从而保证数据一致性。

5. 说说线程池的执行流程

5.1. 解释

1. 任务通过submit或者execute方法提交给线程池，此时如果工作线程数小于核心线程数，那么就会创建线程来执行任务；

2. 当工作线程数大于等于核心线程池数，就会将创建好的任务提交到队列中；

3. 当队列满了之后，如果工作线程小于最大线程，就会创建非核心线程来执行任务；

4. 工作线程等于核心线程之后，就会执行拒绝策略。

5.2. 扩展

5.2.1 execute方法源码

public void execute(Runnable command) {// 如果command == null，即Runnable为空，那么抛出异常if (command == null)throw new NullPointerException();// 获取ctl的值，其中控制着runState(运行状态)和workCount(工作线程数)两个值int c = ctl.get();// 如果工作线程数小于核心线程数，那么创建线程来执行任务if (workerCountOf(c) < corePoolSize) {/*** addWorker(firstTask, core)* firstTask：要进行执行的任务* core：true表示添加核心线程，false表示添加非核心线程* return：true表示添加成功，false表示添加失败*/ if (addWorker(command, true))// 线程创建成功，交给新创建的线程来执行任务，直接返回return;// 线程创建失败，再次获取ctl变量的值c = ctl.get();}// 代码执行到这里，首先说明工作线程数是大于等于核心线程数的// 判断线程池状态是否为运行状态并且任务添加到队列是否添加成功if (isRunning(c) && workQueue.offer(command)) {// 重新获取ctl值int recheck = ctl.get();// 再次判断线程池是否为运行状态// 如果不是运行状态，那么就移除刚才添加到队列中的任务if (! isRunning(recheck) && remove(command))// 线程池不是运行状态并且移除任务成功，那么使用拒绝策略对该任务进行处理reject(command);// 代码执行到这里，表示线程池处于运行状态// 此时判断工作线程是否为0else if (workerCountOf(recheck) == 0)// 如果为0，那么就执行addWorker方法/*** 第一个参数是null，表示在线程池中创建一个线程，但不启动* 第二个参数是false，表示创建的是非核心线程*/addWorker(null, false);}// 执行到这里，有两种可能的情况：// 1. 线程池已经不是RUNNING状态// 2. 线程池是RUNNING状态，但是队列已经满了// 此时再次调用addWorker方法，第二个参数为false，表示创建非核心线程，如果创建失败就执行拒绝策略else if (!addWorker(command, false))reject(command);}

5.2.2 Executor框架

在Executor系列的内容中，比较重要的就是ThreadPoolExecutor和ScheduledThreadPoolExecutor两个实现类，前者是用于执行异步任务，后者是用于执行延迟任务或者定时任务

6. 谈谈你对Redis的理解？它使用的场景有哪些？

Redis是一个开源的、基于内存的key-value数据存储系统。它支持多种数据结构，包括String、Hash、Set、Zset以及List等等。由于它是一个内存型数据库，因此具有非常高的读写性能，从而经常作为Java服务和MySQL之间的中间件来使用。并且，Redis还提供了一些持久化机制，例如AOF和RDB，这样可以在一定程度上保证数据的安全性和持久性。

1. 缓存：由于Redis是基于内存存储，因此经常将MySQL的一些数据存储在Redis中，减少MySQL压力的同时提升程序的效率。

2. 分布式锁：Redis经常作为一个分布式锁来使用，例如常见的Redission框架就是基于Redis服务开发的。

3. 排行榜：Redis中zSet数据结构天然有序，因此可以将其作为一个排行榜来使用。

4. 存储位置信息：Redis提供了GEO数据结构，可以简单快速的存储和读取一些位置信息，并且可以简单的计算一些距离等。

5. 签到功能：Redis提供了BitMap数据结构，可以使用较少的空间来完成签到功能。

6. 简单消息队列：Redis提供了Stream数据结构，可以用于简单的消息队列系统，支持异步处理任务。

7. 计数器：Redis的原子操作incr可以用于实现各种计数器。

8. UV统计功能：Redis提供了HyperLogLog数据结构，可以在较少误差的情况下使用尽量少的数据结构来统计网站访问量。

7. 什么是大Key问题？大Key问题的场景有哪些？如何排查？如何解决？

1. 大key指的是在Redis中存储的数据，其value占用了较大的内存空间，或者包含了大量的数据。大Key并没有一个统一的标准，只要是因为这个key影响了系统的性能，他就是一个大key。

2. 大key出现的常见场景有：Redis中缓存了文件数据、排行榜或者关注列表等存储了全部用户等等。

3. 大key的排查手段有：使用Redis提供的redis-cli --bigkeys命令来查看每个数据结构的Top1；使用Java程序写一个扫描来查看有无大key；使用一些第三方工具来分析Redis的内存使用情况。

4. 大key的解决手段有：使用压缩算法压缩value值；将大key拆分成多个小key进行存储；加强监控和管理，实时监控dakey的出现和内存使用情况。

8. 说说Redis主从复制的原理

8.1. 解释

1. 从节点中执行了slaveof IP PORT命令之后，从节点会先保存主机点的IP地址和端口号。

2. 从节点和主节点之间建立连接，也就是主从之间发起TCP三次握手。

3. 从节点向主节点发送ping命令，观察主节点是否能够正常工作。

4. 如果主节点存在密码，那么从节点就会携带密码去进行权限验证，从而真正的连接上主节点。

5. 主从连接建立好之后，就会进行数据同步，这里可能是全量复制，也可能是部分复制。

6. 主从之间建立长连接，主节点持续向从节点同步命令。

8.2. 扩展

在上述主从复制的流程中，比较重要的就是三种数据同步方式了。下面对这三种方式做一个简单的介绍。

8.2.1 运行流程

数据同步的命令是：psync replicationId offset。这个命令并不需要程序猿主动去执行，而是主从节点建立好连接之后，从节点主动执行命令从而去复制数据。

在主从复制中，replicationId和offset是比较重要的两个参数。replicationId是主从复制中主节点的唯一标识，主从关系建立之后，从节点主动向主节点获取该信息。数据同步命令中，携带上该唯一标识，主节点就可以判断是否是自己的从节点，从而判断是否要进行复制数据。offset是偏移量，主节点接收到命令之后，都会占用几个字节，主节点就会记录下来，作为自己的偏移量。从节点中的偏移量则是用来标识同步主节点数据的位置。当主从偏移量一致时，表示同步完成。
同步时，使用replicationId + offset的原因就是两者可以描述一个数据集合。当两者完全相同时，表示两个节点的数据完全相同。

发送命令时，如果从节点不知道replicationId和offset，那么默认发送?和-1。获取数据时，可以获取全部数据，也可以获取部分数据，这和offset有一定的关系。当值为-1时，就表示获取全部的数据；当值为其他时，就表示获取部分数据。不过不单单仅仅是看这一个指标，同时还考虑主节点的情况。两者结合判断是部分复制还是全量复制。

+FULLRESYNC：表示从节点需要进行全量复制。
+CONTINUE：表示从节点需要部分复制。
-ERR：表示Redis版本过低，不支持psync命令。从节点可以使用sync来进行全量复制，不过需要手动调用，并且还会影响其他请求的执行。

8.2.2 全量复制

1. 从节点向主节点发送psync命令，由于是第一次进行复制，因此replicationId和offset为?和-1。

2. 主节点接收到命令之后，发现需要进行全量复制，就会给从节点发送replicationId和offset。

3. 从节点保存主节点发送过来的replicationId和offset信息。

4. 主节点调用bgsave命令，生成RDB文件。

5. 主节点向从节点发送生成的RDB文件，从节点保存主节点发送的RDB文件。

6. 主节点在生成RDB文件的同时，还会搞一个缓存区，把生成RDB文件过程中的命令进行记录，当RDB文件生成之后，就会把缓冲区的内容也写到RDB文件中，发送给从节点，保证主从数据的一致性。

7. 从节点清除自身的数据，加载RDB文件，获取主节点的全部数据。

8. 从节点保存完毕之后，如果自身开启了AOF功能，那么就会执行重写操作，得到最新的AOF文件。

在上述过程中发现，主节点会生成RDB文件，发送给从节点，从节点保存之后再进行加载。这个过程有点冗余了，我们直接可以让主节点发送给从节点命令，而不是传输文件。这个称作为无硬盘模式。

8.2.3 部分复制

部分复制是针对全量复制的一种优化，依旧是使用psync命令来进行复制。当主从节点之间由于网络抖动等原因导致连接断开时，从节点就会发送psync命令。主节点会判断是否能够进行部分复制。如果可以的话，那么就会返回+CONTINUE命令进行部分复制。

主从之间能否进行部分复制主要取决于从节点发送的replicationId和offset，以及主节点的缓冲积压区。在缓冲积压区中，主要存在四个参数，分别是是否开启缓冲积压区、缓冲积压区的大小、缓冲积压区的开始偏移量、已经存在的数据长度。这本质上是一个环形队列，当队列长度满了之后，起始偏移量就会发生变化。如果数据缺失太多，那么就就无法开启部分复制。

1. 当主节点和从节点之间出现网络故障时，如果超过rept-timeout，那么主节点就会认为从节点故障并且断开连接。

2. 主从断开连接之后，主节点依旧会接收数据，但是从节点此时无法感知到数据的变化，因此主节点就会开启积压缓冲区，把这段时间内的命令复制到积压缓冲区中。

3. 主从再次建立连接之后，从节点就会发送psync命令，主节点判断是否能够开启部分复制。如果可以，那么就会给从节点发送+CONTINUE命令。

4. 主节点逐步将数据同步给从节点，从而达到数据的最终一致性。