2つのファイルが等しいかどうかをチェックするために使用されるハッシュ関数を作成する最も速い方法は何ですか？
セキュリティはそれほど重要ではありません。
編集：ネットワーク接続を介してファイルを送信していますが、両側のファイルが等しいことを確認します
77492 次
12 に答える
55
非常に複雑なハッシュや低速のハッシュを使用している場合を除き、ディスクからのデータのロードには、ハッシュの計算よりもはるかに長い時間がかかります（RAMディスクまたはトップエンドSSDを使用している場合を除く）。
したがって、2つのファイルを比較するには、次のアルゴリズムを使用します。
- サイズを比較する
- 日付を比較します（ここで注意してください：これは間違った答えを与える可能性があります;これがあなたに当てはまるかどうかをテストする必要があります）
- ハッシュを比較する
これにより、迅速な失敗が可能になります（サイズが異なる場合は、ファイルが異なることがわかります）。
さらに高速にするために、ハッシュを1回計算して、ファイルと一緒に保存することができます。また、ファイルの日付とサイズをこの追加ファイルに保存して、ハッシュを再計算する必要がある場合や、メインファイルが変更されたときにハッシュファイルを削除する必要がある場合をすばやく把握できるようにします。
于 2009-11-19T08:14:27.333 に答える
35
1つのアプローチは、単純なCRC-32アルゴリズムを使用することであり、CRC値が等しい場合にのみ、SHA1またはより堅牢なものでハッシュを再実行します。高速CRC-32は、いつでも暗号的に安全なハッシュよりも優れたパフォーマンスを発揮します。
于 2009-11-19T07:55:00.200 に答える
21
xxhashは、衝突に関して非常に高速で強力であると主張しています。
http://cyan4973.github.io/xxHash/
全体として、32ビットプロセッサよりも64ビットプロセッサで「さらに高速」に実行される64ビットバリアントがありますが、32ビットプロセッサでは低速です（図を参照）。
http://code.google.com/p/crcutilも非常に高速であると言われています（そして、存在する場合はハードウェアCRC命令を利用します。これはおそらく非常に高速ですが、それらをサポートするハードウェアがない場合はそうではありません。できるだけ速く）。CRC32cがxxHashと同じくらい（衝突に関して）ハッシュに優れているかどうかわからない...
https://code.google.com/p/cityhash/は、crcutilに類似しており、関連しているようです[指示された場合、ハードウェアCRC32c命令を使用するようにコンパイルできます]。
「最速の生の速度が必要」で、ハッシュ出力のランダムな分散の品質をあまり気にしない場合（たとえば、小さなセットの場合、または速度が最優先される場合）、ここで言及されているいくつかの高速アルゴリズムがあります：http ：//www.sanmayce.com/Fastest_Hash/（これらの「完全にランダムではない」分散タイプのアルゴリズムは、場合によっては「十分」で非常に高速です）。どうやら FNV1A_Jesteress「長い」文字列の場合は最速であり、他のいくつかはおそらく小さな文字列の場合です。 http://locklessinc.com/articles/fast_hash/も関連しているようです。私はこれらの衝突特性が何であるかを見るために研究しませんでした。
最新のホットさはhttps://github.com/erthink/t1haとhttps://github.com/wangyi-fudan/wyhashのようで、xxhashにもわずかに更新されたバージョンがあります。
于 2012-07-10T21:43:06.227 に答える
4
ここで最適化しているのは、タスクに費やされた時間です。残念ながら、私たちは目前のタスクについて十分に理解しておらず、最適なソリューションがどうあるべきかを知ることができません。
任意の2つのファイルを1回だけ比較するためですか？次に、サイズを比較し、その後、IOに適している場合は、ファイルをバイトごと（またはmbごと）に比較します。
2つの大きなファイルのセット、または多数のファイルのセット用であり、1回限りの演習ではない場合。しかし、頻繁に発生することがある場合は、ファイルごとにハッシュを保存する必要があります。ハッシュが一意になることはありませんが、たとえば9桁（32ビット）のハッシュは約40億の組み合わせに適しており、64ビットの数値は16 * 10^18クィンティリオンの異なるファイルを区別するのに十分です。 。
適切な妥協案は、ファイルごとに2つの32ビットハッシュを生成することです。1つは最初の8k用、もう1つは1MB + 8k用で、単一の64ビット数としてそれらを一緒に叩きます。既存のすべてのファイルをDBにカタログ化するのはかなり迅速であり、このDBに対して候補ファイルを検索するのも非常に迅速である必要があります。一致するものがあると、それらが同じであるかどうかを判断する唯一の方法は、ファイル全体を比較することです。
私は人々に彼らが必要としているものを与えることを信じていますが、それは必ずしも彼らが彼らが必要と思っているもの、または欲しいものであるとは限りません。
于 2014-12-14T20:37:32.373 に答える
3
MurmurHashを試すことができます。これは、高速になるように特別に設計されており、コーディングが非常に簡単です。念のために言っておきますが、MurmurHashが一致を返す場合は、2番目のより安全なハッシュを使用することをお勧めします。
于 2009-11-19T08:06:14.417 に答える
3
このタイプのアプリケーションの場合、Adler32はおそらく最速のアルゴリズムであり、妥当なレベルのセキュリティを備えています。より大きなファイルの場合、複数のハッシュ値を計算できます。たとえば、ファイルの5 Mbのブロックごとに1つであるため、エラーの可能性が低くなります（つまり、ハッシュが同じでファイルの内容が異なる場合）。さらに、このマルチハッシュ値の設定により、ハッシュの計算をマルチスレッド方式で実装できる場合があります。
編集:(スティーブン・スディットの発言に続いて）
ファイルが小さい場合は注意が必要です！
Adler32の「暗号化」プロパティ、またはむしろその弱点は、特に短いメッセージでよく知られています。このため、提案されたソリューションは、数キロバイト未満のファイルでは避ける必要があります。
それでもなお、質問では、OPは明示的に高速アルゴリズムを求め、セキュリティに関する懸念を放棄します。さらに、速度の追求は、「大きな」ファイルを扱っていることを意味する可能性があります小さいものではなく。このコンテキストでは、Adler32は、たとえば5Mbのファイルチャンクに並行して適用される可能性があり、非常に有効な答えのままです。Alder32は、そのシンプルさとスピードで定評があります。また、その信頼性は、同じ長さのCRCの信頼性よりも低いままですが、4000バイトを超えるメッセージには十分に受け入れられます。
于 2009-11-19T08:07:04.780 に答える
2
1回限りの場合は、両方のファイルを読み取って両方のハッシュを生成する必要があることを考えると、一度に少量ずつ読み取って比較してみませんか？
そのCRCに失敗することは、非常に単純なアルゴリズムです。
于 2009-11-19T07:56:01.723 に答える
2
いずれの場合も、各ファイルを完全に読み取る必要があるため（サイズが一致しない場合を除く）、両方のファイルを読み取り、ブロックごとに比較してください。
ハッシュを使用すると、CPU使用率が上がるだけで、それ以上のことはありません。何も書き込まないため、OSのキャッシュは、読み取ったデータを効果的にドロップします。したがって、Linuxでは、cmpツールを使用するだけです。
于 2013-02-13T16:41:05.833 に答える
1
なぜそれをハッシュしたいのですか？
2つのファイルが等しいことを確認したい場合は、定義上、ファイル全体を読み取る必要があります（文字通り同じファイルである場合を除きます。この場合、ファイルシステムのメタデータを確認することでわかります）。とにかく、ハッシュする理由はありません。それらを読んで、同じかどうかを確認してください。ハッシュを使用すると、効率が低下します。また、ハッシュが一致していても、ファイルが本当に等しいかどうかはわかりません。
編集：この回答は、質問がネットワークについて何かを指定する前に投稿されました。2つのファイルの比較について尋ねただけです。ファイル間にネットワークホップがあることがわかったので、MD5ハッシュを使用してそれで完了します。
于 2009-11-19T07:55:23.550 に答える
1
samba/rsync開発者が使用するアルゴリズムを確認してください。私はそれを深く見ていませんが、私はそれがいつも言及されているのを見ます。どうやらそれはかなり良いです。
于 2010-08-13T01:51:40.923 に答える
1
以下は、私の個人的なプロジェクトから重複ファイルを見つけて写真を並べ替え、重複を削除するコードです。私の経験によると、最初にCRC32のような高速ハッシュアルゴリズムを使用してからMD5またはSHA1を実行するのはさらに遅く、同じサイズのファイルのほとんどが実際に複製されたため、cpu時間の観点からハッシュを2回実行する方がコストがかかるため改善されませんでした。 、このアプローチはすべてのタイプのプロジェクトに適しているとは限りませんが、画像ファイルには間違いなく当てはまります。ここでは、同じサイズのファイルに対してのみMD5またはSHA1ハッシュを実行しています。
PS：ハッシュを効率的に生成するには、ApacheCommonsコーデックに依存します。
使用例：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));
}
}
}
于 2013-02-14T06:14:51.297 に答える
0
Zmodemのような古いモデム転送プロトコルは、送信されたブロックごとにある種のCRC比較を行うことを覚えています。CRC32、私が古代の歴史を十分に覚えているなら。自分で転送プロトコルを作成することはお勧めしませんが、それが正確に実行している場合を除きますが、ファイルのブロックを定期的にスポットチェックするか、各8kブロックのハッシュを実行するだけで十分です。処理するプロセッサ。私自身、試したことはありません。
于 2019-01-03T05:15:07.577 に答える