我正在寻找一个哈希函数：
- 很好地散列文本字符串（例如很少的冲突）
- 用Java编写，并被广泛使用
- 奖励：适用于多个字段（而不是我将它们连接起来并在连接的字符串上应用哈希）
- 奖励：有一个 128 位的变体。
- 奖励：不是 CPU 密集型的。
问问题
56278 次
9 回答
73
你为什么不使用long默认的变体String.hashCode()（一些非常聪明的人肯定会努力提高它的效率——更不用说已经看过这段代码的成千上万的开发人员了）？
// adapted from String.hashCode()
public static long hash(String string) {
long h = 1125899906842597L; // prime
int len = string.length();
for (int i = 0; i < len; i++) {
h = 31*h + string.charAt(i);
}
return h;
}
如果您正在寻找更多位，您可能会使用
编辑：BigInteger
正如我在对@brianegge 的回答的评论中提到的那样，对于超过 32 位的哈希，没有太多用例，对于超过 64 位的哈希，很可能没有一个用例：
我可以想象一个分布在数十台服务器上的巨大哈希表，可能存储数百亿个映射。对于这种情况，@brianegge 仍然有一个有效的观点：32 位允许 2^32（约 43 亿）个不同的哈希键。假设一个强大的算法，你应该仍然有相当少的碰撞。使用 64 位（18,446,744,073 亿个不同的密钥），无论您需要什么疯狂的场景，您都可以放心。不过，考虑 128 位密钥（340,282,366,920,938,463,463,374,607,431 亿个可能的密钥）的用例几乎是不可能的。
要组合多个字段的哈希，只需执行 XOR将 1 与素数相乘并将它们相加：
long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2);
小素数用于避免切换值的哈希码相等，即 {'foo','bar'} 和 {'bar','foo'} 不相等，应该有不同的哈希码。XOR 不好，因为如果两个值相等，它会返回 0。因此，{'foo','foo'} 和 {'bar','bar'} 将具有相同的哈希码。
于 2009-11-02T11:00:52.767 回答
5
今天的答案（2018 年）。西普哈希。
它比这里的大多数答案要快得多，而且质量比所有答案都要高得多。
于 2018-01-16T06:43:39.363 回答
4
创建一个 SHA-1 哈希，然后屏蔽掉最低的 64 位。
于 2009-11-02T10:49:51.357 回答
2
long hash = string.hashCode();
是的，前 32 位将为 0，但在遇到哈希冲突问题之前，您可能会耗尽硬件资源。String 中的 hashCode 非常有效且经过良好测试。
更新 我认为以上满足了可能可行的最简单的事情，但是，我同意@sfussenegger 扩展现有字符串 hashCode 的想法。
除了为您的 String 提供一个好的 hashCode 之外，您可能还需要考虑在您的实现中重新散列哈希代码。如果您的存储被其他开发人员使用，或与其他类型一起使用，这有助于分发您的密钥。例如，Java 的 HashMap 是基于 2 的幂的长度哈希表，所以它添加了这个函数来确保低位充分分布。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
于 2009-11-02T11:42:56.463 回答
2
为什么不使用 CRC64 多项式。这些是相当有效和优化的，以确保所有位都被计算并分布在结果空间中。
如果你用谷歌搜索“CRC64 Java”，网上有很多可用的实现
于 2010-06-03T10:15:49.887 回答
1
做这样的事情：
import java.io.ByteArrayOutputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public class Test {
public static void main(String[] args) throws NoSuchAlgorithmException,
IOException {
ByteArrayOutputStream baos = new ByteArrayOutputStream();
DataOutputStream dos = new DataOutputStream(baos);
try {
MessageDigest md = MessageDigest.getInstance("MD5");
SomeObject testObject = new SomeObject();
dos.writeInt(testObject.count);
dos.writeLong(testObject.product);
dos.writeDouble(testObject.stdDev);
dos.writeUTF(testObject.name);
dos.writeChar(testObject.delimiter);
dos.flush();
byte[] hashBytes = md.digest(baos.toByteArray());
BigInteger testObjectHash = new BigInteger(hashBytes);
System.out.println("Hash " + testObjectHash);
} finally {
dos.close();
}
}
private static class SomeObject {
private int count = 200;
private long product = 1235134123l;
private double stdDev = 12343521.456d;
private String name = "Test Name";
private char delimiter = '\n';
}
}
DataOutputStream允许您编写原语和字符串并将它们作为字节输出。在其中包装一个ByteArrayOutputStream可以让您写入一个字节数组，该数组与MessageDigest很好地集成。您可以从此处列出的任何算法中进行选择。
最后BigInteger将让您将输出字节转换为更易于使用的数字。MD5 和 SHA1 算法都产生 128 位哈希，所以如果你需要 64，你可以截断。
SHA1 几乎可以很好地散列任何东西，并且很少发生冲突（它是 128 位的）。这适用于 Java，但我不确定它是如何实现的。它实际上可能相当快。它适用于我的实现中的几个领域：只需将它们全部推送到DataOutputStream您就可以开始了。您甚至可以使用反射和注释@HashComponent(order=1)来做到这一点（也许显示哪些字段进入散列以及以什么顺序）。它有一个 128 位的变体，我想你会发现它使用的 CPU 没有你想象的那么多。
我已经使用这样的代码来获取庞大数据集（现在可能有数十亿个对象）的哈希值，以便能够在许多后端存储中对它们进行分片。它应该适用于您需要的任何东西。请注意，我认为您可能只想调用MessageDigest.getInstance()一次，然后clone()从那时起：IIRC 的克隆速度要快得多。
于 2010-06-03T10:55:15.157 回答
1
反转字符串以获取另一个 32 位哈希码，然后将两者结合起来：
String s = "astring";
long upper = ( (long) s.hashCode() ) << 32;
long lower = ( (long) s.reverse().hashCode() ) - ( (long) Integer.MIN_VALUE );
long hash64 = upper + lower;
这是伪代码；该String.reverse()方法不存在，需要以其他方式实现。
于 2014-08-06T07:17:08.573 回答
0
但是对于 64 位（和 128 位），您需要一些技巧：Joshua Bloch 的《Effective Java》一书中列出的规则可帮助您轻松创建 64 位哈希（只需使用 long 而不是 int）。对于 128 位，您需要额外的技巧...
于 2009-11-02T11:12:42.297 回答
-2
免责声明：如果您希望有效地散列单个自然语言单词，则此解决方案适用。散列较长的文本或包含非字母字符的文本效率低下。
我不知道一个功能，但这里有一个可能有帮助的想法：
- 将 64 位中的 52 位专用于表示字符串中存在哪些字母。例如，如果存在“a”，您将设置位 [0]，为“b”设置位1，为“A”设置位 [26]。这样，只有包含完全相同字母集的文本才会具有相同的“签名”。
然后，您可以使用剩余的 12 位对字符串长度（或它的模值）进行编码以进一步减少冲突，或使用传统的散列函数生成 12 位 hashCode。
假设您的输入是纯文本的，我可以想象这将导致很少的冲突并且计算成本低廉（O（n））。 与迄今为止的其他解决方案不同，这种方法考虑了问题域以减少冲突- 它基于 Programming Pearls 中描述的 Anagram Detector（参见此处）。
于 2009-11-02T10:47:43.807 回答