如何为JavaScript Set自定义对象相等性

Question

ES 6（Harmony）引入了新的Set对象。Set使用的身份算法类似于===运算符，因此不太适合比较对象。

var set = new Set();
set.add({a:1});
set.add({a:1});
console.log([...set.values()]); // Array [ Object, Object ]

如何自定义Set对象的等式比较以进行深度对象比较？有没有类似于Java的equals（Object）的东西？

- czerny

---

“定制平等”是什么意思？JavaScript不允许操作符重载，因此无法对===操作符进行重载。ES6集合对象没有任何比较方法。.has()方法和.add()方法仅在它们是同一个实际对象或者原始值相同时起作用。 - jfriend00

“自定义相等性”指开发人员可以定义某些对象被认为是相等或不相等的任何方式。 - czerny

另外，https://dev59.com/b2kv5IYBdhLWcg3wghIi。 - Pacerier

这可能是“集合规范化”TC39提案的一部分。 (https://github.com/tc39/proposal-collection-normalization/issues/18) - Bergi

Answer 1

2022年3月更新

目前有一个提案，旨在将记录和元组（基本上是不可变的对象和数组）添加到JavaScript中。在该提案中，它提供了直接使用 === 或！== 进行记录和元组的比较，其中比较值而不仅仅是对象引用，并且与此答案相关的是， Set 和 Map 对象将使用记录或元组的值进行键比较/查找，这将解决此处所要求的内容。

由于记录和元组是不可变的（无法修改），并且因为它们可以轻松按值进行比较（通过它们的内容，而不仅仅是它们的对象引用），因此允许Maps和Sets使用对象内容作为键，并且拟议的规范明确命名了这个特性适用于Sets和Maps。

这个最初的问题要求自定义Set比较以支持深度对象比较。虽然这并没有提出Set比较的定制化，但如果您使用新的记录或元组而不是对象或数组，则直接支持深度对象比较，从而解决了这个最初的问题。

注意，该提案已于2021年中期进入第二阶段。最近一直在推进，但尚未完成。

Mozilla正在此处跟踪这个新提案的工作。

---

翻译后的内容：

ES6中的Set对象没有任何比较方法或自定义比较扩展。

.has()、.add()和.delete()方法只能在实际对象相同或原始值相同的情况下工作，没有一种方式可以插入或替换该逻辑。

您可以从Set派生自己的对象，并用首先执行深度对象比较的方法替换.has()、.add()和.delete()方法，以查找项目是否已经存在于Set中，但性能可能不好，因为底层的Set对象根本没有帮助。您可能需要通过自己的自定义比较对所有现有对象进行暴力迭代，以在调用原始.add()之前找到匹配项。

以下是关于ES6功能的这篇文章和讨论的一些信息:

5.2 为什么我不能配置映射和集合如何比较键和值？ 问题：如果有一种方法可以配置哪些映射键和哪些集合元素被视为相等，那就太好了。为什么没有这个功能？

答案：该功能已被推迟，因为实现起来既困难又低效。其中一个选项是向集合传递回调函数以指定相等性。

另一个选项，在Java中可用，是通过对象实现的方法（Java中的equals()）来指定相等性。然而，对于可变对象，这种方法存在问题：通常情况下，如果对象发生变化，它在集合内的“位置”也必须改变。但在Java中并非如此。JavaScript可能会采取更安全的路线，仅为特殊的不可变对象（所谓的值对象）启用按值比较。按值比较意味着如果两个值的内容相等，则认为它们相等。在JavaScript中，原始值是按值进行比较的。

- jfriend00

---

为什么不实现一个简单的GetHashCode或类似的方法？ - Jamby

@mpen 不对，我允许开发者为特定的类管理自己的哈希函数，这在几乎所有情况下都可以避免冲突问题，因为开发者知道对象的性质并可以派生出一个好的键。在任何其他情况下，回退到当前的比较方法。很多语言已经实现了这一点，只有 JavaScript 没有。 - Jamby

因为 JavaScript 程序员不了解哈希码，所以需要 @Jamby。 - Peter

JavaScript 程序员仍需跟进 Java。拜托各位，你们知道这些功能对程序员有多有用吗？如果你更改其中一个键，那可能意味着破坏契约，但这更多是文档问题，而不是不实现该功能的问题。现在我们被困在 20 种解决方案、40 种过时的方法和 20 个 JavaScript 程序员讨论最佳解决方案中。赶快实施吧。 - TimothyBrake

@Nearoo - 在这个答案中添加了有关Records and Tuples proposal的注释，该提案可以解决大部分在此处所要求的内容。它不提供集合比较的可定制性，但它允许直接比较记录或元组的内容，并允许它们成为Set或Map中的键（这将通过内容进行比较），这将解决最初在此问题中提出的问题。 - jfriend00

Answer 2

如jfriend00的回答所述，自定义等式关系可能不可行。

以下代码提供了计算效率高但占用内存较多的解决方法概述：

class GeneralSet {

    constructor() {
        this.map = new Map();
        this[Symbol.iterator] = this.values;
    }

    add(item) {
        this.map.set(item.toIdString(), item);
    }

    values() {
        return this.map.values();
    }

    delete(item) {
        return this.map.delete(item.toIdString());
    }

    // ...
}

每个插入的元素都必须实现toIdString()方法，返回字符串。当且仅当它们的toIdString方法返回相同的值时，两个对象才被认为是相等的。

- czerny

---

你也可以让构造函数接受一个比较元素相等性的函数作为参数，这样做非常好，因为这样的话相等性就成了集合的特性，而不仅仅是用于其中的对象的特性。 - Ben J

生成一个字符串并将其放入Map中的目的在于，这样你的JavaScript引擎会使用本地代码进行~O(1)搜索来查找对象的哈希值，而接受相等性函数则会强制进行线性扫描集合并检查每个元素。 - Jamby

使用这种方法的一个挑战是它假设item.toIdString()的值不变且无法更改。如果可以更改，那么GeneralSet很容易就会出现“重复”项而失效。因此，这样的解决方案可能只适用于某些特定情况，例如在使用集合时对象本身不会更改，或者无效的集合并不重要。所有这些问题可能进一步解释了为什么ES6 Set没有公开此功能，因为它只适用于特定情况。 - jfriend00

这个答案的问题在于（从外观上看）item.toIdString()计算id字符串时独立于将其插入到其中的GeneralSet实例的内容。这排除了哈希函数的可能性，因此验证了您关于“内存昂贵”的说法。将GeneralSet作为参数传递- item.toIdString(gs:GeneralSet)可以使用哈希。实际上，在“一般”情况下这是唯一的方法（由于内存限制），尽管管理哈希显然需要更多的工作。 - Craig Hicks

实际上，我撤回了必须检查一般集合是否存在冲突的说法。通过适当的toIdString()字符串函数和适当的哈希函数hashOfIdString()，冲突的机会足够低，可以忽略不计。而且内存使用率很低 - 使您关于“内存昂贵”的说法是不正确的。 - Craig Hicks

这是一个翻译的示例文本。请注意，这只是一个示例，并不代表实际的翻译结果。 - Erik Aronesty

Answer 3

如排名第一的回答所提到的，对于可变对象来说自定义相等性是有问题的。好消息是（我很惊讶没有人提到过）有一个非常流行的库叫做immutable-js，它提供了一组丰富的不可变类型，这些类型提供了您正在寻找的深度值相等语义。

以下是使用immutable-js的示例：

const { Map, Set } = require('immutable');
var set = new Set();
set = set.add(Map({a:1}));
set = set.add(Map({a:1}));
console.log([...set.values()]); // [Map {"a" => 1}]

- Russell Davis

---

immutable-js的Set/Map在性能上与原生的Set/Map相比如何？ - frankster

似乎对于相同的列表值，仍然不等于Map键。 - SolaWing

Answer 4

也许你可以尝试使用 JSON.stringify() 来进行深层对象比较。

例如：

const arr = [
  {name:'a', value:10},
  {name:'a', value:20},
  {name:'a', value:20},
  {name:'b', value:30},
  {name:'b', value:40},
  {name:'b', value:40}
];

const names = new Set();
const result = arr.filter(
  item => !names.has(JSON.stringify(item)) 
    ? names.add(JSON.stringify(item)) 
    : false
);

console.log(result);

- GuaHsu

---

这是可行的，但不一定要这样做，因为JSON.stringify({a:1,b:2}) !== JSON.stringify({b:2,a:1})。如果所有对象都是按照你的程序中同样的顺序创建的，那么就是安全的。但总的来说，这不是一个真正安全的解决方案。 - relief.melone

没错，“将其转换为字符串”是JavaScript万能的解决方案。 - Timmmm

Answer 5

为了补充这里的答案，我实现了一个Map包装器，它接受自定义哈希函数、自定义相等函数，并将具有等效（自定义）哈希的不同值存储在桶中。

可预见的是，它比czerny的字符串连接方法慢。

完整源代码在此处：https://github.com/makoConstruct/ValueMap。

- mako

---

“字符串连接”？这个方法更像是“字符串代理”（如果你要给它起个名字的话）？还是你使用“连接”这个词有什么原因？我很好奇;-) - binki

