Computing an md5 hash of a data structure

Question

I want to compute an md5 hash not of a string, but of an entire data structure. I understand the mechanics of a way to do this (dispatch on the type of the value, canonicalize dictionary key order and other randomness, recurse into sub-values, etc). But it seems like the kind of operation that would be generally useful, so I'm surprised I need to roll this myself.

Is there some simpler way in Python to achieve this?

UPDATE: pickle has been suggested, and it's a good idea, but pickling doesn't canonicalize dictionary key order:

>>> import cPickle as pickle
>>> import hashlib, random 
>>> for i in range(10):
...  k = [i*i for i in range(1000)]
...  random.shuffle(k)
...  d = dict.fromkeys(k, 1)
...  p = pickle.dumps(d)
...  print hashlib.md5(p).hexdigest()
...
51b5855799f6d574c722ef9e50c2622b
43d6b52b885f4ecb4b4be7ecdcfbb04e
e7be0e6d923fe1b30c6fbd5dcd3c20b9
aebb2298be19908e523e86a3f3712207
7db3fe10dcdb70652f845b02b6557061
43945441efe82483ba65fda471d79254
8e4196468769333d170b6bb179b4aee0
951446fa44dba9a1a26e7df9083dcadf
06b09465917d3881707a4909f67451ae
386e3f08a3c1156edd1bd0f3862df481

Answer 1

json.dumps() can sort dictionaries by key. So you don't need other dependencies:

import hashlib
import json

data = ['only', 'lists', [1,2,3], 'dictionaries', {'a':0,'b':1}, 'numbers', 47, 'strings']
data_md5 = hashlib.md5(json.dumps(data, sort_keys=True).encode('utf-8')).hexdigest()

print(data_md5)

Prints:

87e83d90fc0d03f2c05631e2cd68ea02

Answer 2

bencode sorts dictionaries so:

import hashlib
import bencode
data = ['only', 'lists', [1,2,3], 
'dictionaries', {'a':0,'b':1}, 'numbers', 47, 'strings']
data_md5 = hashlib.md5(bencode.bencode(data)).hexdigest()
print data_md5

prints:

af1b88ca9fd8a3e828b40ed1b9a2cb20

Answer 3

I ended up writing it myself as I thought I would have to:

class Hasher(object):
    """Hashes Python data into md5."""
    def __init__(self):
        self.md5 = md5()

    def update(self, v):
        """Add `v` to the hash, recursively if needed."""
        self.md5.update(str(type(v)))
        if isinstance(v, basestring):
            self.md5.update(v)
        elif isinstance(v, (int, long, float)):
            self.update(str(v))
        elif isinstance(v, (tuple, list)):
            for e in v:
                self.update(e)
        elif isinstance(v, dict):
            keys = v.keys()
            for k in sorted(keys):
                self.update(k)
                self.update(v[k])
        else:
            for k in dir(v):
                if k.startswith('__'):
                    continue
                a = getattr(v, k)
                if inspect.isroutine(a):
                    continue
                self.update(k)
                self.update(a)

    def digest(self):
        """Retrieve the digest of the hash."""
        return self.md5.digest()

Answer 4

You could use the builtin pprint that will cover some more cases than the proposed json.dumps() solution. For example datetime-objects will be handled correctly.

Your example rewritten to use pprint instead of json:

>>> import hashlib, random, pprint
>>> for i in range(10):
...     k = [i*i for i in range(1000)]
...     random.shuffle(k)
...     d = dict.fromkeys(k, 1)
...     print hashlib.md5(pprint.pformat(d)).hexdigest()
... 
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db
b4e5de6e1c4f3c6540e962fd5b1891db

Answer 5

UPDATE: this won't work for dictionaries due to key order randomness. Sorry, I've not thought of it.

import hashlib
import cPickle as pickle
data = ['anything', 'you', 'want']
data_pickle = pickle.dumps(data)
data_md5 = hashlib.md5(data_pickle).hexdigest()

This should work for any python data structure, and for objects as well.

Answer 6

While it does require a dependency on joblib, I've found that joblib.hashing.hash(object) works very well and is designed for use with joblib's disk caching mechanism. Empirically it seems to be producing consistent results from run to run, even on data that pickle mixes up on different runs.

Alternatively, you might be interested in artemis-ml's compute_fixed_hash function, which theoretically hashes objects in a way that is consistent across runs. However, I've not tested it myself.

Sorry for posting millions of years after the original question

Answer 7

ROCKY way: Put all your struct items in one parent entity (if not already), recurse and sort/canonicalize/etc them, then calculate the md5 of its repr.

Answer 8

Calculating checksum upon a JSON serialization is a good idea as it's easy to implement and easy to extend for some Python data structures that are natively not JSON serializable.

This is my revised version of @webwurst's answer, which generates the JSON string in chunks that are immediately consumed to calculate the final checksum, to prevent excessive memory consumption for a large object:

import hashlib
import json

def checksum(obj, method='md5'):
    m = hashlib.new(method)
    encoder = json.JSONEncoder(
        # don't escape Unicode chars to save bytes
        ensure_ascii=False,

        # skip checking to save an in-memory mapping
        check_circular=False,

        # if mappings with different key order are to be treated as
        # identical
        sort_keys=True,
                         
        # reduce default spaces to be more compact
        separators=(',', ':'),
    )
    for chunk in encoder.iterencode(obj):
        m.update(chunk.encode('UTF-8'))

    # use .digest() to save a few bytes if the checksum is used only 
    # for internal comparison and not to be output
    return m.hexdigest()

data = [
    'only',
    'lists', [1,2,3],
    'dictionaries', {'a':0,'b':1},
    'numbers', 47,
    'strings', '哈囉世界'
]
chk = checksum(data)
print(chk)