在Python中基于文件内容创建唯一键

Question

我有很多文件需要上传到服务器，我只想找到一种方法来避免重复的文件。

所以，从一个很长的字符串生成一个独特且小的键值，听起来像是校验和（checksum）应该做的事情，而哈希（hashing）似乎是这个概念的进化版。

我本来打算用MD5哈希来实现这个功能。但后来我在某个地方看到有人说“MD5并不适合用作唯一键”，我觉得这真奇怪。

那正确的做法是什么呢？

补充：顺便说一下，我参考了两个 来源，得到了以下内容，这就是我目前的做法，并且在Python 2.5中运行得很好：

import hashlib

def md5_from_file (fileName, block_size=2**14):
    md5 = hashlib.md5()
    f = open(fileName)
    while True:
        data = f.read(block_size)
        if not data:
            break
        md5.update(data)
    f.close()
    return md5.hexdigest()

Answer 1

MD5这个东西有个问题，就是它已经不安全了。虽然在很多常见的情况下用起来没什么大问题，所以很多人还是在用MD5和SHA1，但我觉得如果你需要一个哈希函数，那就得用一个安全性强的。根据我所知道的，目前还没有一个标准的替代品可以完全取代这两个。虽然有一些算法被认为是安全的，但我们对SHA1和MD5的了解更多。也就是说，我们（认为）知道这两个算法什么时候会出问题，而对于那些新算法，我们就不太清楚了。

总之：要考虑风险。如果你想更谨慎一点，可以在发现哈希值重复的时候加一些额外的检查，不过这样会影响性能。

Answer 2

哈希的一个问题是，它是从一个“大的”数据集中生成一个“小的”标识符。这就像是有损压缩。虽然不能保证每个标识符都是唯一的，但可以用它来大大减少需要比较的其他项目数量。

比如说，MD5会产生一个128位的值（我想就是这个，虽然具体的位数并不重要）。如果你的输入数据集有129位，并且你真的用到了所有这些位，那么每个MD5值平均会出现两次。对于更长的数据集（例如“所有正好有1024个可打印字符的文本文件”），一旦输入数量足够，你还是会遇到重复的情况。与其他回答所说的相反，发生重复是数学上必然的。

可以参考一下生日悖论。

当然，在有2.6*10^18个条目的情况下，使用128位哈希碰撞的概率大约是1%。但处理碰撞的情况总比希望永远不会发生要好。

Answer 3

继续使用MD5是个不错的主意。为了更保险，我建议你在文件哈希表中加上文件的长度或者块的数量。

确实有可能出现两个文件的MD5哈希值是一样的，但这种情况很少发生（如果你的文件大小还不错的话）。所以把块的数量加到你的哈希中可能会帮你减少这种情况，因为这样你就得找到两个大小相同且MD5也相同的文件。

# This is the algorithm you described, but also returns the number of chunks.
new_file_hash, nchunks = hash_for_tile(new_file)
store_file(new_file, nchunks, hash)

def store_file(file, nchunks, hash):
  "" Tells you whether there is another file with the same contents already, by 
     making a table lookup ""
  # This can be a DB lookup or some way to obtain your hash map
  big_table = ObtainTable()

  # Two level lookup table might help performance
  # Will vary on the number of entries and nature of big_table
  if nchunks in big_table:
     if hash in big_table[hash]:
       raise DuplicateFileException,\
         'File is dup with %s' big_table[nchunks][lookup_hash]
  else:
    big_table[nchunks] = {}

  big_table[nchunks].update({
    hash: file.filename
  })

  file.save() # or something

为了进一步降低这种可能性，可以换成SHA1，并且用同样的方法。或者如果性能不是问题的话，可以同时使用两者（拼接在一起）。

当然，要记住，这种方法只适用于在二进制层面上完全相同的文件，而不适用于那些“看起来相同”但签名不同的图片、声音和视频。