JavaScript - 深度相等比较

Question

问题（来自《JavaScript编程精解》第2版第4章练习4）：

编写一个名为deepEqual的函数，该函数接受两个值，并仅在它们是相同值或具有相同属性且这些属性的值与对deepEqual的递归调用进行比较时也相等的对象时返回true。

测试用例：

var obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}));
// → true

我的代码：

var deepEqual = function (x, y) {
  if ((typeof x == "object" && x != null) && (typeof y == "object" && y != null)) {
    if (Object.keys(x).length != Object.keys(y).length)
      return false;
    for (var prop in x) {
      if (y.hasOwnProperty(prop))
        return deepEqual(x[prop], y[prop]);
    /*This is most likely where my error is. The question states that all the values
    should be checked via recursion; however, with the current setup, only the first
    set of properties will be checked. It passes the test cases, but I would like
    to solve the problem correctly!*/
      }
    }
  else if (x !== y)
    return false;
  else
    return true;
}

我觉得我大致明白了；但是，正如我在评论中所说的那样，程序将不会检查对象中的第二个属性。我感觉存在结构/逻辑问题，并且仅仅是以错误的方式使用递归，因为我最初的想法是循环遍历属性，使用递归来比较第一个属性的值，然后继续在循环中进行下一个属性的比较。虽然，我不确定是否可能实现？

我已经仔细考虑过并尝试了几种不同的方法，但这是迄今为止我得出的最正确的答案。有任何可能的提示可以指引我朝着正确的方向吗？

- Gavin Feriancek

Answer 1

正如你所怀疑的那样，你正在返回第一个属性匹配的结果。如果该属性不匹配，你应该返回false，但继续查找其他属性。

此外，如果在y上没有找到prop属性（即计数匹配但实际属性不匹配），则返回false。

如果所有属性都匹配，则返回true：

var deepEqual = function (x, y) {
  if (x === y) {
    return true;
  }
  else if ((typeof x == "object" && x != null) && (typeof y == "object" && y != null)) {
    if (Object.keys(x).length != Object.keys(y).length)
      return false;

    for (var prop in x) {
      if (y.hasOwnProperty(prop))
      {  
        if (! deepEqual(x[prop], y[prop]))
          return false;
      }
      else
        return false;
    }
    
    return true;
  }
  else 
    return false;
}

var deepEqual = function (x, y) {
  if (x === y) {
    return true;
  }
  else if ((typeof x == "object" && x != null) && (typeof y == "object" && y != null)) {
    if (Object.keys(x).length != Object.keys(y).length)
      return false;

    for (var prop in x) {
      if (y.hasOwnProperty(prop))
      {  
        if (! deepEqual(x[prop], y[prop]))
          return false;
      }
      else
        return false;
    }

    return true;
  }
  else 
    return false;
}

var obj = {here: {is: "an", other: "3"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an", other: "2"}, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2}));
// → true

- Paul Roub

---

最好对“x”的属性进行.hasOwnProperty()检查，或者更好的是使用已经通过调用Object.keys()获得的返回值来进行迭代，因为这些返回值已经被限制为“自有”属性。 - Pointy

非常感谢！我对递归还很陌生，但是你的修改为这个主题提供了很好的教训。我有一个想法，为什么我的代码不起作用，而你的解决方案很直接明了。再次感谢，并享受这个赞吧！ - Gavin Feriancek

为什么不在函数顶部加上 if(x === y) 呢？这样，如果返回 true，就可以避免通过第一个大的 if 块。 - JamesWillett

绝对值得一试（并进行分析，以查看它是否真的有所不同）。在这种情况下，我试图尽可能接近问题的结构，以使差异清晰明了。 - Paul Roub

@kharish 对象比较处理了这个问题。将数组视为一个键为 0, 1, 2... 的对象。for... in 循环遍历这些“键”并比较值（在本例中是数组中的整数）。没有必要 - 也没有明智的方法 - 以不同的方式处理数组。示例：https://codepen.io/paulroub/pen/NWxvprK?editors=0011 - Paul Roub

Answer 2

感觉这个版本更易读（更容易理解），虽然逻辑与前面的答案非常相似。（这次是ES6）

function deepEqual(obj1, obj2) {

    if(obj1 === obj2) // it's just the same object. No need to compare.
        return true;

    if(isPrimitive(obj1) && isPrimitive(obj2)) // compare primitives
        return obj1 === obj2;

    if(Object.keys(obj1).length !== Object.keys(obj2).length)
        return false;

    // compare objects with same number of keys
    for(let key in obj1)
    {
        if(!(key in obj2)) return false; //other object doesn't have this prop
        if(!deepEqual(obj1[key], obj2[key])) return false;
    }

    return true;
}

//check if value is primitive
function isPrimitive(obj)
{
    return (obj !== Object(obj));
}

顺便提一下，有一个欺骗版本的深度相等函数，它的效果非常好)) 然而，它大约慢了 1.6 倍。

