2025-06-30发表算法随想录 / 哈希表13 分钟读完 (大约1949个字)

代码随想录算法训练营第6天｜哈希表Part01

JavaScript 中常见的四种哈希结构

在解决哈希相关问题时，JavaScript 提供了四种常见的数据结构：

数组（Array）
对象（Object）
集合（Set）
映射（Map）

我们分别来看它们在哈希法中的应用与特点。

数组 Array

数组是 JavaScript 中最基础的数据结构，可以使用下标快速访问元素，性能高，代码简洁。适用于下标直接映射的场景，比如小范围的整数索引。

const arr = [];

// 添加元素
arr[1] = 'apple';
arr[3] = 'banana';

// 获取元素
console.log(arr[1]); // 输出: apple

// 检查是否存在
console.log(arr[1] !== undefined); // true
console.log(arr[2] !== undefined); // false

// 删除元素
delete arr[1];
console.log(arr[1]); // undefined

// 获取长度（注意稀疏数组的特殊性）
// 稀疏数组：数组中有一些“中间的索引”没有实际的元素（不是 undefined，是根本没定义过）
// 稀疏数组的特殊性：是指 JavaScript 中数组的一个非直觉性特征：数组的 .length 不代表“实际有值的元素个数”，而是“最大索引 + 1”
console.log(arr.length); // 4

然而，数组并不适合用于存储非整数类型的键值对。因此在哈希场景中，数组只适用于索引为整数的映射问题。

对象 Object

对象是 JavaScript 中最传统的键值对结构，底层实现通常基于哈希表。对象的键只能是字符串或 Symbol，数字键会被自动转换为字符串。

const obj = {};

// 添加/设置属性
obj.name = 'Alice';
obj['age'] = 25;
obj[123] = 'number key'; // 123 会转换为字符串 "123"

// 获取属性
console.log(obj.name); // Alice
console.log(obj['age']); // 25
console.log(obj[123]); // number key

// 检查属性是否存在
console.log('name' in obj); // true
console.log(obj.hasOwnProperty('name')); // true
console.log(obj.height !== undefined); // false
// 在 JavaScript 中，对象属性访问有两种方式：
// 点操作符（dot notation）：obj.propName，点操作符后面必须是一个合法的标识符
// 中括号操作符（bracket notation）：obj["propName"]，里面是字符串表达式或变量，没有标识符限制

// 删除属性
delete obj.age;
console.log(obj.age); // undefined

// 获取所有键
console.log(Object.keys(obj)); // ['123', 'name']

// 获取所有值
console.log(Object.values(obj)); // ['number key', 'Alice']

对象适用于需要快速查找的键值对场景，但键的类型有限制，且原型链可能带来一些意外的属性。

集合 Set

集合（Set）是 ES6 引入的一种结构，用于存储不重复的值。底层实现是哈希表，支持高效的查找、插入和删除。

const set = new Set();

// 添加元素
set.add('apple');
set.add('banana');
set.add('apple'); // 自动去重，不会重复添加

// 检查是否存在
console.log(set.has('apple')); // true
console.log(set.has('orange')); // false

// 删除元素
set.delete('banana');
console.log(set.has('banana')); // false

// 获取大小
console.log(set.size); // 1

// 清空集合
set.clear();
console.log(set.size); // 0

// 批量添加
const fruits = new Set(['apple', 'banana', 'orange']);
console.log(fruits.size); // 3

// 遍历
fruits.forEach(fruit => console.log(fruit));

如果你需要一个高效、不重复的集合结构来快速查找或去重，Set 是最佳选择。

映射 Map

Map 是键值对（key-value）结构，允许使用任意类型的键（不仅限于字符串）。同样是基于哈希表实现，具有 O(1) 的查找和修改性能。

const map = new Map();

// 设置键值对
map.set('name', 'Alice');
map.set('age', 25);
map.set(123, 'number key'); // 支持数字键
map.set(true, 'boolean key'); // 支持布尔键

// 获取值
console.log(map.get('name')); // Alice
console.log(map.get(123)); // number key
console.log(map.get(false)); // undefined

// 检查键是否存在
console.log(map.has('name')); // true
console.log(map.has('height')); // false

// 删除键值对
map.delete('age');
console.log(map.has('age')); // false

// 获取大小
console.log(map.size); // 3

// 清空映射
map.clear();
console.log(map.size); // 0

// 批量初始化
const userMap = new Map([
  ['name', 'Bob'],
  ['age', 30],
  ['city', 'New York']
]);

// 遍历
userMap.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

// 获取所有键
console.log([...userMap.keys()]); // ['name', 'age', 'city']

// 获取所有值
console.log([...userMap.values()]); // ['Bob', 30, 'New York']

相比对象（{}），Map 支持任意类型的键，并且迭代更方便，是现代 JavaScript 中处理哈希映射的首选。

性能对比与选择建议

数据结构	键类型限制	时间复杂度	适用场景
Array	整数索引	O(1)	小范围整数索引映射
Object	字符串/Symbol	O(1)	传统键值对，兼容性好
Set	任意类型	O(1)	需要去重的集合
Map	任意类型	O(1)	现代键值对映射

总结与建议

场景	建议数据结构
索引小范围整数	Array
字符串键的简单映射	Object
需要去重的列表	Set
任意类型 key 的键值对映射	Map
兼容老代码，简单映射需求	Object

JavaScript 的 Set 和 Map 是哈希法在 JS 中的现代实现，配合 Array 和 Object 可以应对大多数需要高效查找、插入、删除的场景。在选择时，优先考虑 Map 和 Set，除非有特殊的兼容性需求或性能要求。

哈希碰撞

一般哈希碰撞有两种解决方法，拉链法和线性探测法。

拉链法发生冲突的元素都被存储在链表中，要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

LeetCode242. 有效的字母异位词

var isAnagram = function(s, t) {
  if(s.length !== t.length) return false;
  let char_count = new Map();
  for(let item of s) {
    char_count.set(item, (char_count.get(item) || 0) + 1) ;
    // 优雅的计数更新
    // 使用 (char_count.get(item) || 0) 处理键不存在的情况
    // 避免了繁琐的 if-else 判断，代码更简洁
    // 等价于：char_count.has(item) ? char_count.get(item) + 1 : 1
  }
  for(let item of t) {
    if(!char_count.get(item)) return false;
    // 巧妙的存在性检查
    // !char_count.get(item) 同时检查了两种情况：
    // 1. 键不存在（get返回undefined，!undefined = true）
    // 2. 键存在但值为0（!0 = true）
    // 这比分别检查 has() 和计数值更加高效
    char_count.set(item, char_count.get(item) - 1);
    // 计数递减策略
    // 每使用一个字符就将其计数减1，避免了最后的验证步骤
    // 这种"边验证边消费"的思路非常优雅
  }
  return true;
};

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

LeetCode349. 两个数组的交集

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {
    const set1 = new Set(nums1), res = new Set();
    for (const num of nums2) {
        set1.has(num) && res.add(num);
    }
  	// 循环 比 迭代器快
    // for(let i = nums2.length - 1; i >= 0; i--) {
        // nums1Set.has(nums2[i]) && resSet.add(nums2[i]);
    // }
    return Array.from(res);
};

JavaScript 的迭代器（如for...of、forEach）是基于迭代协议（Symbol.iterator）实现的，每次迭代都会执行以下操作：

创建迭代器对象
调用next()方法
检查done状态
处理闭包和上下文信息

这些操作会产生额外的性能开销，尤其是在处理大量数据时。相比之下，传统for循环直接通过索引访问数组元素，没有中间层的抽象，因此更高效。

#哈希碰撞