How do I make a checksum from a JavaScript Object?

Question

I need to make a checksum from a JavaScript Object.
Unfortunately, there does not seem to be an easy way to accomplish this because of JavaScript's Object ordering. For example, take these Objects:

var obj1 = {type:"cake",quantity:0}
  , obj2 = {quantity:0,type:"cake"};

I consider these Objects equal in data, and would like their checksums to be the same. I really don't care about the order of the Object just as long as the data in them is the same.
Alas, JSON.stringify of both of them is actually not equal; as the only way to make a checksum of an Object is via its String representation, and the JSON.stringify-ed representations are not equal, my checksums will not be equal!
One solution I have come up with is to recreate the Object based on a predefined schema, like so:

var schema = ["type","quantity"];
function sortify(obj,schema){
  var n={};
  for(i in schema)
    n[schema[i]]=obj[schema[i]];
  return n
}

Running JSON.stringify(sortify(obj1,schema))==JSON.stringify(sortify(obj2,schema)) will return true... but at the price of creating a new Object and shuffling around data.

My other solution is to replace the JSON.stringify method with one that picks keys from a predefined schema and stringifying their values, then joining them together. The function reads:

function smarterStringify(obj,schema){
  var s="";
  for(i in schema)
    s+=JSON.stringify(obj[schema[i]]);
  return s
}

Ignoring the fact that this method doesn't return correct JSON (it's close enough as an example of what I'm trying to do), it is a massive improvement over the first one in speed (at least in my Chrome OS browser, you can check it yourself here: http://jsperf.com/sort-then-json-stringify-vs-smarter-stringify), and of course it makes the two Object String representations equal!

However, I was just wondering if I had missed something and there was a built-in method for something like this all along that didn't a) drive the JavaScript GC into a pathological case or b) do way too many String concatenations. I'd rather not do those.

Dreamworld

You should not use for ... in loops to iterate over arrays in JavaScript. Use a plain for loop with an index variable or use .forEach(). – Scud

Are all the property values in your object simple values or can some of them be objects or arrays (e.g. nested structures)? – Ahriman

@Ahriman I was planning on having another Object inside it but it's not a necessity – Dreamworld

That just means you have to check the type of each value and decide if you need to expand it also. It just adds more code, but is certainly doable. – Ahriman

I was tying to do this same thing, but the ordering of my objects are consistent, so that aspect of your issue wasn't a problem for me. However, I did have an issue with JSON.stringify generating different checksums on future rebuilds of what should have been the exact same object. This issue went away once I removed all whitespace by passing additional arguments: JSON.stringify(obj,null,0). – Zanthoxylum

Answer 1

You can collect the keys into an array with Object.keys(), sort that array and then checksum the keys/values in that known, predictable order. I don't know of any way to use JSON.stringify() with all the sorted keys at once though so you'd have to do your own checksum.

I am not aware of any built-in method for something like this. Object keys are NOT guaranteed to be in any particular order so it would not be safe to rely on that.

---

If you don't have nested objects or arrays as property values, then you could do something like this:

// creates an array of alternating property name, property value
// with properties in sorted order
// then stringify's that array
function stringifyPropsInOrder(obj) {
    var keys = Object.keys(obj).sort();
    var output = [], prop;
    for (var i = 0; i < keys.length; i++) {
        prop = keys[i];
        output.push(prop);
        output.push(obj[prop]);
    }
    return JSON.stringify(output);
}

function compareObjects(a, b) {
    return stringifyPropsInOrder(a) === stringifyPropsInOrder(b);
}

If you want faster performance, you don't have to stringify (that was just done here to save code). You could just return the flattened output array and compare the arrays directly.

---

If you could have embedded objects as property values, then some more work has to do to recusively expand those into the same flattened array of properties/values.

Ahriman

Answer 2

3 years later...

I came across this question as I wanted to hash my JSON objects to create Etags for my HTTP responses. So I ended up writing my own solution for Node, jsum, which boils down to a simple serializer:

