我正在寻找一个散列函数来散列字符串。出于我的目的(在导入过程中识别更改的对象),它应该具有以下属性:
快
可以增量使用,即我可以这样使用它:
Hasher h = new Hasher(); h.add("somestring"); h.add("another part"); h.add("eveno more"); Long hash = h.create();
在整个过程中不会影响其他属性或将字符串保留在内存中。
防止碰撞。如果我余生每天比较不同字符串的两个哈希值 100 万次,那么发生冲突的风险应该可以忽略不计。
它不必能够防止恶意尝试制造冲突。
我可以使用什么算法?优先考虑在 Java 中已有免费实现的算法。
澄清
哈希值不必很长。例如,一个字符串就可以了。
要哈希的数据将来自文件或数据库,其中包含许多 10MB 或最多几 GB 的数据,这些数据将分布到不同的哈希中。因此,将完整的字符串保留在内存中并不是一个真正的选择。
最佳答案
哈希是一个明智的主题,很难根据您的问题推荐任何此类哈希。您可能想在 https://security.stackexchange.com/ 上问这个问题获取有关哈希在某些用例中的可用性的专家意见。
到目前为止我的理解是,大多数哈希都是在核心中增量实现的;另一方面,执行时间并不那么容易预测。
我向您展示了两个 Hasher
实现,它们依赖于“Java 中现有的自由实现”。这两种实现的构造方式都是您可以在调用 add()
之前任意拆分 String
并获得相同的结果,只要您不更改字符串的顺序即可其中的字符:
import java.math.BigInteger;
import java.nio.charset.Charset;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;
/**
* Created for https://stackoverflow.com/q/26928529/1266906.
*/
public class Hashs {
public static class JavaHasher {
private int hashCode;
public JavaHasher() {
hashCode = 0;
}
public void add(String value) {
hashCode = 31 * hashCode + value.hashCode();
}
public int create() {
return hashCode;
}
}
public static class ShaHasher {
public static final Charset UTF_8 = Charset.forName("UTF-8");
private final MessageDigest messageDigest;
public ShaHasher() throws NoSuchAlgorithmException {
messageDigest = MessageDigest.getInstance("SHA-256");
}
public void add(String value) {
messageDigest.update(value.getBytes(UTF_8));
}
public byte[] create() {
return messageDigest.digest();
}
}
public static void main(String[] args) {
javaHash();
try {
shaHash();
} catch (NoSuchAlgorithmException e) {
e.printStackTrace(); // TODO: implement catch
}
}
private static void javaHash() {
JavaHasher h = new JavaHasher();
h.add("somestring");
h.add("another part");
h.add("eveno more");
int hash = h.create();
System.out.println(hash);
}
private static void shaHash() throws NoSuchAlgorithmException {
ShaHasher h = new ShaHasher();
h.add("somestring");
h.add("another part");
h.add("eveno more");
byte[] hash = h.create();
System.out.println(Arrays.toString(hash));
System.out.println(new BigInteger(1, hash));
}
}
这里显然“SHA-256”可以替换为其他常见的哈希算法; Java 提供了相当多的此类工具。
现在您调用 Long
作为返回值,这意味着您正在寻找 64 位哈希。如果这确实是故意的,请查看 What is a good 64bit hash function in Java for textual strings? 的答案。接受的答案是 JavaHasher
的一个轻微变体,因为 String.hashCode()
执行基本相同的计算,但溢出边界较低:
public static class Java64Hasher {
private long hashCode;
public Java64Hasher() {
hashCode = 1125899906842597L;
}
public void add(CharSequence value) {
final int len = value.length();
for(int i = 0; i < len; i++) {
hashCode = 31*hashCode + value.charAt(i);
}
}
public long create() {
return hashCode;
}
}
表达你的观点:
快
由于 SHA-256 比其他两种方法慢,我仍然认为所有三种提出的方法都很快。
可以增量使用,而不会影响其他属性或在整个过程中将字符串保留在内存中。
我不能保证 ShaHasher 的该属性,因为我知道它是基于 block 的,并且我缺少源代码。不过我建议最多一个 block 、哈希和一些内部状态被存管。另外两个显然只存储调用
add()
之间的部分哈希值
防止碰撞。如果我余生每天比较不同字符串的两个哈希值 100 万次,那么发生冲突的风险应该可以忽略不计。
每个哈希值都存在冲突。考虑到良好的分布,散列的位大小是冲突发生频率的主要因素。
JavaHasher
用于例如HashMap 似乎“无冲突”,足以将相似的键分布在彼此相距很远的地方。至于任何更深入的分析:请自行测试或询问本地的安全工程师 - 抱歉。
我希望这提供了一个良好的起点,细节可能主要基于意见。
关于java - Java中的快速增量哈希,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26928529/