帆软一面：双重检查锁、HashMap 扩容与快排追问

《面试题目》

1. 你的专业是网络空间安全，这属于纯软件方向吗？它更偏密码学还是网络攻防？是区块链方向吗？
2. 那你为什么考虑做纯后台开发？
3. Java 是自学的吗？学校有相关课程吗？自学主要通过什么途径？
4. 滴滴实习了三个月，简单讲讲主要做了什么？是为了完成数据分析 Agent 的能力做了一些扩展和增强吗？
5. 个人职责里你印象最深或觉得最难的是哪个？
6. 资产查询具体是什么？背景是什么？也就是去对方服务里专门开发一个批量接口来降低延迟，是吗？这个过程是你做的吗？整个方案是你独立完成的，还是导师带着你做的？
7. 这涉及跨部门或跨组操作，你们怎么完成跨组交流？遇到什么问题？对方为什么配合你？过程中有没有沟通障碍？你去找对方小组长时，是和导师一起，还是导师告诉你找谁之后你自己去？
8. 交流时怎么迅速达成一致？你做了哪些努力让人家快速接受你的方案？
9. 你写了 Spring IOC，讲讲 IOC 是什么概念？Spring 里 Bean 一般是单例，单例有哪些实现方式？
10. 能不能投屏写一段双重检查锁的实现？为什么给这个单例对象本身标记 volatile？作用是什么？外层判空是什么作用？外层已经判空了，为什么里面还要再判一次？直接把外层删了会有什么影响？如果把里面这层判空删了会怎么样？
11. volatile 除了让其他线程立即感知，还有什么作用？重排序会有什么问题，能举个实际例子吗？除了加减，赋值语句是否也有重排序问题？结合创建对象、初始化、赋值这三步，加 volatile 和不加，业务上会有什么影响？除了被覆盖，还有别的问题吗？volatile 不能保证原子性，中间被多线程处理也会有问题吗？对象还没初始化就被引用，会出什么问题？
12. Java 里 HashMap 用得多吗？讲讲 HashMap 本身的结构。是冲突时才往链表上插吗？这是拉链法吗？HashMap 不能无限加元素，除了转红黑树，还有扩容吧？扩容具体怎么执行？size、哈希这些是什么概念和过程？扩容是先开辟两倍空间再做元素迁移吗？为什么不直接把原数组变成两倍，而一定要新开辟一个 table？
13. HashMap 本身是线程安全的吗？如果要线程安全的 Map 应该怎么用？ConcurrentHashMap 的原理是什么？CAS 具体原理是什么，什么是 CAS？CAS 这种原理实践有什么问题？ABA 问题怎么理解，怎么解决？
14. 回到 HashMap，put 一个元素后，get 时能思考出什么异常场景？不考虑 JDK7 和红黑树，只考虑数组、链表、扩容。如果全程不涉及修改、只新增元素，会有什么异常场景？并发下会怎样？并发 put 时链表指针被覆盖，除了最终 get 不到，对系统、应用、JVM 线程还有什么影响？会造成内存泄漏吗？
15. 数据库之前了解过吗？讲讲数据库范式是什么。设计数据库范式的目的是什么，解决什么问题，为什么要搞这些范式？除了数据一致性，还有别的原因吗？实际代码过程中，有哪些场景需要违背范式，能举个实际例子吗？
16. 快速排序算法的原理知不知道，讲一下。快排复杂度一般是多少？最坏情况是多少？如果原来有序，复杂度是多少？怎么优化这个算法来避免坏情况？随机选取基准？还有其他思路吗？三路快排？还有吗？
17. 现在有 1 到 100 的数字，乱序，丢了一个数字，给你 99 个数字，怎样快速找到丢失的数据？除了数组、Map、求和，还有别的方式吗？除了加减乘除，可以只用位运算实现吗？

《参考解析》

双重检查锁：volatile 的两个作用都要讲全。 第一是可见性——一个线程构造完对象后，其他线程能立刻看到实例引用已赋值；第二是禁止重排序——new 的语义被拆成「分配内存、初始化、把引用赋给变量」三步，没有 volatile 时这三步之间可以重排序，别的线程可能拿到一个「引用非空但字段还是默认值」的半成品对象。所以标准写法是实例字段加 volatile、同步块内判空后再创建。破坏单例的另几条路也要能接上：反射调用私有构造、反序列化生成新实例（用 readResolve 兜）、以及枚举实现天然防这两者；再补一句 Spring 的「单例」是容器级单例，与 JVM 级单例不是一回事。

