MySQL 为什么用 B+ 树，Redis ZSet 为什么用跳表？

[面试官]：那 ZSet 怎么快速查单个元素？
[我]：别忘了它还有个哈希表！查分数值直接 O(1) 搞定。

// 伪代码感受下跳表的插入逻辑
// 不像红黑树那样需要复杂的旋转平衡
void insert(Node node) {
    int level = randomLevel(); // 随机决定这个节点有多高
    // 更新各层指针...
    // 纯链表操作，并发下也比树好控制（虽然 Redis 是单线程）
}

HashMap 里的红黑树机制

面试官：好，最后问你 HashMap。JDK 1.8 引入了红黑树，这又是图啥？

✅ 正确回答：这是为了兜底。
HashMap 主体还是数组 + 链表。只有当链表冲突太严重（链表长度 >= 8 且 数组容量 >= 64）时，链表才会变成红黑树。

[面试官]：为啥这里不用跳表或者 B+ 树？
[我]：

1. 内存占用：B+ 树节点大，浪费内存。
2. 查询性能：红黑树是平衡二叉树，查询复杂度 O(logN)。当冲突严重时，比链表的 O(n) 快得多。
3. 为啥不用 AVL 树？ AVL 树太严格平衡了，插入删除要疯狂旋转。红黑树平衡要求宽松，旋转次数少，更适合 HashMap 这种频繁插入删除的场景。

易错点：HashMap 哈希计算

这里有个90% 的人都会挂的易错点，关于 HashMap 的哈希计算。

[面试官]：HashMap 的数组长度为啥非要是2 的次幂？

❌ 小白回答：呃… 可能是为了吉利？程序员喜欢 2？

✅ 揭秘：
这是为了性能！
计算索引位置本该用取模：hash % length。
但如果 length 是 2 的次幂，hash % length 就等价于 hash & (length - 1)。
位运算（&）比取模运算（%）快得多！

而且，为了防止哈希冲突，HashMap 还搞了个扰动函数：把 hashCode 的高 16 位和低 16 位做异或。
这也解释了为啥要用 2 的次幂——为了让高位特征也能参与运算，让数据散列得更均匀。

// JDK 1.8 源码片段
// 这行代码价值千金
static final int hash(Object key) {
    int h;
    // 高 16 位异或低 16 位，这就是扰动函数
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 索引计算
// n 必须是 2 的次幂，否则分布就不均匀了
int index = (n - 1) & hash;

总结清单

面试被问到数据结构选型，可以参考以下结论：

1. MySQL (InnoDB)：

   • 结构：B+ 树。
   • 理由：叶子节点存全量数据且相连，扫库、范围查询无敌，树矮减少磁盘 IO。

2. Redis (ZSet)：

   • 结构：跳表 + 哈希表。
   • 理由：内存操作，无需考虑磁盘 IO。跳表实现简单，范围查询（排行榜）比红黑树更高效。

3. HashMap (JDK 1.8)：

   • 结构：数组 + 链表 + 红黑树。
   • 理由：红黑树是对链表过长时的性能兜底。选择红黑树是因为它在插入性能和查询性能之间取得了平衡（比 AVL 树插入快）。

技术没有银弹，只有取舍。下次面试官再问这种题，你就拿这些场景举例！