java中用于文本字符串的64位哈希函数是什么?

0tdrvxhp  于 2021-07-05  发布在  Java
关注(0)|答案(9)|浏览(415)

我在找一个哈希函数:
很好地散列文本字符串(例如,很少发生冲突)
是用java编写的,并且被广泛使用
好处:可以处理多个字段(而不是我将它们串联起来并对串联的字符串应用哈希)
优点:有一个128位的变体。
优点:不是cpu密集型。

jecbmhm3

jecbmhm31#

反转字符串以获得另一个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() 方法不存在,需要以其他方式实现。

xzv2uavs

xzv2uavs2#

创建一个sha-1散列,然后屏蔽最低的64位。

4sup72z8

4sup72z83#

免责声明:如果您希望高效地散列单个自然语言单词,则此解决方案适用。它对于散列较长的文本或包含非字母字符的文本效率很低。
我不知道函数,但这里有一个想法可能会有所帮助:
将64位中的52位用于表示字符串中存在的字母。例如,如果存在“a”,则设置位[0],“b”设置位1,“a”设置位[26]。这样,只有包含完全相同的字母集的文本才会有相同的“签名”。
然后可以使用剩余的12位对字符串长度(或其模值)进行编码,以进一步减少冲突,或者使用传统的哈希函数生成12位哈希代码。
假设您的输入是纯文本,我可以想象这将导致很少的冲突,并且计算(o(n))很便宜。与目前为止的其他解决方案不同,这种方法将问题域考虑在内,以减少冲突-它基于编程pearls中描述的anagram检测器(参见此处)。

r6vfmomb

r6vfmomb4#

这样做:

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 Package 在其中可以让您写入字节数组,它与messagedigest很好地集成。您可以从这里列出的任何算法中进行选择。
最后,biginteger将允许您将输出字节转换为更易于使用的数字。md5和sha1算法都产生128位哈希,因此如果需要64位,可以直接截断。
sha1应该很好地散列几乎所有内容,并且很少发生冲突(它是128位的)。这是从java开始的,但我不确定它是如何实现的。它实际上可能相当快。在我的实现中,它在几个领域都起作用:只需将它们全部推到 DataOutputStream 你可以走了。您甚至可以使用反射和注解(也许 @HashComponent(order=1) 显示哪些字段以什么顺序进入散列)。它有一个128位的变种,我想你会发现它没有你想象的那么多cpu使用。
我已经使用了这样的代码来获取大型数据集(到目前为止可能有数十亿个对象)的哈希值,以便能够在许多后端存储中对它们进行切分。不管你需要它做什么,它都应该有用。请注意,我想您可能只想打电话 MessageDigest.getInstance() 偶尔 clone() 从那时起:iirc克隆的速度要快得多。

wecizke3

wecizke35#

为什么不使用crc64多项式呢。这些是合理有效的和优化的,以确保所有位都被计数并分布在结果空间中。
如果你用谷歌搜索“crc64 java”,网上有很多可用的实现

vwhgwdsa

vwhgwdsa6#

今天(2018年)的答案。西普哈什。
它将比这里的大多数答案快得多,而且比所有答案的质量都要高得多。
Guava图书馆有一个:https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/hashing.html#siphash24--

k2fxgqgv

k2fxgqgv7#

你为什么不使用 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位的散列,很可能没有一个用例:
我可以想象一个巨大的哈希表分布在几十个服务器上,可能存储着数百亿个Map。对于这种情况,@brianegge在这里仍然有一个有效点:32位允许2^32(约43亿)个不同的散列键。假设一个强大的算法,你应该仍然有相当多的碰撞。有了64位(18446744073亿个不同的密钥),您的存储量肯定会减少,不管您需要它做什么疯狂的场景。不过,考虑128位密钥(340282366920938463463374607431亿个可能的密钥)的用例几乎是不可能的。
要组合多个字段的哈希,只需将一个与素数进行异或相乘,然后将它们相加:

long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2);

小素数用于避免交换值的哈希码相等,即{foo',bar}和{bar',foo}不相等,应该有不同的哈希码。xor是错误的,因为如果两个值相等,则返回0。因此,{foo',foo}和{bar',bar}将具有相同的哈希代码。

w46czmvw

w46czmvw8#

long hash = string.hashCode();

是的,前32位将是0,但在遇到哈希冲突问题之前,可能会耗尽硬件资源。字符串中的hashcode非常有效,并且经过了很好的测试。
我认为上面的更新满足了最简单的可能工作的东西,但是,我同意@sfussenegger扩展现有字符串hashcode的想法。
除了为您的字符串提供一个好的哈希代码之外,您可能还需要考虑在实现中重新设置哈希代码的格式。如果您的存储被其他开发人员使用,或者与其他类型一起使用,这可以帮助您分发密钥。例如,java的hashmap基于两个长度哈希表的幂,因此它添加了这个函数以确保低位得到充分分布。

h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
fhity93d

fhity93d9#

你看apache commons lang吗?
但是对于64位(和128位)您需要一些技巧:joshua bloch在《有效java》一书中列出的规则可以帮助您轻松创建64位哈希(只需使用long而不是int)。对于128位,您需要额外的黑客。。。

相关问题