Python中的顺序不变哈希

Question

在Python中,我想快速计算文件行的顺序不变哈希,作为识别其"唯一"内容的方法.这些文件例如是a的输出,select ... from table因此行的顺序是随机的.

这是一个实现我想要的例子(使用hashlib中的一个哈希),但代价是必须对行进行排序. 请注意,对行进行排序只是实现目标的一种方法,即获取不依赖于文件中行的顺序的哈希.但显然,我想避免O(n*log(n))成本,尤其是 当文件更长时.

def get_hexdigest(filename, hasher, blocksize=65536, order_invariant=False):
    if not os.path.isfile(filename):
        return None
    if order_invariant:
        with open(filename, 'r') as f:
            for line in sorted(f):
                hasher.update(line.encode())
    else:
        with open(filename, 'rb') as f:
            while True:
                buf = f.read(blocksize)
                hasher.update(buf)
                if len(buf) < blocksize:
                    break
    return hasher.hexdigest()

所以,对于例如1MB,50K行的文件:

%%time
get_hexdigest('some_file', hashlib.sha1())
# Wall time: 1.71 ms

但:

%%time
get_hexdigest('some_file', hashlib.sha1(), order_invariant=True)
# Wall time: 77.4 ms

有什么更好/更快的方法呢？

正如在这个答案中所指出的,Scala有一个基于Murmurhash的顺序不变哈希,但是我认为它是mmh3的32位版本(对于我来说太容易碰撞),而且我宁愿使用一些标准库Python而不是在C或Cython中实现某些东西.Murmurhash3有一个128位版本,但它的输出在x64和x86上是不同的.我想有机器独立的结果.

所以,总之,我想:

• 跨机器架构的一致结果
• 低冲突率,即至少128位具有良好的色散(但我不需要哈希加密)
• 相当快,即1MB,50K行文件至少不到5ms.
• 如果可能的话,作为PyPi或Conda的图书馆随时可用.
• 适用于具有重复行的文件(因此只需对每行哈希进行异或,因为任何一对相同的行都会相互抵消).

---

编辑和注释: 感谢几条评论,上面的代码更新为对内存中的行进行排序.原始版本order_invariant is True是:

    with os.popen('sort {}'.format(filename)) as f:
        for line in f:
            hasher.update(line.encode(encoding='utf-8'))
    return hasher.hexdigest()

相关的墙壁时间(对于上面使用的文件)则为238毫秒.现在减少到77毫秒,但仍然比没有排序线慢.排序将为n行添加*log(n)成本.

在模式的编码方式(以UTF-8)和读出'r'也没有'rb'读线路时,如然后我们得到的字符串不是字节是必要的.我不想依赖假设文件只包含ASCII数据; 阅读'rb'可能会导致线路不正确分裂.当order_invariantFalse 时我没有同样的关注,因为那时我不必拆分文件,因此最快的方法是啜饮大块的二进制数据来更新hasher.

Answer 1

我认为您应该在 ( ) 之前对文件进行排序select ... from table order by ...，或者针对您的实际问题提出另一种解决方案。

无论如何，Python 中使用freezeset 的可能方法是：

#!/usr/bin/python

lines1 = ['line1', 'line2', 'line3', 'line4']
lines2 = ['line2', 'line1', 'line3', 'line4']  # same as lines1 but different order
lines3 = ['line1', 'line1', 'line3', 'line4', 'line5']


for lines in [lines1, lines2, lines3]:
    print(lines)
    print(hash(frozenset(lines)))
    print('')

输出

['line1', 'line2', 'line3', 'line4']
8013284786872469720

['line2', 'line1', 'line3', 'line4']
8013284786872469720

['line1', 'line1', 'line3', 'line4', 'line5']
7430298023231386903

我怀疑它是否符合您的性能限制。我不知道 freezeset() 的时间复杂度（Big O）。它还假设线条是唯一的。我再次强烈建议以不同的方式解决根本问题。