字典和哈希表（javascript版）

在 JavaScript 中，没有哈希表，哈希表是字典的一种实现，字典（Dictionary）和哈希表（Hash Table）本质上都是用于存储键值对的数据结构，但它们在实现和使用场景上有一些区别。下面从概念、实现和应用角度详细解析：

一、基本概念

字典（Dictionary）
- 抽象概念： 一种以键值对形式存储数据的集合，键必须唯一，通过键快速查找对应的值。
- 核心操作： 插入、删除、查找、遍历。
- 特点： 不强制要求高效的哈希函数，更关注接口的通用性。
哈希表（Hash Table）
- 具体实现： 通过哈希函数将键映射到存储桶（Bucket），以实现高效的插入、查找和删除。
- 核心机制： 哈希函数：将键转换为索引。
- 冲突处理： 解决不同键映射到同一索引的问题（如链地址法、开放寻址法）。
- 特点： 平均时间复杂度为 (O(1))，适合大规模数据存储。

二、JavaScript 中的实现

字典的实现JavaScript 中没有内置的 Dictionary 类，但可以用以下方式实现：

方式一：使用普通对象（Object）

const dict = {};
// 添加键值对
dict["name"] = "John";
dict[123] = "Number Key"; // 数字键会被转换为字符串// 访问值
console.log(dict["name"]); // 输出: John// 检查键是否存在
console.log("name" in dict); // 输出: true// 删除键值对
delete dict[123];

方式二：使用 Map 对象（推荐）

const dict = new Map();
// 添加键值对（键可以是任意类型）
dict.set("name", "John");
dict.set(123, "Number Key");
dict.set({}, "Object Key");// 访问值
console.log(dict.get("name")); // 输出: John// 检查键是否存在
console.log(dict.has(123)); // 输出: true// 获取键值对数量
console.log(dict.size); // 输出: 3// 删除键值对
dict.delete(123);

哈希表的实现JavaScript 中没有直接的 HashTable 类，但 Map 对象的底层实现通常使用哈希表：

const hashTable = new Map();// 操作与字典示例相同hashTable.set("key", "value");console.log(hashTable.get("key")); // 输出: value

如果需要手动实现哈希表（展示原理）：

	class HashTable {constructor(size = 10) {this.buckets = Array(size).fill(null).map(() => []);}// 简单哈希函数hash(key) {return key.toString().length % this.buckets.length;}// 设置键值对set(key, value) {const index = this.hash(key);this.buckets[index].push([key, value]);}// 获取值get(key) {const index = this.hash(key);return this.buckets[index].find(([k]) => k === key)?.[1];}}// 删除键值对delete(key) {const index = this.hash(key);const bucket = this.buckets[index];for (let i = 0; i < bucket.length; i++) {const [storedKey] = bucket[i];if (storedKey === key) {bucket.splice(i, 1);return true;}}return false;}// 获取所有键keys() {const keys = [];for (const bucket of this.buckets) {for (const [key] of bucket) {keys.push(key);}}return keys;}
}// 使用示例
const table = new HashTable();
table.set("name", "Alice");
table.set(123, "Number Value");
console.log(table.get("name")); // 输出: Alice
console.log(table.keys()); // 输出: ['name', 123]

三、核心区别与联系

特性	字典（Dictionary）	哈希表（Hash Table）
本质	抽象数据类型（接口规范）	具体数据结构（实现方式）
实现方式	可基于数组、哈希表等	必须使用哈希函数和存储桶
键的类型限制	无强制要求	需可哈希（能通过函数转换为索引）
时间复杂度	取决于实现（可能为 (O(n))）	平均 (O(1))，最坏 (O(n))
JavaScript 实现	Object 或 Map	Map（底层通常用哈希表实现）

四、应用场景

字典的适用场景
- 简单键值对存储： 无需复杂哈希计算，如配置项管理。
- 需要保持插入顺序： Map 会按插入顺序遍历。
- 键为非原始类型： 如对象作为键（Map 支持）。
哈希表的适用场景
- 大规模数据快速查找： 如数据库索引、缓存系统。
- 高效去重： 利用哈希函数的快速判重。
- 算法优化： 如两数之和问题（LeetCode 第 1 题）。

五、性能对比

操作	普通对象（Object）	Map	手动哈希表
插入	快（(O(1))）	快（(O(1))）	平均 (O(1))
查找	快（(O(1))）	快（(O(1))）	平均 (O(1))
删除	中等（(O(1))，但有开销）	快（(O(1))）	平均 (O(1))
遍历	中等（顺序不确定）	快（保持插入顺序）	取决于实现
J键类型	字符串或 Symbol	任意类型	需可哈希