比较 JavaScript 中的循环（自引用）对象

Question

我比较包含值两个对象string，number，array和object。到此为止没有问题。当我尝试比较自引用对象时，出现以下错误RangeError: Maximum call stack size exceeded。如果自引用对象被其他对象的同一级别引用，则应认为它们是相等的。我的问题是如何实现它。这是我的代码：

const equalsComplex = function(value, other) {
  // Get the value type
  const type = Object.prototype.toString.call(value);

  // If the two objects are not the same type, return false
  if (type !== Object.prototype.toString.call(other)) return false;

  // If items are not an object or array, return false
  if (['[object Array]', '[object Object]'].indexOf(type) < 0) return false;

  // Compare the length of the length of the two items
  const valueLen =
    type === '[object Array]' ? value.length : Object.keys(value).length;
  const otherLen =
    type === '[object Array]' ? other.length : Object.keys(other).length;
  if (valueLen !== otherLen) return false;

  // Compare two items
  const compare = function(item1, item2) {
    // Get the object type
    const itemType = Object.prototype.toString.call(item1);

    // If an object or array, compare recursively
    if (['[object Array]', '[object Object]'].indexOf(itemType) >= 0) {
      if (!equalsComplex(item1, item2)) return false;
    }

    // Otherwise, do a simple comparison
    else {
      // If the two items are not the same type, return false
      if (itemType !== Object.prototype.toString.call(item2)) return false;

      // Else if it's a function, convert to a string and compare
      // Otherwise, just compare
      if (itemType === '[object Function]') {
        if (item1.toString() !== item2.toString()) return false;
      } else {
        if (item1 !== item2) return false;
      }
    }
  };

  // Compare properties
  if (type === '[object Array]') {
    for (let i = 0; i < valueLen; i++) {
      if (compare(value[i], other[i]) === false) return false;
    }
  } else {
    for (let key in value) {
      if (value.hasOwnProperty(key)) {
        if (compare(value[key], other[key]) === false) return false;
      }
    }
  }

  // If nothing failed, return true
  return true;
};
const r = { a: 1 };
r.b = r;
const d = { a: 1 };
d.b = d;

console.log(
  equalsComplex(
    {
      a: 2,
      b: '2',
      c: false,
      g: [
        { a: { j: undefined } },
        { a: 2, b: '2', c: false, g: [{ a: { j: undefined } }] },
        r
      ]
    },
    {
      a: 2,
      b: '2',
      c: false,
      g: [
        { a: { j: undefined } },
        { a: 2, b: '2', c: false, g: [{ a: { j: undefined } }] },
        r
      ]
    }
  )
);

Answer 1

在我们开始之前

您是否有理由不使用像deep-equal这样的现有库？有时使用已经为您编写的代码比自己编写更容易

现在修复代码中的一些简单问题

对于初学者来说，使用Object.prototype.toString来确定类型感觉就像一个黑客，如果不同的浏览器以toString不同的方式实现该方法，将来可能会有错误的风险。如果有人知道toStringECMAScript 规范中是否明确定义了该方法的返回值，请加入。否则，我会避免这种 hack，因为 JavaScript 提供了一个完美的替代方案：https : typeof //developer.mozilla.org/en-US /docs/Web/JavaScript/Reference/Operators/typeof

有趣typeof value的是，对象和数组都会返回相同的值，因为就 ECMAScript 而言，数组是对象的子类。因此，您以后对[Object object]和 的比较[Object Array]可以简化为仅检查类型object

一旦开始使用typeof value而不是Object.prototype.toString.apply(value)，您将需要一种方法来区分对象和数组以进行比较。为此，您可以使用Array.isArray

问题的关键

现在关于自我引用，你所指的问题是一个循环。一个简单的循环是：

var a = {};
a.foo = a;

这将创建循环： a.foo.foo.foo.foo.foo.... == a

有一个很好的方法来检查 JavaScript 中两个引用是否指向同一个对象，这有助于确定何时等于true，但在等于false的情况下无济于事。要检查两个引用是否指向同一个对象，只需使用==运算符！这将返回true指向内存中完全相同实例的对象。例如：

var a = {foo: "bar"}
var b = {foo: "bar"}
var c = a;

a == b; // false
a == c; // true
b == c; // false

因此，您可以通过检查来轻松查看两个引用是否相同 item1 == item2

但是当它们不相等时，您仍然会执行 a complexCompare，它将深入每个自引用，并且将具有相同的堆栈溢出。要解决此问题，您需要一种检测周期的方法。与深度平等一样，有一些库用于此，但出于智力原因，我们将看看是否可以重新创建它们。

为此，我们需要记住我们见过的所有其他对象，并在递归时与它们进行比较。一个简单的解决方案可能如下所示：

var objectsWeveSeen = [];

function decycle(obj) {
    for (var key in obj) {
        if (typeof obj[key] == "object") {
            for (var i = 0; i < objectsWeveSeen.length; i++) {
                if (objectsWeveSeen[i] == obj[key]) {
                    obj[key] = "CYCLE! -- originally seen at index " + i;
                }
            }
            objectsWeveSeen.push(obj[key]);
        }
    }
}

