哈希表

🗃️ 哈希表

哈希表是实现 O(1) 查找的核心数据结构。

🗃️哈希表

哈希表 (大小: 7)

元素: 0 | 负载因子: 0.00

[0]

→

空

[1]

→

空

[2]

→

空

[3]

→

空

[4]

→

空

[5]

→

空

[6]

→

空

📊 时间复杂度

平均: O(1)

最坏: O(n) (所有元素冲突)

💡 链地址法

冲突元素存入链表，空间换时间，适合高负载

🎯 核心概念

哈希函数

将任意键映射到固定范围的索引：

function hash(key, tableSize) {
  let sum = 0;
  for (const char of key) {
    sum += char.charCodeAt(0);
  }
  return sum % tableSize; // 取模得到索引
}

好的哈希函数特征：

确定性：相同输入 → 相同输出
均匀分布：减少冲突
高效计算：O(1) 时间

冲突解决

当两个不同的键映射到同一索引时，需要处理冲突：

方法	原理	优点	缺点
链地址法	同一桶存链表	简单、适合高负载	需要额外空间
开放寻址	向后探测空位	缓存友好	删除复杂、聚集问题

📊 复杂度分析

操作	平均	最坏	说明
查找	O(1)	O(n)	最坏：所有键冲突
插入	O(1)	O(n)	可能需要扩容
删除	O(1)	O(n)	开放寻址需标记删除

负载因子

\alpha = \frac{n}{m}

n = 元素数量
m = 桶数量
α > 0.7 时建议扩容

💻 实际应用

// JavaScript 的 Map/Object 就是哈希表
const map = new Map();
map.set('name', 'Alice');   // O(1)
map.get('name');            // O(1)
map.has('name');            // O(1)
map.delete('name');         // O(1)

// Python 的 dict
user = {'name': 'Alice', 'age': 25}
user['name']  # O(1)

// Java 的 HashMap
Map<String, Integer> map = new HashMap<>();

⚠️ 注意事项

键必须可哈希：不可变类型 (字符串、数字)
负载因子控制：过高影响性能
哈希函数选择：影响冲突率
不保证顺序：需要顺序用 LinkedHashMap

🔗 相关知识

数组 - 哈希表的底层实现
复杂度分析 - 理解 O(1) 摊销