正如 zero298 注意到的那样，这种方法对属性的顺序敏感，不应被认真对待。

function cheatDeepEqual(obj1, obj2)
{
    return JSON.stringify(obj1) === JSON.stringify(obj2);
}

- Daniil Andreyevich Baunov

---

如果属性顺序不同，我认为“作弊者”版本可能会失败。考虑在node.js中测试的以下示例：JSON.stringify（{foo：“bar”，fizz：“buzz”}）=== JSON.stringify（{fizz：“buzz”，foo：“bar”}）;是错误的；但是JSON.stringify（{foo：“bar”，fizz：“buzz”}）=== JSON.stringify（{foo：“bar”，fizz：“buzz”}）;是正确的。 - zero298

@zero298，是的，我想你说得对。无论如何，这种方法不应该被过分认真对待 :) - Daniil Andreyevich Baunov

另外，当您使用JSON.stringify进行转换并使用parse进行转换时，如果存在任何日期对象，它将被转换为字符串类型。顺便提一下。 - Harish Krishnan

Object.keys 需要进行 null 检查 - Wildhammer

对于 deepEqual([],{}) 的测试失败。 - hannad rehman

Answer 3

虽然我对JS还不是很熟悉，但这是我解决问题的方法：

function deepEqual(obj1, obj2) {
if (typeof obj1 === "object" && typeof obj2 === "object") {
    let isObjectMatch = false;
    for (let property1 in obj1) {
        let isPropertyMatch = false;
        for (let property2 in obj2) {
            if (property1 === property2) {
                isPropertyMatch = deepEqual(obj1[property1], obj2[property2])
            }

            if(isPropertyMatch){
                break;
            }
        }

        isObjectMatch  = isPropertyMatch;

        if (!isObjectMatch) {
            break;
        }
    }

    return isObjectMatch;
} else {
    return obj1 === obj2;
}
}

以下是我的测试：

var obj = {here: {is: "an"}, object: 2};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2}))
// → true
console.log(deepEqual(obj, {object: 2, here: {is: "an"}}));
// → true
console.log(deepEqual(obj, {object: 1, here: {is: "an"}}));
// → false
console.log(deepEqual(obj, {objectt: 2, here: {is: "an"}}));
// → false
console.log(deepEqual(2, 2));
// → true
console.log(deepEqual(2, 3));
// → false
console.log(deepEqual(2, null));
// → false
console.log(deepEqual(null, null));
// → false
console.log(deepEqual(obj, null));
// → false

- Teodor Dimitrov

Answer 4

你可以在for循环外部使用一个变量来跟踪比较：

var allPropertiesEqual = true;
for (var prop in x) {
    if (y.hasOwnProperty(prop)) {
        allPropertiesEqual = deepEqual(x[prop], y[prop]) && allPropertiesEqual;
    } else {
        allPropertiesEqual = false;
    }
}
return allPropertiesEqual;

