JS哈希集合实现与冲突解决方法

本文深入探讨了如何在JavaScript中实现哈希集合及其冲突处理方法。由于JS没有原生哈希集合类型，开发者通常利用Map对象进行模拟。文章重点讲解了如何处理复杂对象的哈希冲突，通过链式法将哈希值相同的元素存储在桶（数组或Set）中，并自定义`_getHashKey`和`_isEqual`方法实现内容比较与唯一性判断，从而构建一个支持内容相等性判断的哈希集合。此外，文章还讨论了自定义哈希函数的挑战，包括深层比较、属性顺序、循环引用等问题，并提供了JSON.stringify和手动拼接字符串等策略，以及使用成熟哈希算法库的建议，旨在帮助开发者理解哈希集合的原理和实践。

JavaScript没有原生的哈希集合类型，因为它依赖Object、Map和Set等通用结构来满足不同需求，而Set仅基于引用判断对象唯一性，无法实现基于内容的唯一性；我们通过Map模拟哈希集合，使用链式法处理哈希冲突，将哈希值作为键，桶（数组或Set）存储同哈希值的元素，并自定义_getHashKey和_isEqual方法实现复杂对象的内容比较与唯一性判断，从而完整构建一个支持内容相等性判断的哈希集合。

在JavaScript中实现哈希集合，我们通常不会找到一个原生的“哈希集合”类型，因为它不像其他语言那样直接暴露底层哈希表机制。我们更多的是通过利用JavaScript现有的数据结构，特别是Map对象，来模拟哈希集合的行为。至于哈希冲突处理，这通常在我们尝试将复杂对象作为键，并希望基于其“内容”而非“引用”来判断唯一性时，才真正需要我们介入解决的核心问题。

解决方案

要实现一个哈希集合，最直观且实用的方式就是基于Map来构建。Map本身就提供了键值对存储，并且它的键可以是任意类型，这在一定程度上简化了我们对“哈希”的理解——它内部已经帮我们处理了大部分键的唯一性判断。但如果我们的“集合”需要存储的是复杂对象，并且我们希望这些对象在内容相同的情况下被视为同一个元素，那么我们就需要自定义哈希逻辑和冲突处理。

一个基础的HashSet实现可以这样：

class MyHashSet {
    // 内部使用Map来存储元素。
    // 对于简单类型（字符串、数字、布尔值），Map的键已经足够作为哈希值。
    // 对于复杂对象，我们需要额外的哈希函数和冲突处理。
    constructor() {
        this.data = new Map();
    }

    /**
     * 添加一个元素到集合中。
     * @param {*} value 要添加的元素。
     * @returns {boolean} 如果元素是新添加的，返回true；否则返回false。
     */
    add(value) {
        // 这里的关键是：如何将value转换为Map能识别的“唯一键”。
        // 对于简单类型，value本身就是键。
        // 对于复杂对象，我们需要一个哈希函数。
        const key = this._getHashKey(value);
        if (this.data.has(key)) {
            // 如果Map中已经存在这个哈希键，那可能是真正的重复，也可能是哈希冲突。
            // 针对冲突，我们需要在对应的“桶”里检查value的实际内容。
            // 默认情况下，如果_getHashKey已经处理了冲突（比如返回一个唯一标识），
            // 那么这里直接判断即可。
            // 否则，如果key是哈希值，value是桶（数组），则需要遍历桶。

            // 假设_getHashKey已经足够“唯一”，或者我们正在处理简单类型。
            // 对于复杂对象，我们通常会用链表法，key对应一个数组或Set。
            let bucket = this.data.get(key);
            if (!bucket) { // 第一次遇到这个哈希值
                bucket = [];
                this.data.set(key, bucket);
            }
            // 检查桶中是否已存在该元素（基于内容比较）
            if (!bucket.some(item => this._isEqual(item, value))) {
                bucket.push(value);
                return true;
            }
            return false;
        } else {
            // 新的哈希键，直接创建桶并添加
            this.data.set(key, [value]);
            return true;
        }
    }

