Comparing 2 JSON objects structure in JavaScript

Lets say you have two JSON objects, jsonA and jsonB.

function compareValues(a, b) {

    //if a and b aren't the same type, they can't be equal
    if (typeof a !== typeof b) {
        return false;
    }
 
    // Need the truthy guard because
    // typeof null === 'object'
    if (a && typeof a === 'object') {
        var keysA = Object.keys(a).sort(),
            keysB = Object.keys(b).sort();

        //if a and b are objects with different no of keys, unequal
        if (keysA.length !== keysB.length) {
            return false;
        }

        //if keys aren't all the same, unequal
        if (!keysA.every(function(k, i) { return k === keysB[i];})) {
            return false;
        }

        //recurse on the values for each key
        return keysA.every(function(key) {
            //if we made it here, they have identical keys
            return compareValues(a[key], b[key]);
        });

    //for primitives just use a straight up check
    } else {
        return a === b;
    }
}

//true if their structure, values, and keys are identical    
var passed = compareValues(jsonA, jsonB); 

Note that this can overflow the stack for deeply nested JSON objects. Note also that this will work for JSON but not necessarily regular JS objects as special handling is needed for Date Objects, Regexes, etc.

Actually you do need to sort the keys, as they are not required to be spit out in any particular order. Write a function,

function getComparableForObject(obj) {
    var keys = Object.keys(obj);
    keys.sort(a, b => a > b ? 1 : -1);

    var comparable = keys.map(
            key => key + ":" + getValueRepresentation(obj[key])
        ).join(",");
    return "{" + comparable + "}";
}

Where getValueRepresentation is a function that either returns "String" or calls getComparableForObject. If you are worried about circular references, add a Symbol to the outer scope, repr, assign obj[repr] = comparable in the function above, and in getValueRepresentation check every object for a defined obj[repr] and return it instead of processing it recursively.

Sorting an array of the keys from the object works. However, sorting has an average time complexity of O(n⋅log(n)). We can do better. A fast general algorithm for ensuring two sets A and B are equivalent is as follows:

for item in B
  if item in A
    remove item from A
  else
    sets are not equivalent
sets are equivalent iff A is empty

To address @Katana31, we can detect circular references as we go by maintaining a set of visited objects and ensuring that all descendents of that object are not already in the list:

# poorly written pseudo-code
fn detectCycles(A, found = {})
  if A in found
    there is a cycle
  else
    found = clone(found)
    add A to found
    for child in A
      detectCycles(child, found)

Here's a complete implementation (you can find a simplified version that assumes JSON/non-circular input here):

var hasOwn = Object.prototype.hasOwnProperty;
var indexOf = Array.prototype.indexOf;

function isObjectEmpty(obj) {
  for (var key in obj) {
    return false;
  }

  return true;
}

function copyKeys(obj) {
  var newObj = {};

  for (var key in obj) {
    newObj[key] = undefined;
  }

  return newObj;
}

// compares the structure of arbitrary values
function compareObjectStructure(a, b) {
  return function innerCompare(a, b, pathA, pathB) {
    if (typeof a !== typeof b) {
      return false;
    }

    if (typeof a === 'object') {
      // both or neither, but not mismatched
      if (Array.isArray(a) !== Array.isArray(b)) {
        return false;
      }

      if (indexOf.call(pathA, a) !== -1 || indexOf.call(pathB, b) !== -1) {
        return false;
      }

      pathA = pathA.slice();
      pathA.push(a);

      pathB = pathB.slice();
      pathB.push(b);

      if (Array.isArray(a)) {
        // can't compare structure in array if we don't have items in both
        if (!a.length || !b.length) {
          return true;
        }

        for (var i = 1; i < a.length; i++) {
          if (!innerCompare(a[0], a[i], pathA, pathA)) {
            return false;
          }
        }

        for (var i = 0; i < b.length; i++) {
          if (!innerCompare(a[0], b[i], pathA, pathB)) {
            return false;
          }
        }

        return true;
      }

      var map = copyKeys(a), keys = Object.keys(b);

      for (var i = 0; i < keys.length; i++) {
        var key = keys[i];

        if (!hasOwn.call(map, key) || !innerCompare(a[key], b[key], pathA,
            pathB)) {
          return false;
        }

        delete map[key];
      }

      // we should've found all the keys in the map
      return isObjectEmpty(map);
    }

    return true;
  }(a, b, [], []);
}

Note that this implementation directly compares two objects for structural equivalency, but doesn't reduce the objects to a directly comparable value (like a string). I haven't done any performance testing, but I suspect that it won't add significant value, though it will remove the need to repeatedly ensure objects are non-cyclic. For that reason, you could easily split compareObjectStructure into two functions - one to compare the structure and one to check for cycles.