上述示例故意未进行优化。由于您正在比较对象，因此一旦找到不相等的内容，您可以立即返回false，并且可以在所有先前检查的属性相等的情况下继续循环：

for (var prop in x) {
    if (y.hasOwnProperty(prop)) {
        if (! deepEqual(x[prop], y[prop]) )
            return false; //first inequality found, return false
    } else {
        return false; //different properties, so inequality, so return false
    }
}
return true;

- Volune

---

这将返回 true，因为对比 { c: 3, d: 4 } 时 hasOwnProperty() 总是为 false，所有测试都将被跳过。 - Paul Roub

谢谢你的回答！我希望我能给你们两个都一个绿色的勾选，因为你们都有很好、详细的答案。:( 不过我还是给了你一个赞！ - Gavin Feriancek

Answer 5

基于Paul Roub所接受的答案，我需要它也匹配函数值，并且我希望它更加简洁明了，因此我进行了重构。

function deepEqual(x, y, z) {
  return x === y || typeof x == "function" && y && x.toString() == y.toString()
    || x && y && typeof x == "object" && x.constructor == y.constructor
    && (z = Object.keys(y)) && z.length == Object.keys(x).length
    && !z.find(v => !deepEqual(x[v], y[v]));
}

var myFunc = (x) => { return x*2; }
var obj = {here: {is: "an", other: "3"}, object: 2, andFunc: myFunc};
console.log(deepEqual(obj, obj));
// → true
console.log(deepEqual(obj, {here: 1, object: 2, andFunc: myFunc}));
// → false
console.log(deepEqual(obj, {here: {is: "an"}, object: 2, andFunc: myFunc}));
// → false
console.log(deepEqual(obj, {here: {is: "an", other: "2"}, object: 2, andFunc: myFunc}));
// → false
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2, andFunc: myFunc}));
// → true
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2, andFunc: (x) => { return x*2; }}));
// → true
console.log(deepEqual(obj, {here: {is: "an", other: "3"}, object: 2, andFunc: (x) => { return x*999; }}));
// → false

注：

• 你只需要传入2个参数：x和y（z是内部使用的）。
• 如果其中一个变量为null或undefined，它将返回该值而不是false，但该结果仍然是“falsey”，所以我可以接受。要解决这个问题，你可以将所有出现y &&的地方改为(y || !1) &&，将x &&改为(x || !1) &&
• 如果你确定对象中不会提供函数/回调，则删除|| typeof x == "function" && y && x.toString() == y.toString()

- braks

---

基于函数的输出结果进行比较是错误的。请尝试如下代码：const plus = x => y => x + y; deepEqual(plus(1), plus(2)) - Eli Barzilay

Answer 6

虽然这种方式更冗长，但也许更易于阅读：

function deepEqual(elem1, elem2) {
    if(elem1 === elem2) {
        return true;
    }
    if(typeof elem1 == 'object' && typeof elem2 == 'object' && elem1 != null && elem2 != null) {
      if(Object.keys(elem1).length == Object.keys(elem2).length) {
          for(let key of Object.keys(elem1)) {
              if(elem2.hasOwnProperty(key) != true) {
                  return false;
              }
          }
          for(let key of Object.keys(elem1)) {
              if(typeof elem1[key] == 'object' && typeof elem2[key] == 'object' && typeof elem1[key] != null && typeof elem2[key] != null) {
                  return deepEqual(elem1[key], elem2[key]);
              }
              else {
                if(elem1[key] !== elem2[key]) {
                    return false;
                }
              }
          } else {
            return false;
          }
        }
      }
    else {
        return false;
    }
    return true;
  }

- Vlad Moisuc

Answer 7

之前所有的回答都含有微小的错误，这些错误会导致在某些情况下失败。它们要么 1) 依赖于属性以相同的顺序排列，要么 2) 在某些情况下返回不对称的结果，因此 deepEqual(a, b) !== deepEqual(b, a)。以下是一个改进的答案，假设以下内容：