    /**
     * 检查集合中是否包含某个元素。
     * @param {*} value 要检查的元素。
     * @returns {boolean} 如果集合包含该元素，返回true；否则返回false。
     */
    has(value) {
        const key = this._getHashKey(value);
        const bucket = this.data.get(key);
        if (!bucket) {
            return false;
        }
        // 遍历桶，进行内容比较
        return bucket.some(item => this._isEqual(item, value));
    }

    /**
     * 从集合中删除一个元素。
     * @param {*} value 要删除的元素。
     * @returns {boolean} 如果元素被成功删除，返回true；否则返回false。
     */
    delete(value) {
        const key = this._getHashKey(value);
        let bucket = this.data.get(key);
        if (!bucket) {
            return false;
        }
        const initialLength = bucket.length;
        // 过滤掉要删除的元素
        bucket = bucket.filter(item => !this._isEqual(item, value));
        if (bucket.length === 0) {
            this.data.delete(key); // 如果桶空了，就删除这个哈希键
        } else if (bucket.length < initialLength) {
            this.data.set(key, bucket); // 更新桶
        }
        return bucket.length < initialLength;
    }

    /**
     * 返回集合中元素的数量。
     * @returns {number} 集合的大小。
     */
    get size() {
        let count = 0;
        for (const bucket of this.data.values()) {
            count += bucket.length;
        }
        return count;
    }

    /**
     * 内部方法：生成元素的哈希键。
     * 这是哈希冲突处理的关键点。
     * @param {*} value
     * @returns {string | number} 用于Map的键。
     */
    _getHashKey(value) {
        // 简单类型直接返回自身
        if (typeof value !== 'object' || value === null) {
            return value;
        }
        // 对于复杂对象，这里需要一个自定义的哈希函数。
        // 最简单粗暴（但有缺陷）的方式是JSON.stringify。
        // 后面会详细讨论如何写更健壮的哈希函数。
        try {
            return JSON.stringify(value);
        } catch (e) {
            // 处理循环引用等JSON.stringify无法处理的情况
            // 实际应用中需要更复杂的策略，比如为每个对象生成一个内部ID
            // 或者使用更高级的哈希算法库
            console.warn("无法对对象进行JSON.stringify，可能存在循环引用或非JSON兼容数据:", value);
            // 这是一个兜底方案，但会导致不同对象被视为相同，需要警惕
            return String(value); // 比如 "[object Object]"
        }
    }

    /**
     * 内部方法：判断两个值是否相等（深比较）。
     * @param {*} a
     * @param {*} b
     * @returns {boolean}
     */
    _isEqual(a, b) {
        // 对于简单类型，直接比较
        if (typeof a !== 'object' || a === null || typeof b !== 'object' || b === null) {
            return a === b;
        }
        // 简单对象浅比较（如果需要深比较，这里会很复杂）
        // 在哈希集合语境下，如果_getHashKey已经足够好，这里可能只需要浅比较
        // 否则，就需要一个递归的深比较函数
        const aKeys = Object.keys(a);
        const bKeys = Object.keys(b);

        if (aKeys.length !== bKeys.length) {
            return false;
        }

        for (const key of aKeys) {
            if (!b.hasOwnProperty(key) || a[key] !== b[key]) {
                return false;
            }
        }
        return true;
    }
}

// 示例用法
const mySet = new MyHashSet();
mySet.add(1);
mySet.add("hello");
mySet.add({a: 1, b: 2});
mySet.add({b: 2, a: 1}); // 期望被视为重复，如果_getHashKey和_isEqual处理得当
mySet.add({c: 3});

console.log("集合大小:", mySet.size); // 期望是 4 (1, "hello", {a:1, b:2}, {c:3})

console.log("是否包含 1:", mySet.has(1));
console.log("是否包含 {a:1, b:2}:", mySet.has({a:1, b:2}));
console.log("是否包含 {c:4}:", mySet.has({c:4}));

mySet.delete({a:1, b:2});
console.log("删除 {a:1, b:2} 后大小:", mySet.size);
console.log("删除后是否包含 {a:1, b:2}:", mySet.has({a:1, b:2}));

为什么JavaScript没有原生的哈希集合，我们又该如何模拟它？