/**
 * Stringifies a JSON object (not any randon JS object).
 *
 * It should be noted that JS objects can have members of
 * specific type (e.g. function), that are not supported
 * by JSON.
 *
 * @param {Object} obj JSON object
 * @returns {String} stringified JSON object.
 */
function serialize (obj) {
  if (Array.isArray(obj)) {
    return JSON.stringify(obj.map(i => serialize(i)))
  } else if (typeof obj === 'object' && obj !== null) {
    return Object.keys(obj)
      .sort()
      .map(k => `${k}:${serialize(obj[k])}`)
      .join('|')
  }

  return obj
}

You can then take the result and hash it using common algorithms (e.g. SHA256) or use the convenient method of digest from jsum package.

---

Please note the license here!

Nittygritty

Short and to the point. Maybe you could combine it with decycle (github.com/douglascrockford/JSON-js ), in order to handle cyclic structures – Corie

Awesome use of recursion. It's too small to be as good as it is! – Zanthoxylum

Answer 3

You could also make a function which compares your objects in place:

function compareObjects(a, b) {
  var akeys = Object.keys(a);
  var bkeys = Object.keys(b);
  var len = akeys.length;
  if (len != bkeys.length) return false;
  for (var i = 0; i < len; i++) {
    if (a[akeys[i]] !== b[akeys[i]]) return false;
  }
  return true;
}

This assumes they are objects passed in, and that they're simple flat objects. Logic could be added to check these assumptions and recursively check if sub-objects are equal.

Annalisaannalise

This is assuming that the keys you get from both objects with Object.keys() are in exactly the same order which is not guarenteed to be anything in particular. – Ahriman

No it doesn't as it uses only the akeys. – Miriam

You are assuming that Object.keys() delivers same named properties in exactly the same spot in the returned array. But, since Object.keys() delivers properties in the same order as for/in does, you are assuming that the properties are iterated in a specific order which is NOT guaranteed by the specification. – Ahriman

It does not assume the order is the same. It takes a key from a and checks that key against b. Order is irrelevant here. It checks the same number of keys exist on each object and that the values are the same across objects. I've already tested this. – Annalisaannalise

And where is the problem when it only compares the objects? The order is not important in this case. – Miriam

You are assuming that a given property on both objects ends up in exactly the same array slot in aKeys and bKeys. Can you show me a specification that says that is guaranteed to be true? In fact, the keys returned from Object.keys() can be in any order. You could sort your keys arrays to remove this issue. – Ahriman

And another issue. These two objects will show as equal {hello: true} and {hello: 1} because you are using != instead of !==. – Ahriman

No they won't. Because obj2.hello is undefined. In the second case I agree. By the way, I think you still don't understand he only uses akeys, not both arrays. – Miriam

updated for !== but please just go test and see that the order is irrelevant here. – Annalisaannalise

I think you're relying on a behavior that may be coded into modern browsers, but is explicitly mentioned as NOT guaranteed by the specification. Adding a simple .sort() after Object.keys() would make your method compatible with the specification. I don't know why you refuse to be safe. – Ahriman

Dude.. seriously. Take a step back. You are missing something. The order is not relevant here, and no modern browser tricks are involved. The sort is completely, unequivocally, unnecessary here. It does not matter what order the keys are checked in, only that they are all checked. Going key by key from the keys in A, making sure that the value of that key is the same on A and B. Enough. – Annalisaannalise

Suppose each object has a key named "foo". You are assuming that Object.keys() will return that key in the same array slot for both objects. You are assuming that the implementation does that even if the objects were created in different fashions and have been manipulated differently along the way to now end up with the same set of keys. The JS specification does not specify that it must work that way and many possible implementation choices would not guarantee order. – Ahriman

No. No. No. I am not assuming that, at all. I don't care what order they are returned in. You are completely misreading what is happening here, and should just stop. – Annalisaannalise