红黑树是自平衡二叉搜索树，通过颜色规则保证O(log n)操作效率；哈希表利用哈希函数映射键值，结合链地址法处理冲突，实现平均O(1)的查找、插入与删除，适用于缓存、字典等场景，二者在有序性与性能侧重上各有优势。
红黑树和哈希表是两种在实际开发中非常重要的数据结构。虽然JavaScript本身没有内置这两种结构，但我们可以用其语言特性来实现它们。下面分别介绍红黑树和哈希表的基本原理与简单实现。
红黑树的基本概念与实现
红黑树是一种自平衡的二叉查找树，通过为每个节点添加颜色属性（红色或黑色）并遵守一系列规则，确保树的高度大致保持对数级别，从而保证插入、删除和查找操作的时间复杂度为O(log n)。
红黑树满足以下五个性质：
- 每个节点是红色或黑色
- 根节点是黑色
- 所有叶子（null节点）是黑色
- 如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
这些性质保证了最长路径不超过最短路径的两倍，使树近似平衡。
立即学习“Java免费学习笔记（深入）”；
以下是红黑树节点的定义：
class RBNode {
constructor(value) {
this.value = value;
this.color = 'red'; // 新插入节点默认为红色
this.left = null;
this.right = null;
this.parent = null;
}
}
红黑树的核心操作包括插入、删除和旋转（左旋、右旋）。插入后若破坏了红黑性质，需通过变色和旋转来修复。由于完整实现较为复杂，涉及多种情况判断，这里只展示插入后修复的关键思路：
- 插入节点为根，则涂黑
- 父节点为黑色，无需处理
- 父节点为红色，则检查叔节点颜色，进行变色或旋转（LL、LR、RR、RL情况）
由于篇幅限制，完整红黑树实现建议参考算法书籍或开源项目，但理解其平衡机制对掌握高级数据结构很有帮助。
哈希表的原理与简易实现
哈希表是一种基于键值对存储的数据结构，通过哈希函数将键映射到数组索引，实现平均情况下O(1)的查找、插入和删除效率。
关键问题包括哈希函数设计、冲突处理和扩容机制。常用冲突解决方法有链地址法（拉链法）和开放寻址法。下面使用链地址法实现一个简单的哈希表：
class HashTable {
constructor(size = 8) {
this.size = size;
this.buckets = Array(size).fill(null).map(() => []);
}
// 简单哈希函数
hash(key) {
let h = 0;
for (let i = 0; i < key.length; i++) {
h = (h * 31 + key.charCodeAt(i)) % this.size;
}
return h;
}
// 插入或更新
set(key, value) {
const index = this.hash(key);
const bucket = this.buckets[index];
const existing = bucket.find(entry => entry.key === key);
if (existing) {
existing.value = value;
} else {
bucket.push({ key, value });
}
}
// 获取值
get(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
const entry = bucket.find(entry => entry.key === key);
return entry ? entry.value : undefined;
}
// 删除
remove(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
const indexInBucket = bucket.findIndex(entry => entry.key === key);
if (indexInBucket !== -1) {
bucket.splice(indexInBucket, 1);
return true;
}
return false;
}
}
这个实现存在一些可优化点：比如动态扩容（当负载因子过高时重建哈希表）、更优的哈希函数（避免碰撞）、支持非字符串键等。但在大多数场景下，这种结构已能满足基本需求。
应用场景对比
红黑树适合需要有序遍历、范围查询或严格时间保障的场景，例如：
- 集合或映射的有序实现（如Java中的TreeMap）
- 需要按顺序访问元素的系统
- 实时性要求高的系统（最坏情况O(log n)）
哈希表更适合追求极致平均性能的场景：
- 缓存系统（如LRU缓存底层常结合哈希表）
- 字典、配置项存储
- 去重操作（Set结构）
JavaScript中的Object和Map底层通常使用哈希表或类似优化结构实现，而Set和Map保持插入顺序是因为额外维护了链表结构。
基本上就这些。理解这两种结构有助于写出更高效的代码，尤其是在处理大量数据时做出合理选择。
