快手 AI 全栈一面(秋招):HashMap、JVM、MySQL 与召回打分
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 介绍实习项目,并回答面试官围绕项目展开的追问。
- 介绍 Java HashMap 底层实现原理。
- HashMap 如何判断哈希冲突?通过什么方式判断两个 key 相等?
- 介绍 JVM 内存区域结构与垃圾回收相关机制。
- MySQL 索引底层是如何实现的?
- AI Coding:实现 scammer 召回打分与 token 预算裁剪逻辑。
- 算法题:给定股票价格数组,仅允许买卖一次,求最大收益,除双重 for 外有无其他解法?
《参考解析》
HashMap 底层:JDK 8 的结构是「数组 + 链表 + 红黑树」。put 先对 key.hashCode() 做扰动 h ^ (h >>> 16),让高位也参与定位,再用 (n - 1) & hash 落到某个桶(容量是 2 的幂,位运算等价于取模但更快)。桶为空就放新节点;桶里已有元素,就沿链表逐个比较 hash 和 equals,相同则覆盖 value,不同则尾插。链表长度达到 8 且数组长度达到 64 时转红黑树,查询从 O(n) 降到 O(log n);数组长度不够 64 时优先扩容而不是树化。元素数超过「容量 × 0.75」触发扩容,容量翻倍,JDK 8 把旧链表拆成「低位链」和「高位链」分别挂到原位置和原位置加旧容量上,避免重新计算 hash。key 为 null 时固定放在 0 号桶。并发场景不能用它,改用 ConcurrentHashMap:JDK 8 用 CAS 写空桶、synchronized 锁桶头,锁粒度是一个桶,扩容时多线程可以协同迁移。
哈希冲突与 key 相等:冲突指的是两个不同的 key 经过扰动和取模落到了同一个桶,这是不可避免的(桶数远小于 key 空间),靠链表或红黑树解决。判断两个 key 是否相等分两步:先比 hash,hash 不同一定不相等;hash 相同再比 == 或 equals,引用相同直接算相等,否则调用 equals。所以自定义对象作 key 必须同时正确重写 hashCode 和 equals:只重写 equals 会导致相等对象散到不同桶、查不到;只重写 hashCode 会让本应相等的对象被判为不同。equals 要满足自反、对称、传递、一致,参数类型必须是 Object,还要和 hashCode 的字段保持一致。反过来,hash 冲突不代表 key 相等,最终仍要靠 equals 定论。
JVM 内存与 GC:运行时数据区按线程私有和共享分。线程私有的有程序计数器、虚拟机栈、本地方法栈:虚拟机栈按栈帧存局部变量表、操作数栈、动态链接和返回地址,递归太深会 StackOverflowError;程序计数器记录当前字节码行号,是唯一不会 OOM 的区域。线程共享的是堆和方法区(JDK 8 起用元空间实现,跑在本地内存),堆分新生代(Eden + 两个 Survivor)和老年代,对象优先在 Eden 分配,经历若干次 Minor GC 仍存活就晋升老年代;大对象可能直接进老年代。此外还有直接内存(NIO 的 DirectByteBuffer),不受堆大小限制但受物理内存和 MaxDirectMemorySize 约束。GC 的判断标准是可达性分析,从 GC Roots(栈上引用、静态变量、常量、JNI 引用等)出发,不可达的对象才可回收,不是引用计数。Minor GC 回收新生代,Major/Full GC 覆盖老年代和整个堆,Full GC 通常伴随较长停顿。收集器从 Serial、Parallel、CMS 到 G1、ZGC:G1 把堆切成大小相等的 Region,按回收收益优先处理,可以设定停顿目标;ZGC 用染色指针和读屏障做并发标记与整理,停顿在毫秒级,代价是内存和 CPU 开销更高。回答时把「分代假设、可达性、停顿目标、吞吐与延迟的取舍」串起来,比背名词更有层次。
MySQL 索引:InnoDB 用 B+ 树。聚簇索引的叶子节点直接存整行数据,所以一张表只能有一个聚簇索引,通常是主键;二级索引的叶子存的是索引列加主键值,查非索引列要拿主键回表再查一次聚簇索引。B+ 树的特点是只有叶子存数据、非叶子只存键,扇出大、树高低,一页默认 16KB,三层就能存千万级数据;叶子之间用双向链表连接,范围查询和排序友好。不用 B 树是因为 B 树的非叶子也存数据,同样页大小能放的键更少、树更高,且范围扫描要在层间跳;不用哈希是因为哈希只支持等值查询,范围、排序、最左前缀都用不了。设计索引时看区分度(基数),遵循最左前缀,尽量用覆盖索引避免回表,注意隐式类型转换和函数操作会让索引失效;EXPLAIN 看 type、key、rows 和 Extra,Using index 是覆盖索引,Using filesort、Using temporary 要警惕。联合索引把等值条件放前面、范围条件放后面,更新频繁的列不适合建太多索引。
scammer 召回打分与 token 预算:这题考的是把风控召回和上下文预算放在一条链路上。打分侧先定义标签与目标(欺诈账号、黑产设备、刷单、导流等),特征分四类:账号属性(注册时长、实名、历史处罚)、设备与环境(设备指纹、模拟器、代理 IP、地理位置跳变)、行为序列(短时间高频操作、批量关注/私信、路径异常)、内容与关系(文本模板化、相同话术、与已知黑产账号的图关系)。工程上用「规则兜底 + 模型打分」:规则处理明确的高危模式,模型(LR/GBDT/双塔)输出概率,再做分数校准,按业务可接受的准确率选阈值;召回阶段宁可放宽阈值,把候选交给后面的复核,同时记录特征快照保证可解释、可回溯。在线服务要注意特征时效与离线一致性、延迟预算、以及误伤申诉通道。
token 预算裁剪的核心是「在固定预算下最大化信息价值」。把候选上下文拆成可独立取舍的片段(历史消息、检索文档、工具结果、候选列表),每段估一个价值分(与当前 query 的相关度、时效性、是否含关键实体)和 token 成本,按「价值/成本」排序做贪心填充;预算将满时优先保留硬约束(系统指令、当前问题、最近一轮对话),对长文档做摘要或只取命中段落,对重复内容去重,对低分片段直接丢弃。更严谨一点可以把它建模成 0/1 背包,但片段数量大时贪心加局部调整就够了。实现上要留下「裁掉了什么、为什么裁」的日志,方便评估召回质量;同时给预算留 10%–20% 余量给输出,避免输入占满导致回答被截断。
股票买卖一次:双重循环是枚举买入日和卖出日,O(n²)。更优的是一次遍历:维护「到目前为止的最低价格」minPrice 和「当前最大收益」maxProfit,对每个价格 p,先用 p - minPrice 更新最大收益,再用 p 更新最低价格;顺序不能反,否则会用当天价格和自己相减。时间 O(n)、空间 O(1)。贪心成立的原因是:以某天为卖出日时,最佳买入日一定是它之前价格最低的那天,扫一遍就覆盖了所有候选。追问「可以买卖多次」就累加所有上涨区间的差值;「最多 k 次」用动态规划,dp[k][0/1] 表示第 k 次交易持有/不持有现金的最大收益,可以滚动数组压到 O(k) 空间;「含冷冻期/手续费」在状态转移里加约束即可。