Java中用于文本string的64位散列函数是什么？
我在找一个哈希函数：
- 很好地扫描文本string （例如很less碰撞）
- 用Java编写，并被广泛使用
- 奖金：工作在几个领域（而不是我连接他们和应用连接的string散列）
- 奖金：有一个128位的变种。
- 奖金：不占用CPU。
为什么不使用默认String.hashCode()一个long变体（其中一些真正聪明的人肯定会努力使其高效 – 而不是提到已经看过这个代码的成千上万的开发人员的眼睛）？
// 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; }
如果你正在寻找更多的位，你可以使用 Edit： BigInteger
正如我在@brianegge的回答中所提到的那样，对于超过32位的哈希，没有太多的用例，对于超过64位的哈希，很可能没有一个哈希。
我可以想象一个巨大的哈希表分布在几十台服务器上，可能会存储数百亿的映射。 对于这种情况，@brianegge在这里仍然有一个有效的点：32位允许2 ^ 32（大约43亿）不同的散列键。 假设一个强大的algorithm，你应该仍然有很less的碰撞。 64位（18,446,744,073十亿不同的密钥），你一定会保存，无论你需要什么疯狂的情况。 想想128位密钥的使用情况（340,282,366,920,938,463,463,374,674,347,431亿个可能的密钥）几乎是不可能的。
要结合几个字段的散列，只需做一个XOR乘以一个素数并添加它们：
long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2);
小素数是在那里，以避免相同的散列码转换值，即{'foo'，'bar'}和{'bar'，'foo'}是不相等的，应该有一个不同的哈希码。 如果两个值相等，则XOR返回0。 因此，{'foo'，'foo'}和{'bar'，'bar'}将具有相同的哈希码。
创build一个SHA-1散列 ，然后掩盖最低的64位。
long hash = string.hashCode();
是的，前32位将是0，但在遇到散列冲突问题之前，您可能会用尽硬件资源。 String中的hashCode非常有效并且经过了很好的testing。
更新我认为上述满足最简单的事情可能工作 ，但是，我同意@sfussenegger扩展现有的String hashCode的想法。
除了为您的string提供了一个好的hashCode之外，您可能还想考虑在您的实现中重新使用哈希码。 如果您的存储由其他开发人员使用，或者与其他types一起使用，则可以帮助分发您的密钥。 例如，Java的HashMap是基于两个长度的哈希表，所以它增加了这个function，以确保低位的分布充分。
h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);
为什么不使用CRC64多项式。 这些都是相当高效和优化，以确保所有的位都被计算和分布在结果空间。
网上有很多实现，如果你google“CRC64 Java”
做这样的事情：
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可以编写基元和string，并将它们输出为字节。 在其中包装一个ByteArrayOutputStream可以让你写入一个与MessageDigest完美集成的字节数组。 你可以从这里列出的任何algorithm中挑选。
最后， BigInteger将让你把输出字节变成一个更容易使用的数字。 MD5和SHA1algorithm都产生128位哈希，所以如果你需要64位，你可以截断。
SHA1应该散列几乎任何东西，并与罕见的冲突（这是128位）。 这从Java的作品，但我不知道它是如何实现的。 它实际上可能相当快。 它在我的实现中的几个字段上工作：只需将它们全部推送到DataOutputStream然后您就可以继续。 你甚至可以使用reflection和注解（可能是@HashComponent(order=1)来显示哪些字段进入哈希，以什么顺序）。 它有一个128位的变体，我想你会发现它不会像你想象的那样使用尽可能多的CPU。
我已经使用这样的代码来获取大量数据集的散列（现在可能是数十亿个对象），以便能够将它们分散到许多后端存储中。 它应该适合你需要的任何东西。 请注意，我认为你可能只想调用MessageDigest.getInstance()一次，然后clone() ：IIRC的克隆速度要快得多。
反转string以获得另一个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()方法不存在，需要以其他方式实现。
你看阿帕奇的普通话吗？
但对于64位（和128位），你需要一些技巧：约书亚·布洛赫（Joshua Bloch）在“有效的Java”（Effective Java）一书中规定的规则可以帮助你轻松创build64位散列（只使用long而不是int）。 对于128位，你需要额外的黑客…
免责声明：如果您希望高效地散列单个自然语言词汇，则此解决scheme适用。 散列较长的文本或包含非字母字符的文本是低效的。
我不知道一个function，但这里有一个想法可能会有所帮助：
- 将64位中的52位分配来表示string中存在哪些字母。 例如，如果存在“a”，则设置位[0]，将'b'设置为位1 ，将'A'设为位[26]。 这样，只有包含完全相同的一组字母的文本才具有相同的“签名”。
然后，您可以使用剩余的12位来对string长度（或其模值）进行编码，以进一步减less冲突，或使用传统的散列函数生成12位的散列码。
假设你的input是纯文本的，我可以想象这将导致非常less的碰撞，并且计算起来便宜（O（n））。 与迄今为止的其他解决scheme不同，这种方法将问题域考虑在内，以减less冲突 – 它基于编程珍珠（参见这里 ）中描述的Anagram探测器。
