哈希集合是一种基于哈希表实现的数据结构，它能够存储唯一的元素，并提供高效的插入、删除和查找操作。在JavaScript中，虽然原生的Set对象已经足够强大，但深入探究其底层实现机制，不仅有助于我们在算法面试中脱颖而出，更能帮助我们在处理海量数据时做出更优的架构决策。实现哈希集合的关键在于哈希函数的设计以及哈希冲突的妥善处理。
哈希集合的基本原理与设计思路
要实现一个哈希集合，首先需要理解它的核心运作机制。哈希集合本质上是一个数组，但与普通数组不同的是，它不通过索引直接访问元素，而是通过一个哈希函数将元素的值映射为数组的索引。当我们想要存入一个值时，先计算该值的哈希码，然后根据哈希码计算出在数组中的位置，将其存入。
理想情况下，每个不同的元素都能映射到不同的数组位置。这样无论是插入还是查找，时间复杂度都是常数级别。然而现实情况是，数组的长度是有限的，而元素的取值范围可能无限大。这就不可避免地会出现两个不同的元素被映射到同一个数组索引的情况，这种现象被称为哈希冲突。
此外，哈希集合与哈希映射略有不同。哈希映射存储的是键值对，而哈希集合仅存储键本身，可以看作是哈希映射的一种特例。在JavaScript中，我们可以利用对象或者数组来作为底层的存储容器，考虑到数组在索引访问上的高效性，通常选择数组作为底层结构。
从零实现一个简易的哈希集合
在没有考虑哈希冲突之前，我们可以先搭建一个简易的哈希集合骨架。我们需要定义一个集合类，初始化一个固定大小的数组，并提供一个简单的哈希函数。对于字符串类型的元素，我们可以通过累加字符的ASCII码值并对数组长度取模来生成索引。
在这个简易版本中，add方法负责计算索引并将元素存入数组对应位置。contains方法用于判断元素是否存在，remove方法则用于删除元素。需要注意的是，这种直接覆盖数组位置的做法存在严重缺陷，一旦发生冲突，旧数据就会丢失。
下面是一个简易版哈希集合的代码实现，它展示了基本的哈希计算和数组操作逻辑，为后续引入冲突处理机制打下基础。
class SimpleHashSet {
constructor(size = 100) {
this.size = size;
this.table = new Array(size);
}
hash(key) {
let hashValue = 0;
const stringKey = String(key);
for (let i = 0; i < stringKey.length; i++) {
hashValue += stringKey.charCodeAt(i);
}
return hashValue % this.size;
}
add(key) {
const index = this.hash(key);
this.table[index] = key;
}
contains(key) {
const index = this.hash(key);
return this.table[index] === key;
}
remove(key) {
const index = this.hash(key);
if (this.table[index] === key) {
this.table[index] = null;
}
}
}
深入理解哈希冲突及链地址法处理
前面的简易版代码在遇到哈希冲突时会直接覆盖原有数据，这在实际应用中是不可接受的。为了解决这个问题，最常用的方法是链地址法。链地址法的核心思想是：不再将元素直接存储在数组的对应索引处，而是将数组的每个位置作为一个桶，桶里存放一个链表或数组。当发生冲突时，将冲突元素追加到该桶的链表或数组中。
使用链地址法后，查找和删除操作需要先定位到桶，然后在桶内的链表中进行线性查找。虽然这增加了查找时间，但在合理的负载因子下，链表长度通常很短，对性能的影响微乎其微。相比于开放寻址法，链地址法对大装载因子的容忍度更高，实现起来也更为直观。
在JavaScript中，我们可以直接使用数组来代替链表，因为JS的数组天然支持动态扩容和丰富的操作方法。我们将底层存储结构改为二维数组，每次插入元素时，先找到对应的桶，再检查桶内是否已存在该元素，避免重复插入。
class HashSetWithChaining {
constructor(size = 100) {
this.size = size;
this.table = new Array(size).fill(null).map(() => []);
}
hash(key) {
let hashValue = 0;
const stringKey = String(key);
for (let i = 0; i < stringKey.length; i++) {
hashValue += stringKey.charCodeAt(i);
}
return hashValue % this.size;
}
add(key) {
const index = this.hash(key);
const bucket = this.table[index];
if (!bucket.includes(key)) {
bucket.push(key);
}
}
contains(key) {
const index = this.hash(key);
const bucket = this.table[index];
return bucket.includes(key);
}
remove(key) {
const index = this.hash(key);
const bucket = this.table[index];
const keyIndex = bucket.indexOf(key);
if (keyIndex !== -1) {
bucket.splice(keyIndex, 1);
return true;
}
return false;
}
}
性能评估与扩容机制探讨
哈希集合的性能高度依赖于哈希函数的均匀分布程度和底层数组的容量。如果哈希函数设计不当，导致大量元素集中在少数几个桶中，哈希集合就会退化为一个链表，查找时间复杂度从O(1)恶化到O(n)。因此，设计一个能够均匀分布键的哈希函数至关重要。
随着集合中元素数量的不断增加，冲突的概率也会随之上升。为了维持高效的操作性能，我们需要引入负载因子的概念。负载因子等于集合中元素的总数除以底层数组的容量。当负载因子超过某个设定的阈值（例如0.75）时，就需要对哈希表进行扩容。
扩容操作通常是将底层数组的容量翻倍，并将所有现有的元素重新哈希并插入到新的数组中。这是一个耗时的操作，时间复杂度为O(n)，但由于扩容操作并不频繁，平摊到每次插入操作上的成本仍然是常数级别。通过动态扩容，哈希集合能够在空间和时间之间取得良好的平衡，确保在数据量增长时依然保持卓越的性能表现。