使用JavaScript对象的共享*测试深度相等*

Question

关于在JavaScript中测试两个对象以实现深度相等的主题,已经有很多墨水.但是,没有人关心区分以下两个对象:

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

大多数深度相等算法会说o1,o2并且o3是相同的.我想要一个算法,说明o1并且o2不相等,但是o1并且o3相等.换句话说,我想要一个算法,告诉我指针图是否具有相同的结构.我关心这个因为如果我对第一个元素进行了修改,则反映在第二个元素中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);
}