面经 - 召田最帅boy

哈希

hashCode() 与 equals() 决定了键在 HashMap 中的定位与比较，若实现不当会导致冲突或误判相等，直接影响集合的准确性。HashMap 以键值对存储，使用键的 hashCode 计算数组下标并在冲突时通过链表或 JDK8 起的红黑树保存，支持 put/get 的快速访问；容量与负载因子决定扩容时机，扩容后桶数保持 2 的幂次。HashMap 不是同步的，key、value 可为 null，映射无序。构造一致性哈希时在 2³² 环上放置节点，按键的 hash 顺时针定位最近节点，提升扩缩容时的路由稳定性。作为键的对象必须保证 hashCode 在生命周期内不变。HashSet 仅保存唯一元素，内部基于 HashMap 实现，存取无序。

2023-03-01 18:00:04 阅读

树

本文围绕树结构的常见面试考点展开，首先说明 TreeSet 与 TreeMap 在排序时分别要求元素或键实现 Comparable 接口，或在 Collections.sort 中提供 Comparator 实现自定义比较；随后给出实现 Comparable 的 Student 示例以及 TreeSet 的使用演示。接着介绍二叉树的层序遍历、深度求解（递归与非递归两种实现）以及计算任意两节点最长路径的思路，并提供相应的 Java 代码片段。最后简要比较 B+ 树与 B‑树：前者内部节点不存数据、叶层链表化、查询复杂度固定为 log n，适合外部存储和区间查询；后者键值同存、查询复杂度随键位置变化。

2023-03-01 18:01:43 阅读

遍历

本文通过两个 Java 示例说明遍历的基本思想。第一个示例实现二叉树的 Z 字型层序遍历，利用队列逐层访问节点并通过布尔标记在奇偶层之间切换顺序，必要时对当前层结果进行反转。第二个示例演示文件系统的递归遍历，使用 `File` 类遍历指定目录，若遇文件直接输出名称，若遇子目录则递归调用以遍历其全部子文件，实现对整个文件夹及其子文件夹的完整遍历。两段代码均突出遍历的实现方式和常用技巧。

2023-03-01 18:03:34 阅读

链表

本文围绕单向链表的常见面试题展开，首先介绍使用快慢指针判断链表是否成环的原理；随后指出在哈希桶中使用链表存储会导致查找、插入、删除效率低下；接着给出奇数位升序、偶数位降序链表转为整体升序的思路——按奇偶位拆分为两链表、将偶数链表逆序再合并，并提供完整实现代码；随后展示 O(1) 额外空间的随机指针链表复制算法；最后给出标准的单链表反转实现。整体阐述了链表环检测、性能缺陷、排序合并、深拷贝及反转等关键技术要点。

2023-03-01 18:05:02 阅读

数组

本文介绍了几道常见的数组面试题及其核心思路：① 用层层交换实现二维矩阵顺时针旋转90°；② 利用全体异或找出唯一不成对的元素；③ 通过哈希表在 O(n) 时间内求和为 S 的两数下标；④ 使用 Kadane 算法求连续子数组最大和；⑤ 采用快排划分（或堆）实现前 K 大元素的快速查找。每个实现均给出关键代码示例。

2023-03-01 18:06:42 阅读

排序

本文先给出Java实现的冒泡排序代码示例，随后列出常见排序算法分类：插入、交换、选择、归并、分配等，并简要说明各子类。接着阐述归并排序的分治合并过程、堆排序通过构建大（小）顶堆并不断取堆顶的原理。再介绍在数据流中实时获取中位数的做法：使用最大堆保存左半部分、最小堆保存右半部分，插入为O(log n)，取中位数为O(1)。最后给出快速排序的划分思路及双指针交换过程。

2023-03-01 18:08:45 阅读

堆与栈

文章阐述了 Java 内存划分：堆区存放对象实例，由所有线程共享，需通过 new 分配，由垃圾回收器回收；栈区为每线程私有，仅存基本类型值和对象引用，由编译器自动分配释放，访问速度快；方法区（静态区）存放类信息、static 与全局变量，同样共享。对比堆与栈：堆容量大、手动/GC 分配、访问相对慢；栈容量小、自动分配、后进先出、访问快。并通过字符串创建示例说明两者在实际使用中的差异。

2023-03-01 18:10:11 阅读

队列

Java PriorityQueue 是基于堆实现的无界队列，元素按自然顺序或自定义比较器排序。创建时可指定比较器，队列不接受 null 值。它不是线程安全的，入队和出队的时间复杂度均为 O(log n)。

2023-03-01 18:11:43 阅读

高级算法

文章介绍了几种常见的面试算法及实现要点。首先阐述了LRU（最近最少使用）缓存的原理、get/put 接口及其命中率、复杂度等特性。随后简述逆波兰（后缀）表达式无需括号的优势。接着给出基于 MD5 的 URL 短链压缩思路。随后详细说明 SnowFlake 分布式全局唯一自增 ID 的 64 位结构、优缺点。最后提供了 LFU（最不经常使用）缓存的 O(1) 时间复杂度实现代码，包括节点和哈希表的设计。

2023-03-01 18:15:09 阅读

设计模式

本文围绕面向对象的设计原则与常用设计模式展开。概述了六大原则：单一职责、里氏替换、依赖倒置、接口隔离、迪米特（最少知识）和开闭原则，阐明其含义及对高内聚、低耦合、可复用、可维护和可扩展性的促进作用。随后给出单例模式的实现示例，包括饿汉式、懒汉式及其线程安全写法。最后介绍工厂模式的概念及实现，分别展示了简单工厂、工厂方法的代码结构，说明了工厂模式在把对象创建职责抽象化、解耦客户端与具体实现方面的价值。

2023-03-01 18:16:41 阅读

场景题

文章分别介绍了微信红包、秒杀系统、扫码登录、单点登录和本地缓存的实现要点。红包采用实时内存计算、随机算法、Cache计数防超发；秒杀需防超卖、限流、Redis预减库存、URL动态化、异步下单等；扫码登录通过二维码ID关联Token，分待扫描、已扫待确认、已确认三阶段完成；SSO实现全局会话与局部会话的令牌授权及统一注销；本地缓存关注数据结构、容量上限、LRU/FIFO等淘汰策略、过期时间和线程安全。

2023-03-01 18:18:32 阅读

UML

UML提供多种图形化符号描述系统的静态和动态结构，包括用例图、类图、时序图、协作图、状态图、活动图、构件图、部署图等。其中，用例图用于捕获需求并展示功能模块及其关系，类图描述类及类间关联，时序图展示对象交互及消息顺序，这三图是最关键的。

2023-03-01 18:20:04 阅读