计算数据结构的MD5哈希值

Question

我想计算一个数据结构的md5哈希值，而不是字符串。我知道如何实现这个功能（依据值的类型进行分发、按照字典键顺序规范化和随机化等，递归到子值中）。但它似乎是一种通用的操作，所以我很惊讶需要自己编写代码来实现这个功能。在Python中有没有更简单的方法来实现这个功能？

更新：有人建议使用pickle，这是一个好主意，但pickle不能规范化字典键顺序：

>>> 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

- Ned Batchelder

---

我觉得有点不太好意思建议，但你能对你的数据结构的pickled版本进行md5sum吗？ - sarnold

腌制并不肮脏，只是不能满足哈希的需求。 - Ned Batchelder

啊，真遗憾。我本来希望它能为你节省大量的精力。 :) - sarnold

Answer 1

json.dumps()可以按键对字典进行排序，因此您不需要其他依赖项：

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)

输出:

87e83d90fc0d03f2c05631e2cd68ea02

- webwurst

---

很好，hashlib和json在Python中始终存在。 - Stéphane

不错的解决方案，但要记住有些数据类型不能直接转换为JSON格式，需要额外的处理，其中datetime是最常见的。例如：data = ['1234', 234, datetime.datetime(2013,1,1)]，执行hashlib.md5(json.dumps(a, sort_keys=True)).hexdigest()会导致以下错误：TypeError: datetime.datetime(2013, 1, 1, 0, 0) is not JSON serializable。 - Boris Chervenkov

@Boris：很容易让json模块序列化更多数据类型（包括大多数用户定义类的实例以及datetime.datetime实例），如我在问题Making object JSON serializable with regular encoder中所示的答案中所述。 - martineau

在Python3中可能会出现“TypeError: Unicode-objects must be encoded before hashing”错误。因此，请使用以下代码：data_md5 = hashlib.md5(json.dumps(data, sort_keys=True).encode('utf-8')).hexdigest()来解决问题。该代码将数据进行编码并计算MD5哈希值。 - Dineshs91

纯Python中的确定性哈希函数的非常聪明的解决方案。 - Chris Conlan

字典的顺序问题还存在吗？Python 3.7及以上版本保留了字典的插入顺序。 - Jeyekomon

Answer 2

bencode 对字典进行排序的方式如下：

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

输出：

af1b88ca9fd8a3e828b40ed1b9a2cb20

- Dan D.

---

是的，bencode似乎正好做我想象中的事情，但具有可逆性的额外功能。 - Ned Batchelder

需要注意的是，bencode 不是标准的 Python 2 或 3 模块。 - martineau

它也不能像pickle一样编码许多数据结构 :-( - user48956

我认为这不应再是被接受的解决方案了。Bencode 依赖于一个名为 BTL 的模块，但这个模块似乎已经不再易于获取（参见 https://github.com/bittorrent/bencode/issues/3）。 - David Kaufman

@DavidKaufman 记者发现的问题是相对导入的工作方式已经改变。模块bencode由一个包含__init__.py文件的目录组成，该文件从目录中的BTL.py文件进行导入。 BTL模块就在bencode包中。只是现在这样的导入必须使用点前缀形式。但是，旧版本的bencode模块是一个单独的自包含文件。 - Dan D.

@DavidKaufman 如果你这么认为，就请告诉提问者重新考虑。我只是提供了一个选项。甚至可能不是一个好的选项。 - Dan D.

Answer 3

我最终自己写了它，因为我认为我必须这样做：

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()

- Ned Batchelder

---

你会如何处理“set”类型？我个人认为，处理方式与元组和列表相同，不同之处在于应该首先进行“sorted()”排序。你同意吗？ - exhuma

是的，sorted(v) 是一个好方法。 - Ned Batchelder

注意，对update()的调用基本上是串联的。 因此，这将哈希{'test': 1}与['test'，1]和test1相同。这可能是所期望的行为，也可能不是。 - Ross Hemsley

@RossHemsley 你忽略了 self.md5.update(str(type(v)))。 - Ned Batchelder

没错，这很有帮助。值得注意的是，用这种方式做会有一些边缘情况。 - Ross Hemsley

Answer 4

你可以使用内置的 pprint，它将涵盖一些比建议的 json.dumps() 解决方案更多的情况。例如，datetime 对象将被正确处理。

将你的示例重写为使用 pprint 而不是 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

- UlfR

Answer 5

更新：由于字典中键的顺序随机性，此方法无法使用。非常抱歉，我没有考虑到这一点。

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

这适用于任何Python数据结构，也适用于对象。

- rvs

---

腌制并不能解决字典键中的随机性。 - Ned Batchelder

Answer 6

虽然需要依赖于joblib，但我发现joblib.hashing.hash(object)非常好用，并且专为与joblib的磁盘缓存机制配合使用而设计。从经验上看，它似乎在不同运行中产生一致的结果，即使是在pickle在不同运行中混淆数据的情况下也是如此。

或者，您可能会对artemis-ml的compute_fixed_hash函数感兴趣，该函数理论上以一种在多次运行中保持一致的方式对对象进行哈希。但是，我自己没有测试过。

很抱歉在原问题发布数百万年后才回答。

- Connor Brinton

Answer 7

ROCKY方式：将所有结构项放入一个父实体中（如果尚未），递归并对其进行排序/规范化等操作，然后计算其repr的md5。

- Hossein

---

我更愿意不改变数据结构来适应哈希任务。 - Ned Batchelder

Answer 8

计算JSON序列化的校验和是一个好主意，因为它易于实现，并且易于扩展到一些原生不支持JSON序列化的Python数据结构。

这是我对@webwurst答案的修改版本，它会将JSON字符串分块生成，并立即消耗这些块来计算最终的校验和，以防止大对象导致过多的内存消耗。

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)

- Danny Lin