#Objects#Recursion

Deep Equality

Compare two values structurally, because === only ever compares references.

By Pratik RaiMedium

Write deepEqual(a, b) returning whether the two values are structurally equal.

Two objects are equal when they have the same keys and every corresponding value is deeply equal; key order does not matter. Two arrays are equal when they have the same length and equal values in the same order. Primitives compare with ===, except that NaN equals NaN.

Examples

Input:

JSfile.javascript
1deepEqual( 2 { id: 7, tags: ['a', 'b'] }, 3 { id: 7, tags: ['b', 'a'] } 4);

Output:

false

The keys match and so does id, but the two tags arrays hold the same items in a different order, and array order counts.

Constraints

  • Values are plain objects, arrays or primitives, including undefined and NaN
  • No value contains a reference to itself

Notes

  • An array is never equal to an object, even one with matching numeric keys.
  • typeof null is "object", so it needs its own guard.

How to solve it

Structural, not referential

{a:1} === {a:1} is false. Two objects are the same only when they are the same object, which is why comparing state or props by === catches nothing when the contents changed in place.

Approach

Recurse, with the cheap answers first.

Implementation

JSfile.javascript
1function deepEqual(a, b) { 2 if (a === b) return true; 3 if (typeof a === 'number' && typeof b === 'number' && Number.isNaN(a) && Number.isNaN(b)) return true; 4 if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null) return false; 5 if (Array.isArray(a) !== Array.isArray(b)) return false; 6 const ka = Object.keys(a); 7 const kb = Object.keys(b); 8 if (ka.length !== kb.length) return false; 9 return ka.every((k) => Object.prototype.hasOwnProperty.call(b, k) && deepEqual(a[k], b[k])); 10}

Worth knowing

Three cases catch people. typeof null is "object", so null needs its own guard or you dereference it. Comparing key counts before walking is what makes {a:1} and {a:1,b:2} unequal rather than equal-on-what-they-share. And Array.isArray(a) !== Array.isArray(b) is what stops [1] matching {0:1}, which have identical keys.

NaN === NaN is false, so equality of two NaNs is a decision you make explicitly. Object.is gets it right and gets +0/-0 wrong for this purpose.

Goal: Return true only when the two values match all the way down.

Frequently asked questions

Why doesn't === work for comparing objects?
Because it compares references, not contents. Two objects are === only when they are the same object, so {a:1} === {a:1} is false even though they look identical.
How do you compare two objects by value?
Recursively: same key count, then every key present in both with deeply equal values. Arrays additionally need the same length and matching order.
What edge cases catch people out?
typeof null is "object", so null needs its own guard. An array and an object can share identical keys, so Array.isArray must match on both sides. And NaN === NaN is false, so equal NaNs need deciding explicitly.
Is there a built-in for this?
Not in the language. Object.is fixes NaN and -0 but is still a shallow comparison. Test frameworks and utility libraries ship their own, and JSON.stringify comparison only works when key order happens to match.

Related Challenges

Continue learning with these related challenges

View All
JavaScript

Deep Clone

Copy a nested structure so nothing is shared — including the cases that break a naive recursion.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Deep Freeze an Object

Freeze an object all the way down, because Object.freeze only handles the top level.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Array.prototype.groupBy

Group an array into buckets by a key function — now a real language feature as Object.groupBy.

JavaScript · ES6 — Pratik Rai ·