JavaScript中的对象集合

Question

我想在Javascript中拥有一组对象。也就是说，需要一个仅包含唯一对象的数据结构。

通常建议使用属性来实现，例如 myset["key"] = true。但是，我需要键是对象。我已经阅读过Javascript将属性名称转换为字符串，所以我猜测无法使用 myset[myobject] = true。

我可以使用数组，但我需要比O(n)更好的性能来添加、查找和删除项目。

它需要只通过引用来区分对象，因此假设有以下内容：

var a = {};
var b = {};

如果它们是独立的对象，那么a和b都应该可以相加。

基本上，我想要像C++的std::set一样的东西，可以存储Javascript对象。有什么想法吗？

- AshleysBrain

---

可能是JavaScript实现集合数据结构的重复问题。 - Ciro Santilli OurBigBook.com

Answer 1

ES6 提供了一种原生的 Set 数据结构：

let s = new Set();
let a = {};
let b = {};

s.add(a);

console.log(s.has(a));  // true
console.log(s.has(b));  // false

- Ry-

---

new Set([{one: "one"}, {one: "one"}]).size 的值为2。难道不应该是1吗？ - ndtreviv

不，它们不是同一个对象。{one: "one"} !== {one: "one"}。 - Ry-

没错，我最终使用了lodash的_.uniqWith和_.isEqual来获取唯一的对象。 - ndtreviv

谢谢@ndtreviv！我使用uniqueObjects = _.uniqWith(objects, _.isEqual)。 - joerick

Answer 2

这里有一个疯狂的建议...以JSON.stringify(object)的结果作为关键字

- Jim Blackler

---

这是我一直在想的，但我真的真的不想以这种方式做事 :/ - Charlie L

类型错误：循环对象值 - Pacerier

当对象属性的顺序不同时，会产生错误的负面结果。 - Artem Balianytsia

Answer 3

我回答了自己的问题，但我想到了一种有趣的替代解决方案，并认为分享出来会很有用。

cwolves的回答给了我一个思路。提供对象的toString()方法可以唯一标识实例，对象的属性可用于存储一组对象。基本上，要存储对象x，您可以使用items[x.toString()] = x;。请注意，值是对象本身，因此可以通过查看所有item的属性并将所有值转储到数组中来提取对象集合。

以下是完整的类，我称之为ObjectSet。它要求对象的toString()方法是唯一标识的，这对我的目的没有问题。add，remove和contains应该在O(n)时间内运行得比较好 - 无论JavaScript的属性访问效率是O(1)还是O(n log n)。

// Set of objects.  Requires a .toString() overload to distinguish objects.
var ObjectSet = function ()
{
    this.items = {};
    this.item_count = 0;
};

ObjectSet.prototype.contains = function (x)
{
    return this.items.hasOwnProperty(x.toString());
};

ObjectSet.prototype.add = function (x)
{
    if (!this.contains(x))
    {
        this.items[x.toString()] = x;
        this.item_count++;
    }

    return this;
};

ObjectSet.prototype.remove = function (x)
{
    if (this.contains(x))
    {
        delete this.items[x.toString()];
        this.item_count--;
    }

    return this;
};

ObjectSet.prototype.clear = function ()
{
    this.items = {};
    this.item_count = 0;

    return this;
};

ObjectSet.prototype.isEmpty = function ()
{
    return this.item_count === 0;
};

ObjectSet.prototype.count = function ()
{
    return this.item_count;
};

ObjectSet.prototype.values = function ()
{
    var i, ret = [];

    for (i in this.items)
    {
        if (this.items.hasOwnProperty(i))
            ret.push(this.items[i]);
    }

    return ret;
};

- AshleysBrain

Answer 4

并非所有对象都可以，但如果您的对象实现了.toString()方法，则可以：

var x = {toString: function(){ return 'foo'; }};
var y = {toString: function(){ return 'bar'; }};
var obj = {};
obj[x] = 'X';
obj[y] = 'Y';
console.log(obj);
// { foo: 'X', bar: 'Y' }

如果您想让这更加简化，可以将其变成一个类：

function myObj(name){
   this.name = name;
}
myObj.prototype.toString = function(){ return this.name; }

var obj = {};
obj[new myObj('foo')] = 'X';
obj[new myObj('bar')] = 'Y';

- user578895

---

所有对象都有一个继承自Object.prototype的toString方法。将对象分配给属性名称将调用其toString方法，因此无需明确执行此操作。您无法保证对象的toString对于所有对象都是唯一的，因此Sophistifunk的方法更好（即将对象存储在数组中并提供包装器以添加、检索和删除成员）。 - RobG

