创建用于检查两个文件是否相等的哈希函数的最快方法是什么？
安全性不是很重要。
编辑：我通过网络连接发送文件，并确保双方的文件是平等的
问问题
77492 次
12 回答
55
除非您使用非常复杂和/或缓慢的哈希，否则从磁盘加载数据将比计算哈希花费更长的时间（除非您使用 RAM 磁盘或高端 SSD）。
因此，要比较两个文件，请使用以下算法：
- 比较尺寸
- 比较日期（这里要小心：这可能会给你错误的答案；你必须测试这是否适合你）
- 比较哈希
这允许快速失败（如果大小不同，您知道文件不同）。
为了使事情变得更快，您可以计算一次哈希并将其与文件一起保存。还将文件日期和大小保存到这个额外的文件中，以便您在主文件更改时快速知道何时必须重新计算散列或删除散列文件。
于 2009-11-19T08:14:27.333 回答
35
一种方法可能是使用简单的 CRC-32 算法，并且只有当 CRC 值比较相等时，才使用 SHA1 或更稳健的方法重新运行散列。快速 CRC-32 在任何一天都将胜过加密安全哈希。
于 2009-11-19T07:55:00.200 回答
21
xxhash 声称自己非常快速和强大，碰撞明智：
http://cyan4973.github.io/xxHash/
总体而言，有一个 64 位变体在 64 位处理器上的运行速度比 32 位处理器“更快”，但在 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个任意文件吗？然后比较大小，然后简单地比较文件，逐字节（或逐字节）如果这对您的 IO 更好。
如果是2组大文件，或者多组文件，也不是一次性练习。但是会经常发生的事情，那么应该为每个文件存储哈希值。散列永远不是唯一的，但是具有 9 位数字（32 位）的散列对于大约 40 亿个组合来说是好的，而 64 位的数字足以区分一些 16 * 10^18 Quintillion 不同的文件.
一个不错的折衷方案是为每个文件生成 2 个 32 位哈希，一个用于前 8k，另一个用于 1MB+8k，将它们作为一个 64 位数字拼接在一起。将所有现有文件编入数据库应该相当快，并且针对该数据库查找候选文件也应该非常快。一旦匹配，确定它们是否相同的唯一方法是比较整个文件。
我相信给人们他们需要的东西，这并不总是他们认为他们需要的东西，或者他们想要的东西。
于 2014-12-14T20:37:32.373 回答
3
你可以试试MurmurHash，它专为快速而设计，而且代码非常简单。如果 MurmurHash 返回匹配项，您可能需要第二个更安全的哈希，只是为了确定。
于 2009-11-19T08:06:14.417 回答
3
对于此类应用程序，Adler32可能是最快的算法，具有合理的安全级别。对于较大的文件，您可以计算多个散列值，例如每个 5 Mb 文件块一个，从而减少出错的机会（即散列相同但文件内容不同的情况）。此外，这种多散列值设置可以允许散列的计算以多线程方式实现。
编辑：（根据 Steven Sudit 的评论）
如果文件很小，请注意！
Adler32 的“加密”属性，或者说它的弱点，尤其是短消息是众所周知的。因此，对于小于几千字节的文件，应避免使用建议的解决方案。
无论如何，在这个问题中，OP 明确地寻求一种快速算法并放弃对安全性的担忧。此外，对速度的追求可能暗示一个人正在处理“大”文件而不是小的。在这种情况下，可能并行应用于 5Mb 文件块的 Adler32 仍然是一个非常有效的答案。Alder32 以其简单和快速而闻名。此外，它的可靠性虽然低于相同长度的 CRC，但对于超过 4000 字节的消息来说是完全可以接受的。
于 2009-11-19T08:07:04.780 回答
2
在任何情况下，您都应该完全读取每个文件（大小不匹配的情况除外），因此只需读取两个文件并逐块比较。
使用哈希只会增加 CPU 使用率，仅此而已。由于你不写任何东西，操作系统的缓存会有效地丢弃你读取的数据，所以，在 Linux 下，只需使用cmp 工具
于 2013-02-13T16:41:05.833 回答
2
如果它只是一个关闭，那么鉴于您必须读取这两个文件以生成它们的哈希，为什么不一次只读取少量并进行比较呢？
CRC失败是一个非常简单的算法。
于 2009-11-19T07:56:01.723 回答
1
以下是从我的个人项目中查找重复文件以对图片进行排序的代码，这也删除了重复项。根据我的经验，首先使用 CRC32 之类的快速散列算法，然后执行 MD5 或 SHA1 甚至更慢，并且没有任何改进，因为大多数具有相同大小的文件确实是重复的，因此从 CPU 时间的角度来看，运行两次散列更昂贵，这种方法可能不适用于所有类型的项目，但对于图像文件绝对正确。在这里，我只对具有相同大小的文件进行 MD5 或 SHA1 散列。
PS：它依赖于 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));
}
}
}
于 2013-02-14T06:14:51.297 回答
1
你为什么要散列它？
如果您想确保两个文件相等，那么根据定义，您将必须读取整个文件（除非它们实际上是同一个文件，在这种情况下，您可以通过查看文件系统上的元数据来判断）。无论如何，没有理由散列，只需阅读它们，看看它们是否相同。散列会降低效率。即使哈希匹配，您仍然不确定文件是否真的相等。
编辑：此答案是在问题指定有关网络的任何内容之前发布的。它只是询问比较两个文件。现在我知道文件之间存在网络跃点，我想说只使用 MD5 哈希并完成它。
于 2009-11-19T07:55:23.550 回答
1
您可以查看 samba/rsync 开发人员使用的算法。我没有深入研究它，但我看到它一直被提及。显然它相当不错。
于 2010-08-13T01:51:40.923 回答
0
我记得旧的调制解调器传输协议，如 Zmodem，会在每个块发送时进行某种 CRC 比较。CRC32，如果我对古代历史的记忆足够好的话。我不建议您制定自己的传输协议，除非这正是您正在做的事情，但您可以让它定期抽查文件的一个块，或者对每个 8k 块进行哈希处理对处理器来处理。没试过，我自己。
于 2019-01-03T05:15:07.577 回答