JS确实没有像Java或Python那样，直接提供一个名为HashSet的内置类型。这背后的原因，我个人觉得，可能跟JavaScript的设计哲学有关：它更倾向于提供灵活且通用的基础构建块，而不是预设过多的特定数据结构。你看，Object和Map已经能满足大部分键值对存储的需求，而Set则专注于唯一值的存储。

Set虽然名字里没有“哈希”，但它内部确实实现了对值的唯一性判断。对于基本类型（数字、字符串、布尔值、undefined、null），Set能准确判断唯一性。而对于对象，Set是基于“引用”来判断的，也就是说，两个内容完全一样的对象，只要它们的内存地址不同，Set就会把它们当作两个不同的元素。这和传统哈希集合中“基于内容哈希”的概念是不同的。

所以，当我们谈论“模拟哈希集合”时，我们往往指的是：

1. 一个能存储唯一值的集合：这部分功能Set已经做得很好了。
2. 一个能处理复杂对象“内容”唯一性的集合：这才是我们自定义HashSet的真正目的。因为JS默认的对象比较是引用比较，要实现内容比较，我们就需要介入哈希和相等性判断的逻辑。

模拟它的核心思路，就像上面代码展示的，就是利用Map（或者在旧版本JS中用Object），将哈希值作为Map的键，然后将哈希到同一个值的元素放在一个“桶”里。这个“桶”通常是一个数组或另一个Set。

选择Map而非Object作为底层存储，主要有几个好处：

• 键的类型多样性：Map的键可以是任意类型，包括对象，而Object的键最终都会被转成字符串。这在某些场景下能减少我们自己处理键转换的麻烦。
• 迭代顺序：Map会保持键的插入顺序，这虽然对哈希集合本身不重要，但在调试或某些特定需求下会有帮助。
• 性能和安全性：Map在处理大量键值对时通常比普通Object有更好的性能，并且不会受到原型链污染的风险。

深入理解哈希冲突：在JavaScript中如何高效处理？

哈希冲突，简单来说，就是不同的输入（元素）经过哈希函数计算后，得到了相同的哈希值。这就像你给不同的文件贴标签，结果不小心给两个不同的文件贴了同一个标签号。在哈希集合里，这意味着两个不同的元素被分到了同一个“桶”里。

在JavaScript中处理哈希冲突，最常见且高效的策略是链式法（Separate Chaining）。我的MyHashSet实现就是采用了这种方法。

链式法的工作原理： 每个哈希桶（即Map中一个哈希键对应的值）不再直接存储单个元素，而是一个数据结构（比如数组或另一个Set），这个数据结构里存储所有哈希到该桶的元素。

1. 添加（add）时：

   • 计算元素的哈希值。
   • 根据哈希值找到对应的桶。
   • 遍历桶，检查元素是否已经存在（需要进行深层内容比较）。
   • 如果不存在，将元素添加到桶中。

2. 查找（has）时：

   • 计算元素的哈希值。
   • 根据哈希值找到对应的桶。
   • 遍历桶，进行深层内容比较，看是否存在该元素。

3. 删除（delete）时：

   • 计算元素的哈希值。
   • 根据哈希值找到对应的桶。
   • 遍历桶，找到要删除的元素，并将其移除。如果桶变空了，可以考虑从主Map中删除这个哈希键。

为什么链式法高效？

• 实现简单：相对于开放寻址法（Open Addressing，如线性探测、二次探测等），链式法更容易实现，特别是对于JavaScript这种动态语言。
• 性能稳定：即使哈希函数不是特别完美，链式法也能在一定程度上保持性能。当冲突较多时，每个桶会变成一个小型列表，操作的复杂度从O(1)退化到O(k)，其中k是桶的长度。只要哈希函数能比较均匀地分布元素，k就不会太大。
• 删除操作友好：在链式法中删除元素相对简单，不会像开放寻址法那样导致后续查找路径的断裂。

在我上面的MyHashSet代码中，this.data就是我们的哈希表，_getHashKey生成哈希值，this.data.get(key)返回的就是对应的“桶”（一个数组），而add、has、delete方法都在桶内部进行了遍历和内容比较，这就是链式法的具体体现。