「外层判空能不能删」是这道题的收口，考的是对锁开销的理解。 外层判空是为了性能：绝大多数调用发生时实例已经创建完成，先读一次 volatile 变量就能直接返回，不必进入同步块——同步的加锁解锁有开销，且会造成不必要的竞争。里层判空是为了正确性：两个线程可能同时通过了外层判空，然后在同步块外排队，第一个线程创建完释放锁后，第二个线程如果不重新判空就会再创建一个实例，把前一个覆盖掉。所以外层删掉只损失性能、不影响正确性；里层删掉会真的破坏单例。面试官继续追问「外层判空为什么不加锁」，答「加锁就退化成每次都同步、等于放弃了 DCL 的意义」即可。

volatile 不保证原子性，所以「中间被多线程处理」是另一个维度的问题。 volatile 只保证单次读或单次写的可见性与有序性，i++ 这种读-改-写三步操作照样会丢更新，要用锁或 AtomicInteger 这类 CAS 原子类。至于「对象还没初始化就被引用」，根源是发布逸出：构造过程中把 this 交给别的线程（注册监听器、丢进线程池、赋值给静态字段）都会让别人看到一个未初始化完的对象；解决办法是构造期间不发布 this、用工厂方法或 final 字段保证安全发布，final 字段还有额外的初始化安全保证（构造完成后对其他线程可见的引用一定看到正确初始化的 final 字段）。

HashMap 扩容为什么新开 table，以及并发下会坏成什么样。 不原地扩成两倍的原因是数组长度一旦创建就不可变，而且扩容要做 rehash 把元素重新分布到新桶位置（hash & (newCap - 1)），原地改长度会让已有元素的下标语义失效、并破坏正在遍历或正在插入的线程看到的一致性；所以只能新建 table 再迁移，并且 JDK8 用「高位是 0 留原位、是 1 移到原下标 + 旧容量」的技巧避免逐个重算 hash。并发问题要分版本说：JDK7 的头插法在并发扩容时会形成环形链表，导致后续 get 死循环、CPU 打满；JDK8 改成尾插修掉了环，但并发 put 仍可能丢元素、覆盖链表指针，size 计数也会丢更新。严格说 JDK8 的变量都是非 volatile 的，丢失的元素本身会被 GC 回收、不会因为丢引用而泄漏（泄漏更可能来自长生命周期容器不断累积无用对象），答的时候区分「数据丢失」和「内存泄漏」两件事更稳。

ConcurrentHashMap 与 CAS、ABA。 JDK8 的实现是「CAS 插入空桶 + synchronized 锁单个桶的头节点 + 多线程协同扩容」，size 用 baseCount 加 CounterCell 分散计数降低竞争；读操作大多无锁，所以不是全表锁。CAS 的原理是比较并交换：读内存值 V、与期望值 A 比较、相等就写成新值 B，三步由 CPU 指令保证原子性，失败就自旋重试，代价是自旋耗 CPU、且只适合单一变量的更新。ABA 问题是值从 A 改成 B 又改回 A，CAS 只看值不看版本，会误判成「没变过」，典型场景是链表或栈的节点被复用导致结构损坏；解决办法是加版本号（AtomicStampedReference）或改用带标记的引用，业务上要区分「值相同」和「状态未变」。

数据库范式与反范式要给得出业务例子。 范式解决的是插入、更新与删除异常，以及由此带来的冗余和不一致：第一范式要求字段原子，第二范式消除非主属性对码的部分依赖，第三范式消除传递依赖，BCNF 再进一步约束决定因素。反范式是为了读性能与查询便利有意引入冗余，常见场景包括：列表页频繁联表，于是把作者昵称、商品名冗余进订单表；交易数据要保留下单当时的快照（价格、地址），这与规范化正好相反但业务上必须；报表预先汇总成宽表；分库分表后无法跨库 join，只能冗余。收尾补一句治理方式——冗余字段靠事务内同步或异步补偿保持一致，并写对账任务兜底。

快排优化与位运算找缺失数。 快排平均 O(n log n)、最坏 O(n²)，最坏出现在每次划分极度不均，比如已有序且固定取首元素为基准；优化手段有随机基准、三数取中、三路快排（把等于基准的元素聚到中间，专治大量重复元素）、小区间切插入排序、以及尾递归优化把递归深度压到 O(log n)。找 1 到 100 缺失的那个数，常规解法是求和相减（可能溢出）或开布尔数组/哈希表标记；位运算的解法是把 1 到 100 全部异或，再与 99 个数字依次异或，成对的数两两抵消，剩下的就是缺失值——只用到 XOR 的结合律与自反性，额外空间 O(1)；如果缺失两个数，可以先整体异或得到两个数的异或值，再按最低不同位把集合分成两半分别求。