Implementing deep comparison in Javascript

I was reading through Eloquent JavaScript and one of the exercises is to write a function deepEqual that takes two values and returns true only if they are the same value or are objects with the same properties, where the values of the properties are equal when compared with a recursive call to deepEqual.

Let’s get started.

Note that both UnderscoreJS and Lodash have a toEqual method that can be used if you’re using one of these libraries.

JavaScript has both strict and type–converting comparisons.

The == operator compares objects by identity. === and !== are strict comparison operators. For strict equality the objects being compared must have the same type and:

  • Two strings are strictly equal when they have the same sequence of characters, same length, and same characters in corresponding positions.
  • Two numbers are strictly equal when they are numerically equal (have the same number value). NaN is not equal to anything, including NaN. Positive and negative zeros are equal to one another.
  • Two Boolean operands are strictly equal if both are true or both are false.
  • Two objects are strictly equal if they refer to the same Object.
  • Null and Undefined types are == (but not ===). [I.e. (Null==Undefined) is true but (Null===Undefined) is false]

Comparison Operators – MDN

Two objects are strictly equal if they refer to the same Object. In other words,  two distinct objects are never equal for either strict or abstract comparisons.

var obj1 = { 'key': 'value'}, ob2 = { 'key': 'value' }
obj1 === obj2 // false

To find out whether values should be compared directly or have their properties compared, we can use the typeof operator. If it produces “object” for both values, we should do a deep comparison. However we have to watch out for one major gotcha in JavaScript, because of a historical accident, ​typeof null also produces “object”.

With that, to test whether you are dealing with a real object will look something like typeof x == "object" && x != null. Let us write a function for that:

function isObject (obj) {
    if (typeof obj != "object" || obj == null) {
        return false
    }

    return true
}

Next test is to see whether both objects have the same properties. To be equal, both objects should have the same set of properties and each of these properties should contain the same value.

We can use Object.keys to go over the properties to test whether both objects have the same set of property names and whether those properties have identical values. One way to do that is to ensure that both objects have the same number of properties (the lengths of the property lists are the same).

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

And then, looping over one of the object’s properties to compare them, making sure the other actually has a property by that name. If they have the same number of properties and all properties in one also exist in the other, they have the same set of property names.  We compare the values of each property by letting the function recursively call itself in the for/in loop.

for (let prop in x) {
    if (!deepEqual(x[prop], y[prop])) {
        return false
    }
}

Returning the correct value from the function is best done by immediately returning false when a mismatch is found if not returning true at the end of the function.

Putting everything together, we have:

function deepEqual(x, y) {
    if (x === y) {
        return true
    } else if (isObject(x) && isObject(y)) {
        if (Object.keys(x).length != Object.keys(y).length) {
            return false
        }

        for (let prop in x) {
            if (!deepEqual(x[prop], y[prop])) {
                return false
            }
         }

        return true
    }
}

function isObject (obj) {
    if (typeof obj != "object" || obj == null) {
        return false
    }

    return true 
}

Testing the function:

let obj = {here: {is: "an"}, object: 2}

deepEqual(obj, obj) // true
deepEqual(obj, {here: 1, object: 2}) // false
deepEqual(obj, {here: {is: "an"}, object: 2}) // true

One more improvement we could make is to make the isObject function private.  It not used outside this function and unnecessarily gets added to the global scope.

We can hide a “private” function inside a function of this kind by placing one function declaration inside of another. The inner function is not hoisted out into the global scope, so it is only visible inside of the parent function. With that:

function deepEqual(x, y) {
    if (x === y) {
        return true
    } else if (isObject(x) && isObject(y)) {
        if (Object.keys(x).length != Object.keys(y).length) {
            return false
        }

        for (let prop in x) {
            if (!deepEqual(x[prop], y[prop])) {
                return false
            }
        }

        return true
    }

    function isObject (obj) {
        if (typeof obj != "object" || obj == null) {
            return false
        }

        return true
    }
}

Lastly, this StackOverflow question about determining equality of two JavaScript objects is a really great learning resource, do read.

 

Advertisements