@binki 这是一个很好的问题，我认为答案提出了一个很好的观点，这需要我一段时间才能理解。通常，在计算哈希码时，人们会使用类似于HashCodeBuilder的方法，该方法将各个字段的哈希码相乘，并不能保证唯一性（因此需要自定义相等函数）。然而，在生成ID字符串时，您将连接各个字段的ID字符串，这是保证唯一性的（因此不需要相等函数）。 - Pace

如果您定义了一个形如 { x: number, y: number } 的 Point，那么它的 id string 可能是 x.toString() + ',' + y.toString()。 - Pace

让你的相等比较构建一些值，这些值只有在应该被视为不相等时才保证变化，这是我以前使用过的一种策略。有时候用这种方式思考问题更容易。在这种情况下，你生成的是“键”，而不是“哈希值”。只要你有一个键派生器，它以现有工具支持的值式相等形式输出键，几乎总是以String的形式结束，那么你就可以跳过整个哈希和桶步骤，如你所说，直接使用Map或甚至是旧式普通对象来处理派生键。 - binki

如果您在密钥派生器的实现中实际使用字符串连接，请注意一件事情，即如果允许字符串属性采用任何值，则可能需要特殊处理它们。例如，如果您有{x：'1,2'，y：'3'}和{x：'1'，y：'2,3'}，则String（x）+''+ String（y）将为两个对象输出相同的值。更安全的选择是利用其字符串转义并使用JSON.stringify（[x，y]），假设您可以依赖于JSON.stringify()是确定性的。 - binki