（注意：这个 decycle 函数是破坏性的。它修改了原始对象。另外，这个 decycle 函数不是递归的，所以它实际上很糟糕。但它至少给了你一个大致的想法，你可以尝试自己写，或者看看别人是怎么做的）

然后我们可以像这样传递一个对象给它：

var a = {foo: {}};
a.baz = a.foo;
console.log(decycle(a));
// Outputs: {foo: {}, baz: "CYCLE! -- originally seen at index 0"}

由于此对象缺少循环，您现在可以对其执行复杂的比较：

complexCompare(decycle(a));

当然，仍有一些边缘情况需要考虑。Date如果两个对象引用相同的时间但具有不同的时区，它们是否等效？是否null相等null？而且我的简单 decycle 算法无法解释对根对象的引用，它只记住它看到的所有键（尽管如果您考虑一下，这应该很容易添加）

一个不太完美但可行的解决方案

我没有写出完美的 deep-equals 实现有两个原因：

1. 我觉得写代码是最好的学习方式，而不是从别人那里复制粘贴
2. 我确定有些边缘情况我没有考虑（这就是你应该使用像 Lodash 这样经过实战测试的库而不是编写自己的代码的原因）并且承认这是一个不完整的解决方案而不是将其作为它不是什么，我们会鼓励您去找写了更完整答案的人

function complexCompare(value, other) {
    var objectsWeveSeen = [];
    function nonDestructiveDecycle(obj) {
        var newObj = {};
        for (var key in obj) {
            newObj[key] = obj[key];
            if (typeof obj[key] == "object") {
                for (var i = 0; i < objectsWeveSeen.length; i++) {
                    if (objectsWeveSeen[i] == obj[key]) {
                        newObj[key] = "CYCLE! -- originally seen at index " + i;
                        break;
                    }
                }
                objectsWeveSeen.push(obj[key]);
            }
        }
        return newObj;
    }

    var type = typeof value;
    if (type !== typeof other) return false;

    if (type !== "object") return value === other;

    if (Array.isArray(value)) {
        if (!Array.isArray(other)) return false;

        if (value.length !== other.length) return false;

        for (var i = 0; i < value.length; i++) {
            if (!complexCompare(value[i], other[i])) return false;
        }

        return true;
    }

    // TODO: Handle other "object" types, like Date

    // Now we're dealing with JavaScript Objects...
    var decycledValue = nonDestructiveDecycle(value);
    var decycleOther = nonDestructiveDecycle(other);

    for (var key in value) {
        if (!complexCompare(decycledValue[key], decycleOther[key])) return false;
    }

    return true;
}

更新

回应评论：

== 相对 ===

==在两个变量之间执行“松散”比较。例如，3 == "3"将返回true。===在两个变量之间执行“严格”比较。所以3 === "3"会返回false。在我们的例子中，你可以使用你喜欢的任何一个，结果应该没有区别，因为：

• typeof总是返回一个字符串。因此typeof x == typeof y完全相同typeof x === typeof y
• 如果在比较它们的值之前检查两个变量的类型是否相同，则永远不会遇到==和===返回不同结果的边缘情况之一。例如，0 == false但是typeof 0 != typeof false(0是一个“数字”，false是一个“布尔值”)

我坚持==我的例子，因为我觉得避免两者之间的任何混淆会更熟悉

[] 相对 Set

我看了一下 usingSet重写decycle，很快就遇到了一个问题。您可以使用Set，以检测是否存在是一个循环，但你不能平凡用它来检测两个周期是相同的。请注意，在我的decycle方法中，我用字符串替换了循环CYCLE! -- originally seen at index X。这个“在索引 X”的原因是因为它告诉你引用了哪个对象。我们不仅拥有“我们以前见过的某个对象”，还拥有“我们以前见过的那个对象”。现在，如果两个对象引用同一个对象，我们可以检测到（因为字符串将相等，具有相同的索引）。如果两个对象引用不同的对象，我们也会检测到（因为字符串不相等）

但是，我的解决方案存在问题。考虑以下：

var a = {};
a.foo = a;

var b = {};
b.foo = b;

var c = {};
c.foo = a;

在这种情况下，我的代码将要求a和c相等（因为它们都引用相同的对象），但a和b是不是（因为即使它们具有相同的价值观，同样的模式，同样的结构-它们引用不同的对象）

更好的解决方案可能是将“索引”（代表我们找到对象的顺序的数字）替换为“路径”（表示如何到达对象的字符串）

var objectsWeveSeen = []

function nonDestructiveRecursiveDecycle(obj, path) {
    var newObj = {};
    for (var key in obj) {
        var newPath = path + "." + key;
        newObj[key] = obj[key];
        if (typeof obj[key] == "object") {
            for (var i = 0; i < objectsWeveSeen.length; i++) {
                if (objectsWeveSeen[i].obj == obj[key]) {
                    newObj[key] = "$ref:" + objectsWeveSeen[i].path;
                    break;
                }
            }
            if (typeof newObj[key] != "string") {
                objectsWeveSeen.push({obj: obj[key], path: newPath});
                newObj[key] = nonDestructiveRecursiveDecycle(obj[key], newPath);
            }
        }
    }
    return newObj;
}

var decycledValue = nonDestructiveRecursiveDecycle(value, "@root");