@RobG - 你没有理解我的意思。我添加toString()方法是为了让你能够返回当前对象的唯一哈希值。在这种情况下，我只返回'foo'和'bar'，但你可以轻松地哈希任何其他标识对象的内容（因此有了原型示例）。至于你的第一个声明，不...将toString()分配为属性将调用该函数，而不是从Object.prototype继承的函数。 - user578895

就我而言，var guid=0; myObj.prototype.toString = function(){ return (this.guid || (this.guid=guid++)); } 可以工作。 - user578895

@cwolves - 所有存储的对象都需要具有唯一的名称，因此最好自动化并将其保持私有。 - RobG

@RobG - 首先，我不同意每个编程概念都应该从一种语言转移到另一种语言的想法。我认为这是JS以不同的方式处理事情的一个例子。但是，如果要使用Set类，则仍应使用哈希，而不是像Sophistifunk的示例那样使用数组。设置obj.__index=guid或其他内容，并基于此进行哈希。 - user578895

Answer 5

我用了 Map，解决了我的问题。

const objectsMap = new Map();
const placesName = [
  { place: "here", name: "stuff" },
  { place: "there", name: "morestuff" },
  { place: "there", name: "morestuff" },
];
placesName.forEach((object) => {
  objectsMap.set(object.place, object);
});
console.log(objectsMap);

- ENcy

---

完美的解决方案。谢谢。 - Yehya

Answer 6

ECMAScript6 Set应该像这样表现：

• 标准文档： http://www.ecma-international.org/ecma-262/6.0/#sec-set-o-p-v-throw
• 非官方 ES6 速查表：https://github.com/lukehoban/es6features#map--set--weakmap--weakset

在 Firefox 32 上的示例代码（但在 Chromium 37 中未实现）：

if (Set) {
  var s = new Set()
  var a = {}
  var b = {}
  var c = {}
  s.add(a)
  s.add(b)
  s.add(b)
  assert(s.size === 2)
  assert(s.has(a))
  assert(s.has(b))
  assert(!s.has(c))
}

这并不奇怪，因为{} != {}:默认情况下等式比较对象地址。

该模块为不支持的浏览器实现了它：https://github.com/medikoo/es6-set

- Ciro Santilli OurBigBook.com

Answer 7

你想要做的事情（对象集合）在Javascript中没有原生实现。你需要自己实现。一种方法是为你的对象实现一个哈希函数。集合的后备数据类型将是一个关联数组，其中数组的键是从调用对象的哈希函数获得的值，数组的值是对象本身。

当然，这并没有解决你所提出的问题，所以你需要考虑相等性（也许实现一个相等函数）？

你可以将哈希函数作为对象本身的属性，也可以有一个独立的哈希函数，它以对象作为输入并生成哈希值（可能通过迭代其属性来完成）。

使用这种方法，您应该能够获得O(1)的插入、搜索和删除（不包括哈希函数的顺序，这不应该比O(n)更糟糕，特别是如果你正在迭代其属性来创建哈希值）。

- Vivin Paliath

Answer 8

Javascript中的Set不会进行深度对象比较。

使用lodash，以下是具有深度对象比较的唯一数组：

const objects = [{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }, { 'x': 1, 'y': 2 }];
 
_.uniqWith(objects, _.isEqual);

- Rui Marques

Answer 9

给定以下类型的数组：

Array<{ foo: T1, bar: T2 }>

你可以构建一个相应类型的字典：

{ [foo: T1]: Set<T2> }

查找 { foo: fooValue, bar: barValue } 的方法如下：

if (fooValue in dictionary && dictionary[fooValue].has(barValue))

这样我们就可以构建一个ObjectSet<T1, T2>。 如果现在有三个元素，你可以构建以下字典：

{ [foo: T1]: ObjectSet<T2, T3> }

通过归纳法将您的ObjectSet扩展到任意数量的属性。

这是假设您的类型可以用作索引签名。

- ghostinpeace

Answer 10

我刚刚打了这个，只进行了简单的测试：

var Set = function Set()
{
    var list = [];

    var contains;
    this.contains = contains = function(x) {
        return list.indexOf(x) >= 0;
    }

    var put;
    this.put = put = function(x) {
        if (!contains(x))
            list.push(x);

        return this;
    }

    var remove;
    this.remove = remove = function(x)
    {
        var idx = list.indexOf(x);
        if (idx >= 0)
            list.splice(idx,1);

        return this;
    }

    var all;
    this.all = all = function()
    {
        return list.concat();
    }

    return this;
}

- Sophistifunk

---

谢谢，但我相信indexOf的时间复杂度是O(n)。在问题中，我声明需要比那更好的效率。 - AshleysBrain

抱歉，我错过了帖子的那部分 :-/ 它基本上是一个自定义哈希函数。 - Sophistifunk