2 つのファイルが等しいかどうかを確認する最速のハッシュ アルゴリズムは何ですか?
https://stackoverflow.com/questions/1761607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2 つのファイルが等しいかどうかを確認するために使用されるハッシュ関数を作成する最速の方法は何ですか?
セキュリティはそれほど重要ではありません。
編集：ネットワーク接続を介してファイルを送信しているので、両側のファイルが等しいことを確認します
解決
一つのアプローチは、単純なCRC-32アルゴリズムを使用するかもしれない、とCRCの値が等しい比較した場合にのみ、SHA1またはより堅牢なものとハッシュを再実行します。高速なCRC-32は、任意の日暗号的に安全なハッシュをアウトパフォームします。
他のヒント
本当に複雑なハッシュや遅いハッシュを使用している場合を除き、ディスクからデータをロードするのは、ハッシュを計算するよりもはるかに時間がかかります (RAM ディスクやトップエンド SSD を使用している場合を除く)。
したがって、2 つのファイルを比較するには、次のアルゴリズムを使用します。
- サイズを比較する
- 日付を比較します (ここで注意してください:これでは間違った答えが得られる可能性があります。これが自分に当てはまるかどうかをテストする必要があります)
- ハッシュを比較する
これにより、高速フェールが可能になります (サイズが異なる場合は、ファイルが異なることがわかります)。
処理をさらに高速化するには、ハッシュを 1 回計算してファイルと一緒に保存します。また、ファイルの日付とサイズをこの追加ファイルに保存することで、メイン ファイルが変更されたときにハッシュを再計算する必要があるか、ハッシュ ファイルを削除する必要があるかをすぐに知ることができます。
xxhashは非常に高速かつ強力なとしての地位を主張し、衝突ワイズます：
http://cyan4973.github.io/xxHash/する
32ビットプロセッサ上の全体的な、しかし、より遅い32よりも64ビットプロセッサ上で「より速く」走る64ビットのバリアントは、（図に行く）があります。
http://code.google.com/p/crcutil にも言われています非常に高速である（そしておそらく非常に高速ですハードウェアCRC命令どこ存在し、活用していますが、それらをサポートするハードウェアを持っていない場合は、早くはありません）。 CRC32CがxxHashとして、あるいはない（衝突の面で）ハッシュのように良いかどうかを知りません...
https://code.google.com/p/cityhash/ に似ているようですそして、[それが指示した場合、ハードウェアCRC32C命令を使用するには、下にコンパイルできるように] crcutilに関連します。
あなたは「ただ最速の生の速度をしたい」とハッシュ出力のランダム分布の品質に関する限り気にしない（小さなセットで、例えば、または速度が最優先事項である場合）場合は、言及したいくつかの高速なアルゴリズムがありますここに： http://www.sanmayce.com/Fastest_Hash/する（これらの "かなりランダムではありません"分布型アルゴリズムであり、いくつかのケースでは）、「十分に良い」と非常に速いです。どうやらFNV1A_Jesteressは、小さな文字列に対していくつかの他の可能性が、「長い」文字列の最速です。 http://locklessinc.com/articles/fast_hash/ にも関連すると思われます。私はこれらの衝突の性質が何であるかを確認するために研究しませんでした。
あなたは試みることができる MurmurHash には、具体的に速くなるように設計し、コードに非常に簡単ですしています。 MurmurHashは、念のために、しかし試合を返す場合は、にそして第二に、より安全なハッシュたい場合があります。
このタイプのアプリケーションの場合、 アドラー32 おそらく、妥当なレベルのセキュリティを備えた最速のアルゴリズムです。より大きなファイルの場合は、複数のハッシュ値を計算することができます (たとえば、ファイルの 5 MB のブロックごとに 1 つ)。これにより、エラーの可能性が減ります (つまり、ハッシュが同じでもファイルの内容が異なる場合の割合）。さらに、このマルチハッシュ値の設定により、ハッシュの計算をマルチスレッド方式で実装できるようになります。
編集:(スティーブン・サディット氏の発言を受けて)
ファイルが小さい場合は注意してください。
Adler32 の「暗号化」特性、あるいはむしろその弱点は、特にショート メッセージに関してよく知られています。このため、提案されている解決策は、数キロバイト未満のファイルに対しては避けるべきです。
それでもなお、質問の中で、OPは明示的に求めています 高速なアルゴリズム そして セキュリティに関する懸念を解消します. 。さらに、スピードの追求はおそらく次のことを暗示している可能性があります。 1 つは「大きな」ファイルを扱う場合 小さいものではなく。この文脈では、おそらく 5Mb のファイルチャンクに並行して適用される Adler32 は、依然として非常に有効な答えです。Alder32 は、そのシンプルさとスピードで評判です。また、その信頼性は、同じ長さの CRC よりも低いままですが、4000 バイトを超えるメッセージでは十分に許容できます。
なぜちょうど時に各少量を読んでとは比較にならない、あなたはそれらの両方のハッシュを生成するために、両方のファイルを読み込む必要がありますことを考えると？
CRC には非常に単純なアルゴリズムであることを失敗ます。
私たちはここに最適化されていると、タスクに費やした時間です。 残念ながら、私たちは最適解がどうあるべきかを知るために手元の作業について十分に知らない。
2つの任意のファイルの1回の比較のためにそれはありますか？ それはあなたのIOのために良いでしょう場合（メガバイトによって、またはメガバイト）バイトごと、そして、大きさを比較し、その後、単純にファイルを比較ます。
これは、ファイル、またはファイルの多くのセットの2つの大きなセットのためであり、それは1回の運動ではない場合。しかし、頻繁に起こるか何かが、その後1は、各ファイルのハッシュを保存する必要があります。ハッシュは、ユニークなことはありませんが、言っ9桁（32ビット）の数がハッシュさは約40億の組み合わせのために良いだろう、と64ビットの数は、いくつかの16 * 10 ^ 18京異なるファイルを区別するのに十分な良いでしょうます。
まともな妥協点は、各ファイルの最初の8Kのための1つ、1メガバイト+ 8Kのための別の2 32ビットのハッシュを生成することで、単一の64ビット数として一緒に平手打ち。 DBにすべての既存のファイルをカタログ化すると、かなり迅速であるべきであり、このDBに対して候補ファイルを検索することも非常に迅速でなければなりません。一致するものがあるならば、それらが同じであるかどうかを判断する唯一の方法は、ファイル全体を比較することです。
私は、彼らが必要だと思うものを常に決してないんれ、彼らが必要なものを人々に与えることで信者、またはうと思っています。
いずれにせよ、あなたは完全にそれぞれのファイルを読み込む必要があり、これだけの両方のファイルを読み込み、ブロック間を比較します。
ハッシュを使用すると、単にCPUの使用率とより多くの何を得ることができます。あなたは何も書いていないため、OSのキャッシュが効果的に使用すると、読み込んだデータをドロップしますので、Linuxで、ちょうど<のhref =「http://linux.about.com/library/cmd/blcmdl1_cmp.htm」のrel =」を使用しますnofollowを」タイトル= "CMPツール"> CMPツールの
以下は、私の個人プロジェクトから重複ファイルを見つけて写真を並べ替え、重複を削除するコードです。私の経験によると、最初に CRC32 などの高速ハッシュ アルゴリズムを使用し、次に MD5 または SHA1 を実行するとさらに遅くなり、同じサイズのファイルのほとんどが確かに重複しているため、改善されませんでした。したがって、ハッシュを 2 回実行すると、CPU 時間の観点から見てコストが高くなります。 、このアプローチはすべての種類のプロジェクトに正しいとは限りませんが、画像ファイルには間違いなく当てはまります。ここでは、同じサイズのファイルに対してのみ MD5 または SHA1 ハッシュを実行しています。
追伸：ハッシュを効率的に生成するには、Apache Commons コーデックに依存します。
使用例: new DuplicateFileFinder("MD5").findDuplicateFilesList(filesList);
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import org.apache.commons.codec.digest.DigestUtils;
/**
* Finds the duplicate files using md5/sha1 hashing, which is used only for the sizes which are of same size.
*
* @author HemantSingh
*
*/
public class DuplicateFileFinder {
private HashProvider hashProvider;
// Used only for logging purpose.
private String hashingAlgo;
public DuplicateFileFinder(String hashingAlgo) {
this.hashingAlgo = hashingAlgo;
if ("SHA1".equalsIgnoreCase(hashingAlgo)) {
hashProvider = new Sha1HashProvider();
} else if ("MD5".equalsIgnoreCase(hashingAlgo)) {
hashProvider = new Md5HashProvider();
} else {
throw new RuntimeException("Unsupported hashing algorithm:" + hashingAlgo + " Please use either SHA1 or MD5.");
}
}
/**
* This API returns the list of duplicate files reference.
*
* @param files
* - List of all the files which we need to check for duplicates.
* @return It returns the list which contains list of duplicate files for
* e.g. if a file a.JPG have 3 copies then first element in the list
* will be list with three references of File reference.
*/
public List<List<File>> findDuplicateFilesList(List<File> files) {
// First create the map for the file size and file reference in the array list.
Map<Long, List<File>> fileSizeMap = new HashMap<Long, List<File>>();
List<Long> potDuplicateFilesSize = new ArrayList<Long>();
for (Iterator<File> iterator = files.iterator(); iterator.hasNext();) {
File file = (File) iterator.next();
Long fileLength = new Long(file.length());
List<File> filesOfSameLength = fileSizeMap.get(fileLength);
if (filesOfSameLength == null) {
filesOfSameLength = new ArrayList<File>();
fileSizeMap.put(fileLength, filesOfSameLength);
} else {
potDuplicateFilesSize.add(fileLength);
}
filesOfSameLength.add(file);
}
// If we don't have any potential duplicates then skip further processing.
if (potDuplicateFilesSize.size() == 0) {
return null;
}
System.out.println(potDuplicateFilesSize.size() + " files will go thru " + hashingAlgo + " hash check to verify if they are duplicate.");
// Now we will scan the potential duplicate files, and eliminate false positives using md5 hash check.
List<List<File>> finalListOfDuplicates = new ArrayList<List<File>>();
for (Iterator<Long> potDuplicatesFileSizeIterator = potDuplicateFilesSize
.iterator(); potDuplicatesFileSizeIterator.hasNext();) {
Long fileSize = (Long) potDuplicatesFileSizeIterator.next();
List<File> potDupFiles = fileSizeMap.get(fileSize);
Map<String, List<File>> trueDuplicateFiles = new HashMap<String, List<File>>();
for (Iterator<File> potDuplicateFilesIterator = potDupFiles.iterator(); potDuplicateFilesIterator
.hasNext();) {
File file = (File) potDuplicateFilesIterator.next();
try {
String md5Hex = hashProvider.getHashHex(file);
List<File> listOfDuplicatesOfAFile = trueDuplicateFiles.get(md5Hex);
if (listOfDuplicatesOfAFile == null) {
listOfDuplicatesOfAFile = new ArrayList<File>();
trueDuplicateFiles.put(md5Hex, listOfDuplicatesOfAFile);
}
listOfDuplicatesOfAFile.add(file);
} catch (IOException e) {
e.printStackTrace();
}
}
Collection<List<File>> dupsOfSameSizeList = trueDuplicateFiles.values();
for (Iterator<List<File>> dupsOfSameSizeListIterator = dupsOfSameSizeList.iterator(); dupsOfSameSizeListIterator
.hasNext();) {
List<File> list = (List<File>) dupsOfSameSizeListIterator.next();
// It will be duplicate only if we have more then one copy of it.
if (list.size() > 1) {
finalListOfDuplicates.add(list);
System.out.println("Duplicate sets found: " + finalListOfDuplicates.size());
}
}
}
return finalListOfDuplicates;
}
abstract class HashProvider {
abstract String getHashHex(File file) throws IOException ;
}
class Md5HashProvider extends HashProvider {
String getHashHex(File file) throws IOException {
return DigestUtils.md5Hex(new FileInputStream(file));
}
}
class Sha1HashProvider extends HashProvider {
String getHashHex(File file) throws IOException {
return DigestUtils.sha1Hex(new FileInputStream(file));
}
}
}
なぜあなたはそれをハッシュしたいですか？
あなたは2つのファイルが定義することによって、その後同じであることを確認するには、あなたは彼らがあなたがファイルシステム上のメタデータを見ることで知ることができ、その場合には、文字通り同じファイルでない限り、（ファイル全体を読み込む必要があります）。とにかく、ハッシュする理由は、ちょうど彼らの上に読んでいないと、彼らが同じであるかどうかを確認します。ハッシングは、それが非効率的になります。そして、ハッシュが一致する場合でも、あなたはまだファイルが実際に等しい場合は確認されていません。
編集：この答えは、ネットワークについては何も指定し、質問する前に投稿されました。それはちょうど2つのファイルを比較について尋ねました。今、私はファイル間のネットワークホップがある知っていることを、私はちょうどMD5ハッシュを使用して、それを使って行うことだと思います。
あなたはサンバ/ rsyncの開発者が使用するアルゴリズムをチェックアウトすることがあります。私は深さでそれを見ていないが、私はそれがすべての時間を述べ参照してください。どうやらそのかなり良い。
私はそれが送信されたとして、ブロック毎に比較CRCのいくつかの並べ替えを行うだろう、のZmodemのように、古いモデム転送プロトコルを覚えています。 CRC32、私は十分古代史を覚えていれば。それはあなたがやっている正確に何をしない限り、私は、あなたがあなた自身の転送プロトコルを作る示唆はないんだけど、あなたは多分、それは定期的にファイルのブロックをチェックするスポット持つことができ、または多分各8kのブロックのハッシュを行うことのために十分に簡単になりますプロセッサが処理します。 、自分自身を試していません。
