1. 项目概述
这次快手后端日常实习一面涵盖了四个核心知识点：HashMap底层实现原理、B+树索引机制、缓存三大经典问题，以及10亿级数据TopK算法。作为Java后端开发岗位的常见面试题，这些内容既考察基础数据结构的掌握程度，又检验解决实际工程问题的能力。
2. HashMap底层实现原理
2.1 数据结构设计
HashMap采用数组+链表+红黑树的结构实现。当链表长度超过8且数组长度大于64时，链表会转换为红黑树；当红黑树节点数小于6时，会退化为链表。
// JDK8中的HashMap节点定义 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // ... }2.2 哈希冲突解决
HashMap使用链地址法解决哈希冲突。当多个key的hash值相同时，会在数组的同一个位置形成链表。
注意：良好的hashCode()实现能显著减少哈希冲突。建议使用Objects.hash()方法生成复合对象的hash值。
2.3 扩容机制
HashMap默认负载因子为0.75，当元素数量超过容量*负载因子时触发扩容。扩容时会将数组大小翻倍，并重新计算所有元素的位置。
3. B+树索引原理
3.1 B+树与B树对比
| 特性 | B树 | B+树 |
|---|---|---|
| 数据存储位置 | 所有节点 | 仅叶子节点 |
| 叶子节点链接 | 无 | 有双向链表 |
| 查询稳定性 | 不稳定 | 稳定 |
3.2 MySQL中的B+树索引
InnoDB引擎使用B+树作为索引结构。聚簇索引的叶子节点存储完整数据记录，而非聚簇索引的叶子节点存储主键值。
4. 缓存三大问题
4.1 缓存穿透
解决方案：
- 布隆过滤器拦截
- 缓存空对象
- 接口层校验
4.2 缓存击穿
解决方案：
- 互斥锁
- 永不过期策略
- 缓存预热
4.3 缓存雪崩
解决方案：
- 过期时间随机化
- 多级缓存
- 熔断降级机制
5. 10亿数据TopK算法
5.1 堆排序方案
public List<Integer> topK(int[] nums, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); for (int num : nums) { heap.offer(num); if (heap.size() > k) { heap.poll(); } } return new ArrayList<>(heap); }5.2 分治法优化
对于超大数据集：
- 将数据分片
- 每个分片计算局部TopK
- 合并结果计算全局TopK
5.3 时间复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 快速排序 | O(nlogn) | O(logn) |
| 堆排序 | O(nlogk) | O(k) |
| 分治法 | O(n) | O(n/k) |
6. 面试准备建议
- 对于HashMap要能手写put/get方法的实现
- B+树要能画出插入/删除时的调整过程
- 缓存问题要结合具体业务场景分析
- TopK算法要掌握多种实现方式的trade-off
在实际开发中，这些基础知识往往会组合出现。比如电商系统的商品搜索可能同时涉及B+树索引、缓存管理和热门商品TopK计算。