• 我们对 相同值相等性 感兴趣；我们希望 deepEqual(NaN, NaN) 返回 true，但 deepEqual(0, -0) 返回 false。
• 我们只关心直接在对象上定义的可枚举的字符串键属性（即由 Object.keys() 返回的那些属性）。
• 不需要完全支持循环引用。

/**
 * Tests whether two values are deeply equal using same-value equality.
 *
 * Two values are considered deeply equal iff 1) they are the same value, or
 * 2) they are both non-callable objects whose own, enumerable, string-keyed
 * properties are deeply equal.
 *
 * Caution: This function does not fully support circular references. Use this
 * function only if you are sure that at least one of the arguments has no
 * circular references.
 */
function deepEqual(x, y) {
    // If either x or y is not an object, then they are deeply equal iff they
    // are the same value. For our purposes, objects exclude functions,
    // primitive values, null, and undefined.
    if (typeof x !== "object" || x === null ||
        typeof y !== "object" || y === null) {
        // We use Object.is() to check for same-value equality. To check for
        // strict equality, we would use x === y instead.
        return Object.is(x, y);
    }

    // Shortcut, in case x and y are the same object. Every object is
    // deeply equal to itself.
    if (x === y)
        return true;

    // Obtain the own, enumerable, string-keyed properties of x. We ignore
    // properties defined along x's prototype chain, non-enumerable properties,
    // and properties whose keys are symbols.
    const keys = Object.keys(x);
    // If x and y have a different number of properties, then they are not
    // deeply equal.
    if (Object.keys(y).length !== keys.length)
        return false;

    // For each own, enumerable, string property key of x:
    for (const key of keys) {
        // If key is not also an own enumerable property of y, or if x[key] and
        // y[key] are not themselves deeply equal, then x and y are not deeply
        // equal. Note that we don't just call y.propertyIsEnumerable(),
        // because y might not have such a method (for example, if it was
        // created using Object.create(null)), or it might not be the same
        // method that exists on Object.prototype.
        if (!Object.prototype.propertyIsEnumerable.call(y, key) ||
            !deepEqual(x[key], y[key])) {
            return false;
        }
    }

    // x and y have the same properties, and all of those properties are deeply
    // equal, so x and y are deeply equal.
    return true;
}

- McMath

---

对于 deepEqual([],{}) 的测试失败。 - hannad rehman

@hannadrehman 它对 deepEqual([], {}) 返回 true，这是根据文档注释正确的：它们都是没有可调用属性、零个自有、可枚举、字符串键的对象。但对于许多应用程序（例如比较 JSON 结构），您可能希望区分空对象和空数组，在这种情况下，您需要确保两个参数都是数组或非数组对象。但是，并没有适用于所有应用程序的 deepEqual() 函数，因为如何定义深度相等取决于用例。 - McMath

我并不确定那是否正确。扩展到我的问题，deepEqual({x:[]},{x:{}}) 不应该相等。但根据这个函数，它是相等的。@McMath - hannad rehman

@hannadrehman deepEqual({x:[]},{x:{}}) 根据文档注释中的定义，正确返回true，该定义根本不区分数组和普通对象。甚至有更奇怪的例子：deepEqual([10], {0: 10}) 返回true；deepEqual(new Set(), new Date())也是如此。问题在于，这种深度相等的定义在您的用例（以及大多数用例）中都没有意义。没有一种深度相等的定义适用于每个应用程序。我会在我的答案中添加这个警告。 - McMath

这很有趣。我们需要遵循一些标准，否则可能会导致不必要的错误。我检查了节点assert模块如何处理此情况https://nodejs.org/api/assert.html#assertdeepequalactual-expected-message。它在那里被正确处理。使用`assert.deepEqual()`时，所有情况都给出了预期结果。 - hannad rehman