自定义哈希函数：如何为复杂数据类型生成唯一标识？

这是实现一个真正意义上“内容哈希集合”最挑战的部分。JavaScript默认的对象比较是引用比较，这意味着即使两个对象{a: 1}和{a: 1}，在JS看来也是不相等的，因为它们是两个不同的内存地址。为了让它们被视为同一个元素，我们必须自定义一个哈希函数_getHashKey，以及一个相等性判断函数_isEqual。

挑战点：

1. 深层比较：对象可能包含嵌套的对象或数组，要判断内容是否相同，需要递归地比较它们的属性。
2. 属性顺序：{a: 1, b: 2}和{b: 2, a: 1}在语义上通常被认为是相同的，但JSON.stringify可能会因为属性顺序不同而生成不同的字符串。
3. 循环引用：对象内部可能互相引用，导致递归比较或JSON.stringify陷入无限循环。
4. 非可枚举属性/函数/Symbol：这些内容通常不参与哈希，或者需要特殊处理。
5. 性能：哈希函数需要足够快，否则会抵消哈希表的性能优势。

常见的（但有缺陷的）策略：

1. JSON.stringify(value)：

   • 优点：简单粗暴，对于只包含基本类型且无循环引用的“纯数据”对象非常有效。
   • 缺点：
     • 属性顺序问题：{a:1, b:2}和{b:2, a:1}会生成不同的字符串。
     • 循环引用：会抛出错误。
     • 函数/undefined/Symbol：这些属性会被忽略，导致哈希不准确。
     • 日期对象：会转为ISO字符串，但两个日期对象即使表示同一时间，如果不是同一个实例，也会被视为不同。
   • 示例：我在MyHashSet中就是用的这个，并加了try-catch。

2. 手动拼接字符串并排序键：

   • 思路：遍历对象的所有可枚举属性，将属性名和属性值拼接成一个字符串。为了解决属性顺序问题，可以先将所有属性名排序，再按顺序拼接。
   • 示例（简陋版，未处理嵌套）：

     _getHashKey(value) {
         if (typeof value !== 'object' || value === null) {
             return value;
         }
         // 简单对象，排序键后拼接
         const keys = Object.keys(value).sort();
         let hashString = '{';
         for (const key of keys) {
             hashString += `${key}:${this._getHashKey(value[key])},`; // 递归哈希
         }
         hashString += '}';
         return hashString;
     }

   • 缺点：对于深层嵌套的对象，需要递归处理，并且依然要面对循环引用和函数/Symbol等问题。性能也可能不如预期。

3. 使用一个计数器或WeakMap为每个对象生成唯一ID（仅适用于引用哈希）：

   • 如果你的“哈希集合”实际上是想存储对象的引用，并且希望每个对象实例只出现一次（类似于Set对对象的处理方式），那么可以为每个新加入的对象生成一个内部ID，并用WeakMap来存储对象到ID的映射。这样，即使对象被垃圾回收，WeakMap也不会阻止。但这并不是基于“内容”的哈希。

最健壮的自定义哈希函数通常需要：

• 深度遍历：递归地处理嵌套对象和数组。
• 循环引用检测：使用一个Set或WeakSet来跟踪已经访问过的对象，防止无限循环。
• 类型处理：根据不同类型（基本类型、对象、数组、日期、正则等）采取不同的哈希策略。
• 确定性：对于相同的输入，哈希函数必须始终产生相同的输出。
• 均匀分布：哈希值应该尽可能均匀地分布在哈希空间中，以减少冲突。

在实际项目中，如果对复杂对象的哈希集合有高性能和高可靠性要求，我们通常不会自己从零开始写一个完美无缺的哈希函数。因为这真的太复杂了。我们会倾向于寻找社区中已经经过充分测试和优化的库。但如果只是为了理解原理或处理相对简单的对象，JSON.stringify（注意其局限性）或手动排序拼接的策略，可以作为入门级的实现。

所以你看，实现一个JS的哈希集合，特别是要处理复杂对象的“内容”唯一性，它不仅仅是写几行代码的事，更是一场关于如何权衡性能、准确性和实现复杂度的思考。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~