深信服Java后端一面面经（HashMap+RAG）

《面试题目》

1. 讲讲 HashMap 的底层实现。
2. 场景算法题：给你 11 个数据，挑出其中 10 个高频搜索数据。
3. MySQL 实战拷打：索引失效的场景有哪些？跳表是什么结构？
4. Redis 的数据一致性怎么保证？
5. RAG 的切分策略：chunk size 和 chunk overlap 怎么定？
6. RAG 场景题（结合具体业务问检索与生成效果）。
7. 反问环节。

《参考解析》

HashMap 底层：JDK 8 是「数组 + 链表 + 红黑树」。默认容量 16，负载因子 0.75，元素数超过 容量 × 0.75 就扩容为 2 倍。下标计算是 (n-1) & hash，所以容量取 2 的幂；hash 先做扰动 h ^ (h >>> 16)，让高位也参与运算，减少碰撞。链表长度 ≥ 8 且 数组容量 ≥ 64 才树化，容量不足时优先扩容——这是为了避免小表过早树化。JDK 7 头插法在并发扩容时会形成环形链表导致死循环，JDK 8 改成尾插，但 HashMap 本身仍非线程安全，并发场景要用 ConcurrentHashMap（分段 CAS + synchronized 锁桶头）。

11 选 10 的场景题：这个题的关键是「反过来想」——挑 10 个高频等价于淘汰 1 个最低频的，一次遍历维护当前最小值即可，时间 O(n)、空间 O(1)，不需要排序也不需要堆。如果面试官把数据量放大到 n 选 k（k 远小于 n），标准解法是「哈希计数 + 大小为 k 的小顶堆」：先统计词频，再维护一个只装 k 个元素的小顶堆，堆顶就是这 k 个里最小的，新元素比堆顶大就替换，时间复杂度 O(n log k)；k 接近 n 时反而应该用「快速选择（quickselect）」求第 k 大，期望 O(n)。回答时先确认数据规模、是否允许内存装下全部数据，再给方案。

MySQL 索引失效：常见几类——①违反联合索引最左前缀（跳过中间列）；②在索引列上做函数、表达式或隐式类型转换（WHERE date(create_time)=...、字符串列传数字 WHERE phone=13800000000）；③前导模糊 LIKE '%abc'；④OR 两侧有一侧没索引；⑤范围查询（>、<、BETWEEN、LIKE 'abc%'）之后的列用不上索引，只能靠索引下推（ICP）在引擎层过滤；⑥区分度太低（如性别）优化器判断全表扫描更快；⑦!=、NOT IN、IS NOT NULL 在数据分布极端时也可能放弃索引。定位手段就是 EXPLAIN，重点看 type（出现 ALL 就是全表）、key、rows、filtered、Extra（Using filesort、Using temporary 要警惕）。

跳表：在有序链表上做多层索引的结构，每个节点以一定概率（Redis 里是 1/4）向上提升层数，查找从最高层开始向右走、走不动就下降一层，期望时间复杂度 O(log n)，实现比红黑树简单得多，而且天然支持范围查询（顺着底层链表扫），所以 Redis 的 zset、LevelDB 的 MemTable 都用它。MySQL 的 InnoDB 索引用的是 B+ 树而不是跳表：B+ 树一个节点装几百个键，树高只有 34 层，能把随机 IO 压到 34 次，更适合磁盘；跳表是链表结构，更适合纯内存场景。

Redis 与数据库一致性：工业界主流是 Cache Aside——先更新数据库，再删除缓存（不是更新缓存）。删除失败要有兜底：①给缓存设 TTL，最坏情况下过期后自愈；②删除失败进消息队列重试，或订阅 binlog（Canal）异步删除，把删除动作和业务解耦；③读多写少的热点 key 用「延迟双删」（更新后删一次，延迟几百毫秒再删一次）覆盖主从复制延迟窗口。要接受最终一致：想做到强一致就得上分布式锁或把读写都收敛到同一个存储，代价是吞吐。

RAG 切分策略：chunk size 没有万能值，中文文本一般落在 300~800 token，overlap 取 chunk 的 10%~20%。切分粒度要跟”检索单元”对齐：按标题层级切（Markdown 的 #、## 优先），其次按段落，再退到按句子，最后才硬切字符。切太大召回噪声多、塞进上下文浪费 token；切太小语义不完整、答案被截断。工程上还有几条：给每个 chunk 补上标题路径和元数据（来源文档、章节）便于过滤；表格、代码块单独成块不切碎；检索侧做 hybrid（向量 + BM25）加重排，并保留原文句子边界避免”半句话”。