六、哈希表：键值存储的王者
哈希表（Hash Table）也叫做散列表，是效率最高的数据结构之一，平均情况下查找、插入、删除都是 O(1)。
6.1 哈希表的本质
哈希表的原理是：通过哈希函数将键（Key）映射到数组的某个位置，直接存取。
// 最简单的哈希表实现（理解原理）
class SimpleHashTable {
constructor(size = 10) {
this.table = new Array(size);
this.size = size;
}
// 简单的哈希函数
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i)) % this.size;
}
return hash;
}
set(key, value) {
const index = this._hash(key);
this.table[index] = value;
}
get(key) {
const index = this._hash(key);
return this.table[index];
}
}
6.2 哈希冲突与解决
当两个不同的键映射到同一个数组位置时，就发生了哈希冲突。常用解决方法是链地址法（每个位置存一个链表）。
// 使用链地址法解决冲突的哈希表
class HashTable {
constructor(size = 50) {
this.table = new Array(size);
this.size = size;
}
// 更好的哈希函数
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash * 31 + key.charCodeAt(i)) % this.size;
}
return hash;
}
set(key, value) {
const index = this._hash(key);
// 如果该位置为空，创建一个新的桶（链表）
if (this.table[index] === undefined) {
this.table[index] = [];
}
// 检查键是否已存在，存在则更新
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
this.table[index][i][1] = value;
return;
}
}
// 不存在则添加
this.table[index].push([key, value]);
}
get(key) {
const index = this._hash(key);
if (this.table[index] === undefined) {
return undefined;
}
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
return this.table[index][i][1];
}
}
return undefined;
}
delete(key) {
const index = this._hash(key);
if (this.table[index] === undefined) {
return false;
}
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
this.table[index].splice(i, 1);
return true;
}
}
return false;
}
// 打印哈希表状态
print() {
for (let i = 0; i < this.size; i++) {
if (this.table[i]) {
console.log(`${i}: ${JSON.stringify(this.table[i])}`);
}
}
}
}
// 使用示例
const ht = new HashTable(10);
ht.set("name", "张三");
ht.set("age", "25");
ht.set("city", "北京");
ht.set("name", "李四"); // 更新
console.log(ht.get("name")); // 李四
console.log(ht.get("age")); // 25
ht.delete("city");
console.log(ht.get("city")); // undefined
6.3 哈希表的负载因子与扩容
负载因子 = 元素个数 / 数组长度。当负载因子超过阈值（通常 0.75），需要扩容（rehashing）。
// 带自动扩容的哈希表
class ResizableHashTable {
constructor(initialSize = 16) {
this.table = new Array(initialSize);
this.size = initialSize;
this.count = 0; // 存储的元素个数
this.loadFactor = 0.75; // 负载因子阈值
}
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash * 31 + key.charCodeAt(i)) % this.size;
}
return hash;
}
// 检查是否需要扩容
_checkResize() {
if (this.count / this.size > this.loadFactor) {
this._resize(this.size * 2);
}
}
// 扩容（重新哈希所有元素）
_resize(newSize) {
const oldTable = this.table;
this.table = new Array(newSize);
this.size = newSize;
this.count = 0;
// 重新插入所有旧元素
for (let i = 0; i < oldTable.length; i++) {
if (oldTable[i]) {
for (const [key, value] of oldTable[i]) {
this.set(key, value);
}
}
}
}
set(key, value) {
const index = this._hash(key);
if (this.table[index] === undefined) {
this.table[index] = [];
}
// 更新已存在的键
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
this.table[index][i][1] = value;
return;
}
}
// 新增
this.table[index].push([key, value]);
this.count++;
this._checkResize(); // 检查是否需要扩容
}
get(key) {
const index = this._hash(key);
if (this.table[index] === undefined) {
return undefined;
}
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
return this.table[index][i][1];
}
}
return undefined;
}
}
6.4 哈希表的实战应用
// 1. 统计字符出现次数
function charCount(str) {
const map = new Map(); // JavaScript 内置哈希表
for (const char of str) {
map.set(char, (map.get(char) || 0) + 1);
}
return map;
}
console.log(charCount("hello world"));
// Map(7) { 'h' => 1, 'e' => 1, 'l' => 3, 'o' => 2, ' ' => 1, 'w' => 1, 'r' => 1, 'd' => 1 }
// 2. 找出数组中出现次数超过一半的元素（摩尔投票算法）
function majorityElement(nums) {
let candidate = null;
let count = 0;
for (const num of nums) {
if (count === 0) {
candidate = num;
count = 1;
} else if (num === candidate) {
count++;
} else {
count--;
}
}
// 验证 candidate 是否真的是多数元素
let actualCount = 0;
for (const num of nums) {
if (num === candidate) actualCount++;
}
return actualCount > nums.length / 2 ? candidate : null;
}
console.log(majorityElement([3, 2, 3])); // 3
console.log(majorityElement([2, 2, 1, 1, 2])); // 2
// 3. 判断两个数组是否有交集
function intersection(arr1, arr2) {
const set1 = new Set(arr1);
const result = [];
for (const num of arr2) {
if (set1.has(num)) {
result.push(num);
set1.delete(num); // 去重
}
}
return result;
}
console.log(intersection([1, 2, 2, 3], [2, 2, 4])); // [2]
七、树：层次化的数据结构
树是一种非线性数据结构，用于表示层次关系（如文件系统、HTML DOM、组织架构）。
7.1 树的基本概念
根节点（Root）
/ \
节点A 节点B
/ \ \
节点C 节点D 节点E
/
节点F
术语：
- 根节点：没有父节点的节点
- 叶子节点：没有子节点的节点
- 父节点、子节点、兄弟节点
- 深度：从根到节点的距离（根深度=0）
- 高度：从节点到最深叶子的距离
7.2 二叉树
二叉树是每个节点最多有两个子节点的树。
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 构建一个二叉树
// 1
// / \
// 2 3
// / \ \
// 4 5 6
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
7.3 二叉树的遍历
遍历是对树中所有节点的访问。
// 1. 前序遍历（根→左→右）
function preorderTraversal(root) {
const result = [];
function traverse(node) {
if (node === null) return;
result.push(node.val); // 访问根节点
traverse(node.left); // 遍历左子树
traverse(node.right); // 遍历右子树
}
traverse(root);
return result;
}
// 前序遍历结果：[1, 2, 4, 5, 3, 6]
// 2. 中序遍历（左→根→右）
function inorderTraversal(root) {
const result = [];
function traverse(node) {
if (node === null) return;
traverse(node.left); // 遍历左子树
result.push(node.val); // 访问根节点
traverse(node.right); // 遍历右子树
}
traverse(root);
return result;
}
// 中序遍历结果：[4, 2, 5, 1, 3, 6]
// 对于二叉搜索树，中序遍历得到有序序列
// 3. 后序遍历（左→右→根）
function postorderTraversal(root) {
const result = [];
function traverse(node) {
if (node === null) return;
traverse(node.left); // 遍历左子树
traverse(node.right); // 遍历右子树
result.push(node.val); // 访问根节点
}
traverse(root);
return result;
}
// 后序遍历结果：[4, 5, 2, 6, 3, 1]
// 4. 层序遍历（BFS，广度优先）
function levelOrderTraversal(root) {
if (root === null) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}
// 层序遍历结果：[[1], [2, 3], [4, 5, 6]]
7.4 二叉搜索树（BST）
二叉搜索树的特性：
左子树所有节点的值 < 根节点的值
右子树所有节点的值 > 根节点的值
左右子树也都是二叉搜索树
class BinarySearchTree {
constructor() {
this.root = null;
}
// 插入节点
insert(val) {
const newNode = new TreeNode(val);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (val < current.val) {
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else if (val > current.val) {
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
} else {
// 值相等，不插入（或根据需求处理）
return this;
}
}
}
// 查找节点
search(val) {
let current = this.root;
while (current !== null) {
if (val === current.val) {
return current;
} else if (val < current.val) {
current = current.left;
} else {
current = current.right;
}
}
return null; // 未找到
}
// 查找最小值
findMin() {
if (this.root === null) return null;
let current = this.root;
while (current.left !== null) {
current = current.left;
}
return current.val;
}
// 查找最大值
findMax() {
if (this.root === null) return null;
let current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.val;
}
// 删除节点
delete(val) {
this.root = this._deleteNode(this.root, val);
}
_deleteNode(node, val) {
if (node === null) return null;
if (val < node.val) {
node.left = this._deleteNode(node.left, val);
return node;
} else if (val > node.val) {
node.right = this._deleteNode(node.right, val);
return node;
} else {
// 找到要删除的节点
// 情况1：叶子节点
if (node.left === null && node.right === null) {
return null;
}
// 情况2：只有一个子节点
if (node.left === null) {
return node.right;
}
if (node.right === null) {
return node.left;
}
// 情况3：有两个子节点
// 找到右子树的最小节点（后继节点）
let minNode = this._findMin(node.right);
node.val = minNode.val;
node.right = this._deleteNode(node.right, minNode.val);
return node;
}
}
_findMin(node) {
while (node.left !== null) {
node = node.left;
}
return node;
}
// 中序遍历（得到有序序列）
inorder() {
const result = [];
this._inorder(this.root, result);
return result;
}
_inorder(node, result) {
if (node !== null) {
this._inorder(node.left, result);
result.push(node.val);
this._inorder(node.right, result);
}
}
}
// 使用示例
const bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
console.log(bst.inorder()); // [20, 30, 40, 50, 60, 70, 80]
console.log(bst.search(40)); // TreeNode { val: 40, left: null, right: null }
console.log(bst.findMin()); // 20
console.log(bst.findMax()); // 80
bst.delete(50);
console.log(bst.inorder()); // [20, 30, 40, 60, 70, 80]（50被删除）
7.5 树的实战应用
// 1. 计算二叉树的最大深度
function maxDepth(root) {
if (root === null) return 0;
const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// 2. 判断是否是平衡二叉树（左右子树高度差不超过1）
function isBalanced(root) {
function height(node) {
if (node === null) return 0;
const leftHeight = height(node.left);
if (leftHeight === -1) return -1;
const rightHeight = height(node.right);
if (rightHeight === -1) return -1;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
return height(root) !== -1;
}
// 3. 最近公共祖先（LCA）
function lowestCommonAncestor(root, p, q) {
if (root === null || root === p || root === q) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
if (left !== null && right !== null) {
return root; // p 和 q 分别在左右子树
}
return left !== null ? left : right;
}
