你为什么不使用 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;
}
9条答案
按热度按时间jecbmhm31#
反转字符串以获得另一个32位哈希代码,然后将两者合并:
这是伪码;这个
String.reverse()
方法不存在,需要以其他方式实现。xzv2uavs2#
创建一个sha-1散列,然后屏蔽最低的64位。
4sup72z83#
免责声明:如果您希望高效地散列单个自然语言单词,则此解决方案适用。它对于散列较长的文本或包含非字母字符的文本效率很低。
我不知道函数,但这里有一个想法可能会有所帮助:
将64位中的52位用于表示字符串中存在的字母。例如,如果存在“a”,则设置位[0],“b”设置位1,“a”设置位[26]。这样,只有包含完全相同的字母集的文本才会有相同的“签名”。
然后可以使用剩余的12位对字符串长度(或其模值)进行编码,以进一步减少冲突,或者使用传统的哈希函数生成12位哈希代码。
假设您的输入是纯文本,我可以想象这将导致很少的冲突,并且计算(o(n))很便宜。与目前为止的其他解决方案不同,这种方法将问题域考虑在内,以减少冲突-它基于编程pearls中描述的anagram检测器(参见此处)。
r6vfmomb4#
这样做:
dataoutputstream允许您编写原语和字符串,并将它们作为字节输出。将bytearrayoutputstream Package 在其中可以让您写入字节数组,它与messagedigest很好地集成。您可以从这里列出的任何算法中进行选择。
最后,biginteger将允许您将输出字节转换为更易于使用的数字。md5和sha1算法都产生128位哈希,因此如果需要64位,可以直接截断。
sha1应该很好地散列几乎所有内容,并且很少发生冲突(它是128位的)。这是从java开始的,但我不确定它是如何实现的。它实际上可能相当快。在我的实现中,它在几个领域都起作用:只需将它们全部推到
DataOutputStream
你可以走了。您甚至可以使用反射和注解(也许@HashComponent(order=1)
显示哪些字段以什么顺序进入散列)。它有一个128位的变种,我想你会发现它没有你想象的那么多cpu使用。我已经使用了这样的代码来获取大型数据集(到目前为止可能有数十亿个对象)的哈希值,以便能够在许多后端存储中对它们进行切分。不管你需要它做什么,它都应该有用。请注意,我想您可能只想打电话
MessageDigest.getInstance()
偶尔clone()
从那时起:iirc克隆的速度要快得多。wecizke35#
为什么不使用crc64多项式呢。这些是合理有效的和优化的,以确保所有位都被计数并分布在结果空间中。
如果你用谷歌搜索“crc64 java”,网上有很多可用的实现
vwhgwdsa6#
今天(2018年)的答案。西普哈什。
它将比这里的大多数答案快得多,而且比所有答案的质量都要高得多。
Guava图书馆有一个:https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/hashing.html#siphash24--
k2fxgqgv7#
你为什么不使用
long
默认值的变体String.hashCode()
(其中一些真正聪明的家伙肯定会努力提高效率——更不用说成千上万的开发人员已经在看这段代码了)?如果你想找更多的位子,你可能需要一个
BigInteger
编辑:正如我在对@brianegge答案的评论中所提到的,对于超过32位的散列,没有太多的用例,对于超过64位的散列,很可能没有一个用例:
我可以想象一个巨大的哈希表分布在几十个服务器上,可能存储着数百亿个Map。对于这种情况,@brianegge在这里仍然有一个有效点:32位允许2^32(约43亿)个不同的散列键。假设一个强大的算法,你应该仍然有相当多的碰撞。有了64位(18446744073亿个不同的密钥),您的存储量肯定会减少,不管您需要它做什么疯狂的场景。不过,考虑128位密钥(340282366920938463463374607431亿个可能的密钥)的用例几乎是不可能的。
要组合多个字段的哈希,只需将一个与素数进行异或相乘,然后将它们相加:
小素数用于避免交换值的哈希码相等,即{foo',bar}和{bar',foo}不相等,应该有不同的哈希码。xor是错误的,因为如果两个值相等,则返回0。因此,{foo',foo}和{bar',bar}将具有相同的哈希代码。
w46czmvw8#
是的,前32位将是0,但在遇到哈希冲突问题之前,可能会耗尽硬件资源。字符串中的hashcode非常有效,并且经过了很好的测试。
我认为上面的更新满足了最简单的可能工作的东西,但是,我同意@sfussenegger扩展现有字符串hashcode的想法。
除了为您的字符串提供一个好的哈希代码之外,您可能还需要考虑在实现中重新设置哈希代码的格式。如果您的存储被其他开发人员使用,或者与其他类型一起使用,这可以帮助您分发密钥。例如,java的hashmap基于两个长度哈希表的幂,因此它添加了这个函数以确保低位得到充分分布。
fhity93d9#
你看apache commons lang吗?
但是对于64位(和128位)您需要一些技巧:joshua bloch在《有效java》一书中列出的规则可以帮助您轻松创建64位哈希(只需使用long而不是int)。对于128位,您需要额外的黑客。。。