javascript - 通过 JavaScript 对象的共享来测试深度相等性

Question

在 JavaScript 中测试两个对象的深度相等性这个主题上已经有很多笔墨。然而，似乎没有人关心区分以下两个对象:

var o1 = [{},{}];
var subitem = {};
var o2 = [subitem, subitem];
var o3 = [{}, {}];

大多数深度相等算法会说 o1、o2 和 o3 相等。我想要一个算法表明 o1 和 o2 不相等，但 o1 和 o3 相等。换句话说，我想要一个算法来告诉我指针 graphs 是否具有相同的结构。我关心这一点，因为如果我对第一个元素的修改反射(reflect)在 o2 中的第二个元素中，而不是在 o1 中。

这意味着循环结构的深度相等应该起作用:

var o1 = [];
o1.push(o1);
var o2 = [];
o2.push(o2);
// deepGraphEqual(o1, o2) == true
var o3 = [[]];
o3[0].push(o3);
// deepGraphEqual(o1, o3) == false

如果您要避免改变项目，您可能需要 ECMAScript6 映射，所以我会接受使用这些的解决方案。

Answer 1

没有 ES6 功能的以二次时间运行的版本:

function deepGraphEqual(a, b) {
    var left = [], right = [], has = Object.prototype.hasOwnProperty;
    function visit(a, b) {
        var i, k;
        if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null)
            return a === b;
        if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b))
            return false;
        for (i = 0; i < left.length; i++) {
            if (a === left[i])
                return b === right[i];
            if (b === right[i])
                return a === left[i];
        }
        for (k in a)
            if (has.call(a, k) && !has.call(b, k))
                return false;
        for (k in b)
            if (has.call(b, k) && !has.call(a, k))
                return false;
        left.push(a);
        right.push(b);
        for (k in a)
            if (has.call(a, k) && !visit(a[k], b[k]))
                return false;
        return true;
    }
    return visit(a, b);
}

以线性时间运行的带有 ES6 Map 的版本:

function deepGraphEqual(a, b) {
    let left = new Map(), right = new Map(), has = Object.prototype.hasOwnProperty;
    function visit(a, b) {
        if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null)
            return a === b;
        if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b))
            return false;
        if (left.has(a))
            return left.get(a) === b
        if (right.has(b))
            return right.get(b) === a
        for (let k in a)
            if (has.call(a, k) && !has.call(b, k))
                return false;
        for (let k in b)
            if (has.call(b, k) && !has.call(a, k))
                return false;
        left.set(a, b);
        right.set(b, a);
        for (let k in a)
            if (has.call(a, k) && !visit(a[k], b[k]))
                return false;
        return true;
    }
    return visit(a, b);
}