java - Javaで実装された「最速」のハッシュ関数、ファイルの一部を比較

Question

Java でインスタンス「ファイル」の 2 つの異なるファイルを比較する必要があり、これを高速なハッシュ関数で実行したいと考えています。

アイデア: - ファイル 1 の最初の 20 行をハッシュする - ファイル 2 の最初の 20 行をハッシュする - 2 つのハッシュを比較し、それらが等しい場合は true を返します。

これまで Java に実装された「最速」のハッシュ関数を使用したいと考えています。あなたならどちらを選びますか？

Answer 1

If you want speed, do not hash! Especially not a cryptographic hash like MD5. These hashes are designed to be impossible to reverse, not fast to calculate. What you should use is a Checksum - see java.util.zip.Checksum and its two concrete implementations. Adler32 is extremely fast to compute.

Any method based on checksums or hashes is vulnerable to collisions, but you can minimise the risk by using two different methods in the way RSYNC does.

The algorithm is basically:

• Check file sizes are equal
• Break the files into chunks of size N bytes
• Compute checksum on each pair of matching blocks and compare. Any differences prove files are not the same.

This allows for early detection of a difference. You can improve it by computing two checksums at once with different algorithms, or different block sizes.

More bits in the result mean less chance of a collision, but as soon as you go over 64 bits you are outside what Java (and the computer's CPU) can handle natively and hence get slow, so FNV-1024 is less likely to give you a false negative but is much slower.

If it is all about speed, just use Adler32 and accept that very rarely a difference will not be detected. It really is rare. Checksums like these are used to ensure the internet can spot transmission errors, and how often do you get the wrong data turning up?

It it is all about accuracy really, you will have to compare every byte. Nothing else will work.

If you can compromise between speed and accuracy, there is a wealth of options out there.

Answer 2

同じシステムで同時に 2 つのファイルを比較する場合、両方をハッシュする必要はありません。両方を読み取ったときに、両方のファイルのバイトが等しいことを比較してください。それらを異なる時点で比較したり、異なる場所に置いたりする場合は、MD5 が高速で適切です。非常に大きなファイルを扱っていない限り、より高速なファイルが必要になる理由はあまりありません。私のラップトップでさえ、毎秒数百メガバイトをハッシュできます。

ファイルが同一であることを確認する場合は、ファイル全体をハッシュする必要もあります。それ以外の場合は、サイズと最終更新時刻を確認するだけで十分です。ファイルの先頭と末尾が非常に大きく、中央が変更されないことが信頼できる場合は、ファイルの先頭と末尾を確認することもできます。ただし、数百メガバイトを扱っていない場合は、各ファイルのすべてのバイトをチェックすることもできます。