@hannadrehman 是的，Node的实现具有严格的类型检查并完全支持循环引用；它还超过500行代码。如果你只需要区分数组和普通对象，这里是一个修改版的函数，可能适合你。 - McMath

Answer 8

A simple one:
const isObject = (obj) => {
  return typeof obj === "object" && obj !== null;
};

let isEqual = true;
const deepEqual = (objA, objB) => {
  if (!isEqual) {
    return;
  }
  const keysA = Object.keys(objA);
  const keysB = Object.keys(objB);

  if (keysA.length !== keysB.length) {
    isEqual = false;
  }

  for (let i = 0; i < keysA.length; i++) {
    const valA = objA[keysA[i]];
    const valB = objB[keysA[i]];

    if (isObject(valA) && isObject(valB)) {
      deepEqual(valA, valB);
    } else if (valA !== valB) {
      isEqual = false;
    }
  }

  return isEqual;
};

- Nitin Rawat

---

虽然这段代码可能回答了问题，但是提供关于为什么和/或如何回答问题的额外上下文可以提高其长期价值。 - blazej

Answer 9

<script>
var cmp = function(element, target){

   if(typeof element !== typeof target)
   {
      return false;
   }
   else if(typeof element === "object" && (!target || !element))
   {
      return target === element;
   }
   else if(typeof element === "object")
   {
       var keys_element = Object.keys(element);
       var keys_target  = Object.keys(target);
       
       if(keys_element.length !== keys_target.length)
       {
           return false;
       }
       else
       {
           for(var i = 0; i < keys_element.length; i++)
           {
                if(keys_element[i] !== keys_target[i])
                    return false;
                if(!cmp(element[keys_element[i]], target[keys_target[i]]))
                    return false;
           }
     return true;
       }
   }
   else
   {
       return element === target;

   }
};

console.log(cmp({
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", false, null, {v:1}]}]
}, {
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", false, null, {v:1}]}]
})); // true

console.log(cmp({
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", false, null, {v:1}]}]
}, {
    key1: 3,
    key2: "string",
    key3: [4, "45", {key4: [5, "6", undefined, null, {v:1}]}]
})); // false
</script>

- Daphoque

Answer 10

我更喜欢下面的变体，因为：

- 除了第一行检查Object.is相等性之外，在结尾之前的每个返回语句都是“一致的方向”，即return false。 - 可以通过将其keyCheckLayersLeft参数设置为1来轻松派生出一个shallowEquals。

代码：

const hasOwnProperty = Object.prototype.hasOwnProperty;

export function deepEquals(x, y, keyCheckLayersLeft = -1) {
    // fast route: if values are identical, return true
    if (Object.is(x, y)) return true;

    // values are non-identical; so if one is a primitive or null/undefined, they can't be equal, thus return false
    if (typeof x !== "object" || x == null || typeof y !== "object" || y == null) return false;

    // special case (since it's the one "json relevant" object-type): if only one value is an array, consider them non-equal, thus return false
    if (Array.isArray(x) != Array.isArray(y)) return false;

    // values are non-identical objects; so if we've reached the key-check layer-limit, return false
    if (keyCheckLayersLeft == 0) return false;

    // check for differences in the objects' field-names and field-values; if any such difference is found, return false
    // NOTE: Objects.keys() excludes non-enumerable properties; to include them, use Object.getOwnPropertyNames() instead
    const xKeys = Object.keys(x), yKeys = Object.keys(y);
    if (xKeys.length != yKeys.length) return false;
    for (const key of xKeys) {
        if (!hasOwnProperty.call(y, key)) return false;
        if (!deepEquals(x[key], y[key], keyCheckLayersLeft - 1)) return false;
    }

    // none of the checks found a difference, so the objects must be equal
    return true;
}

// because of the keyCheckLayersLeft parameter, we can easily create a shallowEquals function
export function shallowEquals(objA, objB) {
    return deepEquals(objA, objB, 1);
}

- Venryx