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
就会把它们当作两个不同的元素。这和传统哈希集合中“基于内容哈希”的概念是不同的。
所以，当我们谈论“模拟哈希集合”时，我们往往指的是：
一个能存储唯一值的集合：这部分功能
Set
已经做得很好了。一个能处理复杂对象“内容”唯一性的集合：这才是我们自定义
HashSet
的真正目的。因为JS默认的对象比较是引用比较，要实现内容比较，我们就需要介入哈希和相等性判断的逻辑。
模拟它的核心思路，就像上面代码展示的，就是利用
Map
（或者在旧版本JS中用
Object
），将哈希值作为
Map
的键，然后将哈希到同一个值的元素放在一个“桶”里。这个“桶”通常是一个数组或另一个
Set
。
选择
Map
而非
Object
作为底层存储，主要有几个好处：
键的类型多样性：
Map
的键可以是任意类型，包括对象，而
Object
的键最终都会被转成字符串。这在某些场景下能减少我们自己处理键转换的麻烦。迭代顺序：
Map
会保持键的插入顺序，这虽然对哈希集合本身不重要，但在调试或某些特定需求下会有帮助。性能和安全性：
Map
在处理大量键值对时通常比普通
Object
有更好的性能，并且不会受到原型链污染的风险。
深入理解哈希冲突：在JavaScript中如何高效处理？
哈希冲突，简单来说，就是不同的输入（元素）经过哈希函数计算后，得到了相同的哈希值。这就像你给不同的文件贴标签，结果不小心给两个不同的文件贴了同一个标签号。在哈希集合里，这意味着两个不同的元素被分到了同一个“桶”里。
在JavaScript中处理哈希冲突，最常见且高效的策略是链式法（Separate Chaining）。我的
MyHashSet
实现就是采用了这种方法。
链式法的工作原理：每个哈希桶（即
Map
中一个哈希键对应的值）不再直接存储单个元素，而是一个数据结构（比如数组或另一个
Set
），这个数据结构里存储所有哈希到该桶的元素。
添加（
add
）时：
计算元素的哈希值。根据哈希值找到对应的桶。遍历桶，检查元素是否已经存在（需要进行深层内容比较）。如果不存在，将元素添加到桶中。
查找（
has
）时：
计算元素的哈希值。根据哈希值找到对应的桶。遍历桶，进行深层内容比较，看是否存在该元素。
删除（
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
。
挑战点：
深层比较：对象可能包含嵌套的对象或数组，要判断内容是否相同，需要递归地比较它们的属性。属性顺序：
{a: 1, b: 2}
和
{b: 2, a: 1}
在语义上通常被认为是相同的，但
JSON.stringify
可能会因为属性顺序不同而生成不同的字符串。循环引用：对象内部可能互相引用，导致递归比较或
JSON.stringify
陷入无限循环。非可枚举属性/函数/Symbol：这些内容通常不参与哈希，或者需要特殊处理。性能：哈希函数需要足够快，否则会抵消哈希表的性能优势。
常见的（但有缺陷的）策略：
JSON.stringify(value)
：
优点：简单粗暴，对于只包含基本类型且无循环引用的“纯数据”对象非常有效。缺点：属性顺序问题：
{a:1, b:2}
和
{b:2, a:1}
会生成不同的字符串。循环引用：会抛出错误。函数/
undefined
/
Symbol
：这些属性会被忽略，导致哈希不准确。日期对象：会转为ISO字符串，但两个日期对象即使表示同一时间，如果不是同一个实例，也会被视为不同。示例：我在
MyHashSet
中就是用的这个，并加了
try-catch
。
手动拼接字符串并排序键：
思路：遍历对象的所有可枚举属性，将属性名和属性值拼接成一个字符串。为了解决属性顺序问题，可以先将所有属性名排序，再按顺序拼接。示例（简陋版，未处理嵌套）：
_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等问题。性能也可能不如预期。
使用一个计数器或
WeakMap
为每个对象生成唯一ID（仅适用于引用哈希）：
如果你的“哈希集合”实际上是想存储对象的引用，并且希望每个对象实例只出现一次（类似于
Set
对对象的处理方式），那么可以为每个新加入的对象生成一个内部ID，并用
WeakMap
来存储对象到ID的映射。这样，即使对象被垃圾回收，
WeakMap
也不会阻止。但这并不是基于“内容”的哈希。
最健壮的自定义哈希函数通常需要：
深度遍历：递归地处理嵌套对象和数组。循环引用检测：使用一个
Set
或
WeakSet
来跟踪已经访问过的对象，防止无限循环。类型处理：根据不同类型（基本类型、对象、数组、日期、正则等）采取不同的哈希策略。确定性：对于相同的输入，哈希函数必须始终产生相同的输出。均匀分布：哈希值应该尽可能均匀地分布在哈希空间中，以减少冲突。
在实际项目中，如果对复杂对象的哈希集合有高性能和高可靠性要求，我们通常不会自己从零开始写一个完美无缺的哈希函数。因为这真的太复杂了。我们会倾向于寻找社区中已经经过充分测试和优化的库。但如果只是为了理解原理或处理相对简单的对象，
JSON.stringify
（注意其局限性）或手动排序拼接的策略，可以作为入门级的实现。
所以你看，实现一个JS的哈希集合，特别是要处理复杂对象的“内容”唯一性，它不仅仅是写几行代码的事，更是一场关于如何权衡性能、准确性和实现复杂度的思考。
以上就是JS如何实现哈希集合？哈希冲突处理的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1515773.html
微信扫一扫 
支付宝扫一扫 
