두 파일이 동일한 지 확인하는 가장 빠른 해시 알고리즘은 무엇입니까?
두 파일이 동일한 지 확인하는 데 사용할 해시 함수를 만드는 가장 빠른 방법은 무엇입니까?
보안은 그다지 중요하지 않습니다.
편집 : 네트워크 연결을 통해 파일을 보내고 있으며 양쪽의 파일이 동일한 지 확인합니다.
한 가지 접근 방식은 간단한 CRC-32 알고리즘을 사용하고 CRC 값이 동일하게 비교되는 경우에만 SHA1 또는 더 강력한 것으로 해시를 다시 실행하는 것입니다. 빠른 CRC-32는 언제든지 암호화 보안 해시를 능가합니다.
정말 복잡하거나 느린 해시를 사용하지 않는 한, 디스크에서 데이터를로드하는 것은 해시를 계산하는 것보다 훨씬 더 오래 걸립니다 (RAM 디스크 또는 최고급 SSD를 사용하지 않는 한).
따라서 두 파일을 비교하려면 다음 알고리즘을 사용하십시오.
- 크기 비교
- 날짜 비교 (여기에서주의하십시오 : 잘못된 답을 줄 수 있습니다.이 경우에 해당하는지 테스트해야합니다.)
- 해시 비교
이는 빠른 실패를 허용합니다 (크기가 다른 경우 파일이 다른 것을 알 수 있음).
일을 더 빠르게하기 위해 해시를 한 번 계산하고 파일과 함께 저장할 수 있습니다. 또한 파일 날짜와 크기를이 추가 파일에 저장하여 주 파일이 변경 될 때 해시를 다시 계산하거나 해시 파일을 삭제해야하는시기를 빠르게 알 수 있습니다.
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/ 는 crcutil과 유사하고 관련이있는 것 같습니다 [지시 된 경우 하드웨어 CRC32c 명령어를 사용하도록 컴파일 할 수 있다는 점에서].
"단지 가장 빠른 원시 속도를 원하고"해시 출력의 무작위 배포 품질에별로 신경 쓰지 않는다면 (예를 들어, 작은 집합을 사용하거나 속도가 가장 중요한 경우) 여기에 언급 된 몇 가지 빠른 알고리즘이 있습니다. http : //www.sanmayce.com/Fastest_Hash/ (이 "아주 무작위가 아닌"분포 유형 알고리즘은 경우에 따라 "충분히 양호"하고 매우 빠릅니다). 분명히 FNV1A_Jesteress"긴"문자열의 경우 가장 빠르며 다른 일부는 작은 문자열의 경우 가능합니다. http://locklessinc.com/articles/fast_hash/ 도 관련이있는 것 같습니다. 나는 이것들의 충돌 속성이 무엇인지 조사하지 않았습니다.
특별히 빠르고 코딩이 매우 간단한 MurmurHash를 사용해 볼 수 있습니다. MurmurHash가 일치 항목을 반환하면 더 안전한 두 번째 해시를 원할 수 있습니다.
이러한 유형의 응용 프로그램의 경우 Adler32 는 합리적인 수준의 보안을 갖춘 가장 빠른 알고리즘 일 것입니다. 더 큰 파일의 경우 여러 해시 값을 계산할 수 있습니다 (예 : 파일의 5MB 블록 당 하나씩). 따라서 오류 가능성을 줄일 수 있습니다 (즉, 해시가 동일하지만 파일 내용이 다른 경우). 또한이 다중 해시 값 설정을 통해 해시 계산을 다중 스레드 방식으로 구현할 수 있습니다.
편집 : (Steven Sudit의 발언에 따라)
파일이 작은 경우주의 사항!
Adler32의 "암호화"속성 또는 그 약점은 특히 짧은 메시지에 대해 잘 알려져 있습니다. 이러한 이유로 제안 된 솔루션은 몇 킬로바이트보다 작은 파일에 대해서는 피해야합니다.
결코 적은, 질문에, 영업 이익은 명시 적으로 추구하지 빠른 알고리즘 및 보안에 대한 우려를 포기 . 또한 속도에 대한 탐구 는 "큰"파일을 다루고 있음을 의미 할 수 있습니다.작은 것보다. 이 맥락에서 5Mb의 파일 청크에 병렬로 적용될 수있는 Adler32는 여전히 매우 유효한 답변입니다. Alder32는 단순성과 속도로 유명합니다. 또한 동일한 길이의 CRC보다 낮은 안정성을 유지하면서 4000 바이트가 넘는 메시지에 대해 상당히 허용됩니다.
하나만있는 경우 두 파일 모두의 해시를 생성하기 위해 두 파일을 모두 읽어야한다는 점을 감안할 때 한 번에 적은 양의 파일을 읽고 비교하는 것이 어떻습니까?
CRC에 실패하는 것은 매우 간단한 알고리즘입니다.
여기서 최적화하는 것은 작업에 소요되는 시간입니다. 불행히도 우리는 최적의 솔루션이 무엇인지 알기에 당면한 작업에 대해 충분히 알지 못합니다.
2 개의 임의 파일을 1 회 비교하기위한 것입니까? 그런 다음 크기를 비교하고 IO에 더 적합한 경우 파일을 바이트 단위 (또는 MB 단위)로 간단히 비교합니다.
2 개의 큰 파일 세트 또는 많은 파일 세트를위한 것이며 일회성 연습이 아닙니다. 그러나 자주 발생하는 일이 있으면 각 파일에 대한 해시를 저장해야합니다. 해시는 고유하지 않지만 9 자리 숫자 (32 비트)의 해시는 약 40 억 조합에 적합하며 64 비트 숫자는 약 16 * 10 ^ 18 Quintillion의 다른 파일을 구별하기에 충분합니다. .
적절한 타협은 각 파일에 대해 2 개의 32 비트 해시를 생성하는 것입니다. 하나는 처음 8k, 다른 하나는 1MB + 8k에 대해 단일 64 비트 숫자로 함께칩니다. 기존의 모든 파일을 DB로 카탈로그 화하는 것은 상당히 빠르며이 DB에 대해 후보 파일을 찾는 것도 매우 빠릅니다. 일치하는 항목이 있으면 동일한 지 확인하는 유일한 방법은 전체 파일을 비교하는 것입니다.
나는 사람들에게 그들이 필요하다고 생각하는 것, 또는 원하는 것이 항상 결코 필요한 것은 아닙니다.
어떤 경우 든 각 파일을 완전히 읽어야하므로 (크기가 일치하지 않는 경우 제외) 파일을 모두 읽고 블록별로 비교하십시오.
해시를 사용하면 CPU 사용량 만 얻을 수 있습니다. 아무것도 쓰지 않기 때문에 OS의 캐시는 읽은 데이터를 효과적으로 DROP하므로 Linux에서는 cmp 도구를 사용하십시오.
다음은 중복을 제거하는 사진을 정렬하기 위해 내 개인 프로젝트에서 중복 파일을 찾는 코드입니다. 내 경험에 따르면 처음에는 CRC32와 같은 빠른 해싱 알고리즘을 사용한 다음 MD5 또는 SHA1을 수행하는 것이 훨씬 느 렸고 동일한 크기의 파일 대부분이 실제로 중복되었으므로 해싱을 두 번 실행하는 것이 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));
}
}
}
왜 해시하고 싶습니까?
If you want to make sure that two files are equal then by definition you will have to read the entire file (unless they are literally the same file, in which case you can tell by looking at meta-data on the file system). Anyways, no reason to hash, just read over them and see if they are the same. Hashing will make it less efficient. And even if the hashes match, you still aren't sure if the files really are equal.
Edit: This answer was posted before the question specified anything about a network. It just asked about comparing two files. Now that I know there is a network hop between the files, I would say just use an MD5 hash and be done with it.
you might check out the algorithm that the samba/rsync developers use. I haven't looked at it in depth, but i see it mentioned all the time. apparently its quite good.
Zmodem과 같은 이전 모뎀 전송 프로토콜이 전송 된 각 블록에 대해 일종의 CRC 비교를 수행했던 것을 기억합니다. CRC32, 고대사를 충분히 기억한다면. 정확히 당신이하는 일이 아니라면, 당신 자신의 전송 프로토콜을 만들 것을 제안하는 것이 아닙니다.하지만 당신은 주기적으로 파일 블록을 스팟 체크하도록 할 수도 있고, 각 8k 블록의 해시를 수행하는 것이 충분히 간단 할 것입니다. 처리 할 프로세서. 시도해 보지 않았습니다.
'developer tip' 카테고리의 다른 글
| 특정 색상을 생성하기 위해 필요한 색상 회전을 계산하는 방법은 무엇입니까? (0) | 2020.12.25 |
|---|---|
| 브라우저 창 중앙에 요소를 배치하는 방법은 무엇입니까? (0) | 2020.12.24 |
| System.Windows.Controls.SelectedItemCollection을 캐스팅하는 방법? (0) | 2020.12.24 |
| aspx 파일에 네임 스페이스를 추가하는 방법은 무엇입니까? (0) | 2020.12.24 |
| 자바 스크립트에서 HTML 요소의 스타일 값을 얻는 방법은 무엇입니까? (0) | 2020.12.24 |