6

サーバーにアップロードするファイルが非常に多いので、重複を避ける方法が必要です。

したがって、大きな文字列から一意の小さなキー値を生成することは、チェックサムが意図したことのように見え、ハッシュはその進化のように見えました。

だから私はこれを行うためにハッシュmd5を使用するつもりでした。しかし、どこかで「MD5は一意のキーではない」と読んだので、それは本当に奇妙だと思いました。

これを行う正しい方法は何ですか？

編集：ところで、私は次のことに到達するために2つ のソースを取りました。これは私が現在それを行っている方法であり、Python2.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()
4

3 に答える 3

7

MD5に固執することは良い考えです。念のため、ファイルの長さまたはチャンクの数をファイルハッシュテーブルに追加します。

はい、同じMD5ハッシュを持つ2つのファイルに遭遇する可能性がありますが、それはほとんどありません（ファイルのサイズが適切な場合）。したがって、チャンクの数をハッシュに追加すると、それを減らすのに役立つ場合があります。これは、同じMD5で同じサイズの2つのファイルを見つける必要があるためです。

# 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に切り替えて、同じ方法を使用します。または、パフォーマンスが問題にならない場合は、両方（連結）を使用することもできます。

もちろん、これはバイナリレベルの重複ファイルでのみ機能し、「同じ」であるが署名が異なる画像、音声、ビデオでは機能しないことに注意してください。

于 2010-05-04T23:37:11.627 に答える
3

ハッシュの問題は、「大きな」データセットから「小さな」識別子を生成していることです。非可逆圧縮のようなものです。一意性を保証することはできませんが、それを使用して、比較する必要のある他のアイテムの数を大幅に制限することができます。

MD5が128ビット値を生成することを考慮してください（正確なビット数は関係ありませんが、それがそれであると思います）。入力データセットに129ビットがあり、実際にそれらすべてを使用する場合、各MD5値は平均して2回表示されます。より長いデータセット（たとえば、「正確に1024の印刷可能な文字のすべてのテキストファイル」）の場合、十分な入力を取得すると、衝突が発生します。別の答えが言ったこととは反対に、衝突するのは数学的に確実です。

http://en.wikipedia.org/wiki/Birthday_Paradoxを参照してください

確かに、2.6 * 10 ^ 18エントリで128ビットハッシュとの衝突の可能性は約1％ですが、衝突が発生した場合は、決して発生しないことを期待するよりも処理する方が適切です。

于 2010-05-04T23:13:48.110 に答える
2

MD5の問題は、壊れていることです。最も一般的な用途では、ほとんど問題はなく、人々はまだMD5とSHA1の両方を使用していますが、ハッシュ関数が必要な場合は、強力なハッシュ関数が必要だと思います。私の知る限り、これらのいずれかに代わる標準的なものはまだありません。強力であると「想定される」アルゴリズムは多数ありますが、SHA1とMD5の経験が最も豊富です。つまり、これら2つがいつ壊れるかはわかっていますが、新しいアルゴリズムがいつ壊れたかはあまりわかりません。

結論：リスクについて考えてください。余分な距離を歩きたい場合は、パフォーマンスのペナルティを犠牲にして、ハッシュの重複を見つけたときに追加のチェックを追加することができます。

于 2010-05-04T22:57:50.533 に答える