很好！你的映射比czerny的方法更加普适，所以即使速度慢也没问题。奇怪的是，你把哈希本身用作键，这使得你的桶几乎总是只有一个元素。你的基准测试比较了两个语义上不同的事物，因为你的moahash不是单射的，即不能用作toIdString。 - maaartinus

Answer 6

直接比较它们似乎不可能，但如果键只是排序了，JSON.stringify就能够起作用。正如我在评论中指出的那样：

JSON.stringify({a:1, b:2}) !== JSON.stringify({b:2, a:1});

但是我们可以使用自定义的stringify方法来解决这个问题。首先，我们编写该方法：

自定义Stringify

Object.prototype.stringifySorted = function(){
    let oldObj = this;
    let obj = (oldObj.length || oldObj.length === 0) ? [] : {};
    for (let key of Object.keys(this).sort((a, b) => a.localeCompare(b))) {
        let type = typeof (oldObj[key])
        if (type === 'object') {
            obj[key] = oldObj[key].stringifySorted();
        } else {
            obj[key] = oldObj[key];
        }
    }
    return JSON.stringify(obj);
}

集合

现在我们使用了一个集合。但是我们使用的是字符串集合而不是对象集合。

let set = new Set()
set.add({a:1, b:2}.stringifySorted());

set.has({b:2, a:1}.stringifySorted());
// returns true

获取所有值

在我们创建集合并添加值之后，可以通过以下方式获取所有值：

let iterator = set.values();
let done = false;
while (!done) {
  let val = iterator.next();

  if (!done) {
    console.log(val.value);
  }
  done = val.done;
}

这是一个包含所有内容的链接文件： http://tpcg.io/FnJg2i

- relief.melone

---

如果键已排序，这是一个很大的假设，特别是对于复杂对象。 - Alexander Mills

这正是我选择这种方法的原因 ;) - relief.melone

请注意，JSON.stringify() 在表示通用对象时存在各种挑战，超出了仅仅是键顺序的问题。它仅支持基本类型，而不支持像 Set、Map、Symbol 或 Class 实例之类的东西。它也无法处理循环引用，例如父级引用其子级，而子级又引用其父级的情况。 - jfriend00

Answer 7

对于Typescript用户，其他人（尤其是czerny）的答案可以概括为一个漂亮的类型安全和可重用的基类：

/**
 * Map that stringifies the key objects in order to leverage
 * the javascript native Map and preserve key uniqueness.
 */
abstract class StringifyingMap<K, V> {
    private map = new Map<string, V>();
    private keyMap = new Map<string, K>();

