JavaScript是否有集合数据结构的实现？

Question

我正在寻找一个良好的JavaScript集合数据结构的实现。它应该能够支持普通JavaScript对象作为元素。

目前我只找到了Closure Library的structs.Set，但我不喜欢它修改我的数据的事实。

- Tim Molendijk

---

请参见https://dev59.com/jWsz5IYBdhLWcg3wWmYy#14095368。 - hymloth

Answer 1

ECMAScript 6（即ES6）具有该功能

规范：http://www.ecma-international.org/ecma-262/6.0/#sec-set-constructor

用法：https://github.com/lukehoban/es6features#map--set--weakmap--weakset

示例：

var s = new Set()
s.add("hello").add("goodbye").add("hello")
s.size === 2
s.has("hello") === true

一个用于在不支持该功能的浏览器上实现它的模块：https://github.com/medikoo/es6-set

- Ciro Santilli OurBigBook.com

---

这在JS对象中不起作用。对象被保留为引用。具有相同属性值的对象将被视为两个对象并添加到Set中。 - Shanika Ediriweera

Answer 2

你可以在我的jshashtable提供的哈希表键值周围构建一个简单的包装器。我有一个闲置的实现，稍后会找出来。 更新 我已完成并测试了一个HashSet实现，并将其上传到GitHub上的jshashtable项目中。你可以下载它或查看源代码。

var s = new HashSet();
var o1 = {name: "One"}, o2 = {name: "Two"};
s.add(o1);
s.add(o2);
s.values(); // Array containing o1 and o2

- Tim Down

---

你能解释一下你的库是如何计算对象哈希值的吗？ - user187291

它在文档中有说明，但简而言之：哈希码是字符串，并且您可以提供一个计算哈希码的函数给Hashtable构造函数（以及一个比较两个对象并决定它们是否相等的函数）。否则，它会查找键上名为hashCode()的方法。作为最后的手段，它尝试使用toString()或String()将键转换为字符串。如果所有的键都散列到同一个值（例如"[object Object]"），因为您没有使用上述机制，则它们都将进入同一个桶中，并且必须使用简单的线性搜索。 - Tim Down

嗨，Tim，这个库会将以下格式存储在集合中吗：var o1 = {firstname: "John", lastname: "Doe"}, o2 = {firstname: "Eric", lastname: "Lencher}; - sam

Answer 3

在Javascript的ES6版本中，您可以使用内置类型set（检查您的浏览器兼容性）。请注意保留HTML标签。

var numbers = new Set([1, 2, 4]); // Set {1, 2, 4}

要向集合中添加元素，只需使用.add()，其运行时间为O(1)，如果元素不存在，则将其添加到集合中；如果已经存在，则不执行任何操作。您可以添加任何类型的元素（数组、字符串、数字）。

numbers.add(4); // Set {1, 2, 4}
numbers.add(6); // Set {1, 2, 4, 6}

要检查集合中元素的数量，您可以简单地使用.size。也能在O(1)时间内运行。

numbers.size; // 4

要从集合中删除元素，请使用.delete()。如果该值存在（并已删除），则它返回true，如果该值不存在，则返回false。同时在O(1)时间内运行。

numbers.delete(2); // true
numbers.delete(2); // false

要检查一个集合中是否存在某个元素，请使用.has()方法，如果元素在集合中则返回true，否则返回false。该方法的时间复杂度为O(1)。

numbers.has(3); // false
numbers.has(1); // true

除了您要求的方法外，还有几种额外的方法：

• numbers.clear(); 只会从集合中删除所有元素
• numbers.forEach(callback); 按插入顺序遍历集合中的值
• numbers.entries(); 创建一个包含所有值的迭代器
• numbers.keys(); 返回集合的键，与 numbers.values() 相同

此外，还有一种 Weakset ，它只允许添加对象类型的值。

- Salvador Dali

---

你确定 Set 的插入操作运行时间是 O(1) 吗？我找不到任何类似的实现方式，而且我找到的所有实现都具有 O(N) 的运行时间，并且这些实现都包含 indexOf 方法，用于检查数组中是否存在该值。由于需要在循环内使用，因此我不确定是否应该使用 indexOf 方法。你可以指点给我一些实现方式或者阅读资源吗？ - Vatsal

@Vatsal 是的，将元素插入到集合中的平摊时间为O(1)。我不知道在JS中如何实现集合，但是每本关于数据结构的基础书籍都会证实这一点 。IndexOf是一个操作数组的方法，因此它花费O(n)时间并不意外。 - Salvador Dali

Answer 4

我认为除了将对象的哈希码存储在对象本身中，没有其他方法可以处理对象的哈希码。严格来说，可以使用简单的线性搜索创建一个不需要哈希的集合类，但这几乎不是高效的。

- user187291

---

确实，除了将其与其他对象进行比较之外，JS中没有其他方法可以获取对象的标识。 - bobince

Answer 5

使用ECMAScript 2015 (ES6)标准 Set 数据结构，非常易于使用：

var mySet = new Set();

mySet.add(1);
mySet.add(5);
mySet.add("some text");
var o = {a: 1, b: 2};
mySet.add(o);

mySet.has(1); // true
mySet.has(3); // false, 3 has not been added to the set
mySet.has(5);              // true
mySet.has(Math.sqrt(25));  // true
mySet.has("Some Text".toLowerCase()); // true
mySet.has(o); // true

mySet.size; // 4

mySet.delete(5); // removes 5 from the set
mySet.has(5);    // false, 5 has been removed

mySet.size; // 3, we just removed one value

针对使用AngularJs的用户的更新

请注意，集合（sets）与ng-repeat不兼容。因此最好使用数组并应用唯一的过滤器。

- CommonSenseCode

Answer 6

我喜欢 Simple-JS-Set（可能是因为我写了它）。它支持任何类型的JavaScript对象。它有以下API：

• Set(hashFunction)：（构造函数）使用给定的hashFunction（默认为JSON.stringify）实例化一个新集合
• add(item)：向集合中添加一个项目
• remove(item)：从集合中删除一个项目
• contains(item)：返回项目是否包含在集合中
• size()：返回集合中唯一项目的数量
• each(function(item), thisObj)：在thisObj的上下文中，对集合中的每个项目执行一个函数

- Lukas