HashMap 与二叉树：数据结构的进化之路

在数据结构的世界中，HashMap 和二叉树是两种核心结构，它们各有所长，而 JDK 1.8 的 HashMap 更是将两者巧妙结合。

二叉树基础

二叉树是每个节点最多有两个子节点的树结构：

class TreeNode {
   
    int val;
    TreeNode left;
    TreeNode right;
}

二叉搜索树 (BST)

• 左子树所有节点值 < 根节点值
• 右子树所有节点值 > 根节点值
• 查找时间复杂度：O(log n) ~ O(n)

HashMap 的演进

传统实现：数组 + 链表

早期 HashMap 使用拉链法解决哈希冲突：

// 计算桶位置
int index = hash(key) & (table.length - 1);
// 遍历链表查找
for (Node e = table[index]; e != null; e = e.next) {
   
    if (e.key.equals(key)) return e.value;
}

问题：链表过长时，查找退化为 O(n)

JDK 1.8 优化：引入红黑树

当链表长度 >= 8 且数组容量 >= 64 时，链表转为红黑树：

if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

红黑树的优势

红黑树是一种自平衡二叉搜索树，保证：

• 插入、删除、查找均为 O(log n)
• 最长路径不超过最短路径的 2 倍

性能对比

总结

HashMap 与二叉树的结合是数据结构设计的典范。理解它们的关系，能帮助我们在实际开发中做出更好的技术选型。