拼多多线下面试(后端开发):手写 HashMap 与 SQL left join
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
手撕部分
- 实现一个 HashMap,支持多种数据类型,有较高效的读取、放入数据实现。
- n 个节点的二叉树最多有几种形状?
- 反转链表。
- 反转链表中的一部分。
- 用开放地址法实现一个 HashMap,key 和 value 是 int,不考虑扩容,hash 用 mod 求得,数组大小固定为 5。
- 追问:怎么优化?可以在查找的时候发现为 null 就停止查找吗?
- 追问:在存在 hash 碰撞的时候,开放地址法比拉链表好,效率高 100 倍,为什么?
- 用 Java 实现 SQL 语句 left join,字段类型为 String,class 给出,实现方法即可。
- 追问:目前两个 for 嵌套实现的时间复杂度?除了两个 for 嵌套有没有可以优化的?
- 追问:右边放 map 的话,key 和 value 分别是什么?有没有最好和最坏的情况,时间复杂度是多少?
- 追问:字段类型为很大的 file 的话,怎么做(大数据)?
实习项目与相关内容追问
- 发送命令、下游执行、框架等待响应并返回,这个过程的协议栈是什么?从应用层到传输层怎么分工?gRPC 底层基于什么传输?
- 从用户态和内核态的角度说一下整个过程:Java 代码发送命令时数据怎么在操作系统底层流转?什么是系统调用?执行池线程阻塞等待时 CPU 为什么不会爆掉?
- MCP 的目的是什么?
《参考解析》
支持多类型的 HashMap:核心是「数组 + 链表/红黑树」这套结构,用泛型 HashMap<K, V> 把类型交给调用方。put 时先对 key.hashCode() 做扰动(JDK 8 是 h ^ (h >>> 16)),再用 (n - 1) & hash 定位桶;桶为空直接放,冲突就沿链表比较 hash 和 equals,相同则覆盖、不同则尾插;链表长度到 8 且数组长度到 64 时转红黑树,查询从 O(n) 降到 O(log n)。扩容在元素数超过「容量 × 负载因子(默认 0.75)」时触发,容量翻倍并重新分布,JDK 8 利用容量是 2 的幂这一点,把节点分成「原位置」和「原位置 + 旧容量」两条链,避免逐个重算 hash。工程上还要处理 key == null(固定放 0 号桶)、hashCode 与 equals 的契约、以及并发场景改用 ConcurrentHashMap——后者 JDK 8 用 CAS 写空桶、synchronized 锁桶头,锁粒度比 1.7 的分段锁细得多。面试里如果要求「高效」,就把平均 O(1)、最坏 O(log n)、扩容摊还这三点讲清楚。
二叉树形状数:n 个节点的二叉树形状数是第 n 个卡特兰数 C_n = C(2n, n) / (n + 1),也满足递推 C_n = Σ_{i=0}^{n-1} C_i · C_{n-1-i}:枚举左子树分到 i 个节点,右子树就是 n-1-i 个。前几项是 1、1、2、5、14、42,n=3 是 5 种。注意这里只算形状、节点不编号;如果节点有标号还要再乘 n!,如果要求是「满二叉树」或「完全二叉树」则不是卡特兰数。写代码用一维 DP,O(n²) 时间、O(n) 空间,大数场景用 long 或 BigInteger 防溢出。
链表反转:整表反转用三指针迭代:prev = null,循环里先存 next = curr.next,再 curr.next = prev,然后 prev = curr、curr = next,最后返回 prev;时间 O(n)、空间 O(1)。递归写法是 reverse(head.next) 之后把 head.next.next = head、head.next = null,空间 O(n) 且长链表有栈溢出风险。反转一部分(LeetCode 92)用哨兵节点简化边界:dummy.next = head,走到第 left-1 个节点记为 prev,从 left 开始做 right-left+1 次头插,把区间内的节点逐个挪到 prev 后面,最后返回 dummy.next。边界要覆盖 left == right、left == 1、right == n,写完手动跑一个两节点和一个三节点的例子。
开放地址法实现:固定 5 个槽,用两个 int[] 分别存 key 和 value,再加一个 boolean[] used 或用一个哨兵值区分空槽。hash(key) = (key % 5 + 5) % 5,负数要先修正;put 从该位置线性探测,遇到空槽写入,遇到相同 key 覆盖,转一圈都满就报满;get 从 hash 位置往后找,命中 key 返回,遇到空槽说明不存在。查找遇到 null 就停,在「只插入、不删除」的前提下是成立的,因为线性探测的探测序列连续,空槽意味着后面不可能再有同 hash 的 key;一旦支持删除,直接置空会截断探测链,必须用墓碑标记(DELETED),查找时跳过墓碑继续探,插入时优先复用墓碑。优化方向:换更好的散列(乘法散列、扰动函数)让 5 个槽分布更均匀;用二次探测或双散列减少聚集;固定容量下控制装载因子,5 个槽最多放 3 个元素。开放地址法比拉链快的主要原因是缓存局部性:数据在连续数组里,一次 cache line 能带进多个槽,没有节点对象分配和指针追逐;拉链法每个节点都是独立对象,冲突多时一次查找要多次随机访存。微基准里差一个数量级是可能的,但「100 倍」依赖具体数据规模和实现,不能当成普遍结论——装载因子高时开放地址法会因探测变长而迅速退化。
Java 实现 left join:先明确语义:以左表为准,右表按连接键匹配,匹配不到补 null,右表一个键对应多行时左行要重复输出。朴素写法是两层循环,时间 O(n × m)。优化是哈希连接:遍历右表,用 HashMap<String, List<RightRow>> 建索引,key 是连接字段的值,value 是该键对应的所有右表行(必须是列表,否则一对多会丢行);再遍历左表,用同样的键去查,命中就为列表里每一行输出一条拼接结果,未命中输出一条右表字段全 null 的结果。平均时间 O(n + m),空间 O(m)。最好情况是键分布均匀、哈希不冲突,查找 O(1);最坏情况是哈希退化(所有键相同或 hashCode 实现很差),查找退化成链表遍历,整体 O(n × m),而且当所有键都相同时输出本身就有 n × m 行,复杂度不可能低于输出规模。实际写的时候用 Objects.equals 比较、处理好 null 键,String 字段先判空再入 map。
大文件字段怎么办:不能把文件内容读进内存做 equals,也不能直接把整个文件当 map 的 key。做法分三层:第一层用「文件大小 + 内容哈希(SHA-256)」做连接键,只比对摘要,命中后再按需读取内容;第二层改成流式处理,两边都按连接键外部排序(数据量大到内存放不下就分块排序再归并),然后双指针归并连接,空间只跟块大小有关;第三层如果右表也很大,用分块嵌套循环(block nested loop),把右表按块读入、左表流式扫,或者直接把连接下推到数据库 / 计算引擎,让它们用磁盘溢写和索引完成。核心原则是「连接键要小、可比、可哈希」,文件内容只在最终需要时取。
协议栈:一次跨网络命令调用的完整路径是:应用层——业务代码调用 gRPC stub,protobuf 序列化成二进制,gRPC 把消息封成 HTTP/2 的 DATA 帧,HEADERS 帧里带 :method、:path 和超时等元数据;传输层——HTTP/2 跑在 TCP 上(默认,TLS 时是 TLS over TCP),TCP 负责连接管理、可靠传输、按序交付、流量控制与拥塞控制;网络层——IP 负责寻址和路由;再往下是数据链路层与物理层。gRPC 默认就是 HTTP/2 + TCP,支持双向流和多路复用;HTTP/3 版本则换成 QUIC(UDP)以降低握手和队头阻塞。回答时把「序列化、分帧、连接复用、超时与重试」这几件事挂到对应层上,比背分层名字更有说服力。
用户态与内核态:Java 调 socket.getOutputStream().write() 时,数据先在 JVM 的用户态缓冲区里,最终要通过系统调用进入内核:write/sendto 触发软中断或 syscall 指令,CPU 从用户态切到内核态,内核把用户缓冲区的内容拷贝到 socket 的发送缓冲区(sk_buff),TCP 层分段、加头、维护重传队列,再交给网卡驱动,由 DMA 把数据送到网卡发出。读响应时,阻塞模式下 read 会让内核把当前线程挂到 socket 的等待队列上并让出 CPU,调度器去跑别的线程,所以线程「阻塞等待」不消耗 CPU;数据到达后网卡中断唤醒等待队列,线程重新变成可运行。NIO 则把「等」交给 epoll 的就绪通知,一个 selector 线程管理大量连接。这里可以顺带讲零拷贝(sendfile、mmap)为什么能减少用户态与内核态之间的拷贝次数。
MCP 的目的:MCP(Model Context Protocol)是模型应用与外部工具、数据源之间的标准协议,用 JSON-RPC 描述能力,核心原语是 tools(可调用工具)、resources(可读取的数据)、prompts(可复用的提示模板)。它解决的是集成爆炸问题:没有标准时,M 个模型客户端接 N 个工具要写 M × N 套适配;有了协议,工具方实现一次 server,任何支持 MCP 的客户端都能发现并调用。对工程的价值在三处:能力可插拔,换模型或换客户端不用重写集成;权限与审计有统一落点,哪个工具被谁调用、参数是什么都能在这一层记录和限制;上下文按需加载,客户端先列工具再决定调用,不必把所有工具说明一次性塞进 prompt。