    has(key: K): boolean {
        let keyString = this.stringifyKey(key);
        return this.map.has(keyString);
    }
    get(key: K): V {
        let keyString = this.stringifyKey(key);
        return this.map.get(keyString);
    }
    set(key: K, value: V): StringifyingMap<K, V> {
        let keyString = this.stringifyKey(key);
        this.map.set(keyString, value);
        this.keyMap.set(keyString, key);
        return this;
    }

    /**
     * Puts new key/value if key is absent.
     * @param key key
     * @param defaultValue default value factory
     */
    putIfAbsent(key: K, defaultValue: () => V): boolean {
        if (!this.has(key)) {
            let value = defaultValue();
            this.set(key, value);
            return true;
        }
        return false;
    }

    keys(): IterableIterator<K> {
        return this.keyMap.values();
    }

    keyList(): K[] {
        return [...this.keys()];
    }

    delete(key: K): boolean {
        let keyString = this.stringifyKey(key);
        let flag = this.map.delete(keyString);
        this.keyMap.delete(keyString);
        return flag;
    }

    clear(): void {
        this.map.clear();
        this.keyMap.clear();
    }

    size(): number {
        return this.map.size;
    }

    /**
     * Turns the `key` object to a primitive `string` for the underlying `Map`
     * @param key key to be stringified
     */
    protected abstract stringifyKey(key: K): string;
}

示例实现非常简单：只需覆盖 stringifyKey 方法。在我的情况下，我将一些 uri 属性字符串化。

class MyMap extends StringifyingMap<MyKey, MyValue> {
    protected stringifyKey(key: MyKey): string {
        return key.uri.toString();
    }
}

然后，使用示例就像这是一个常规的 Map<K, V> 一样。

const key1 = new MyKey(1);
const value1 = new MyValue(1);
const value2 = new MyValue(2);

const myMap = new MyMap();
myMap.set(key1, value1);
myMap.set(key1, value2); // native Map would put another key/value pair

myMap.size(); // returns 1, not 2

- Jan Dolejsi

Answer 8

对于一种特殊但频繁出现的情况，即使用TypedArray作为Set/Map键的良好字符串化方法是使用

const key = String.fromCharCode(...new Uint16Array(myArray.buffer));

它生成了一个可以轻松转换回来的最短可能的唯一字符串。然而，对于低代理项和高代理项，这并不总是一个有效的UTF-16字符串。Set和Map似乎忽略代理项的有效性。 在Firefox和Chrome中测量，扩展运算符的执行速度较慢。如果你的myArray大小固定，那么当你写成以下形式时，它会执行得更快：

const a = new Uint16Array(myArray.buffer);  // here: myArray = Uint32Array(2) = 8 bytes
const key = String.fromCharCode(a[0],a[1],a[2],a[3]);  // 8 bytes too

可能是这种密钥生成方法最有价值的优点：它适用于Float32Array和Float64Array，没有任何舍入副作用。请注意，+0和-0是不同的。无穷大是相同的。静默NaN是相同的。信号NaN取决于其信号而不同（在原始JavaScript中从未见过）。

- Henrik Haftmann

Answer 9

就像其他人说的那样，目前还没有本地方法可以做到这一点。 但是，如果您想使用自定义比较器区分数组，可以尝试使用reduce方法。

function distinct(array, equal) {
  // No need to convert it to a Set object since it may give you a wrong signal that the set can work with your objects.
  return array.reduce((p, c) => {
    p.findIndex((element) => equal(element, c)) > -1 || p.push(c);
    return p;
  }, []);
}

// You can call this method like below,
const users = distinct(
    [
      {id: 1, name: "kevin"},
      {id: 2, name: "sean"},
      {id: 1, name: "jerry"}
    ],
    (a, b) => a.id === b.id
);
...

- 张焱伟

Answer 10

正如其他人所说，目前的Set版本无法实现此功能。

我的建议是使用数组和映射的组合来完成。

下面的代码片段将创建一个基于您自己定义的键的唯一键映射，然后将该唯一项映射转换为数组。

const array =
  [
    { "name": "Joe", "age": 17 },
    { "name": "Bob", "age": 17 },
    { "name": "Carl", "age": 35 }
  ]

const key = 'age';

const arrayUniqueByKey = [...new Map(array.map(item =>
  [item[key], item])).values()];

console.log(arrayUniqueByKey);

   /*OUTPUT
       [
        { "name": "Bob", "age": 17 },
        { "name": "Carl", "age": 35 }
       ]
   */

 // Note: this will pick the last duplicated item in the list.

- breno silva