字符串的良好哈希函数

我正在尝试为字符串设想一个好的哈希函数.而且我认为总结字符串中前五个字符的unicode值可能是一个好主意(假设它有五个,否则在它结束时停止).这是一个好主意,还是一个坏主意？

我在Java中这样做,但我不认为这会产生很大的不同.

1> jonathanasdf..：

---

通常哈希不会做算术,否则stop和pots将具有相同的哈希值.

并且你不会将它限制在前n个字符,因为否则房屋和房屋将具有相同的哈希值.

通常,散列取值并乘以素数(使其更有可能生成唯一的散列)所以你可以这样做:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}

---

@devsda他没有说永远独特,他说更有可能是独一无二的.至于为什么,谷歌上的快速搜索揭示了这篇文章:http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/解释为什么31用于Java字符串哈希.没有给出数学证明,但它确实解释了为什么质数更好地工作的一般概念.

---

非常感谢您澄清了做更好哈希的想法.只是要仔细检查 - 在存储对象之前,Java将使用hashCode()返回值映射到某些表索引.因此,如果hashCode()返回m,它会执行类似(m mod k)的操作来获取大小为k的表的索引.是对的吗？

2> 小智..：

---

如果它是一个安全的东西,你可以使用Java加密:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

---

尼斯.我有一个机器学习应用程序,在大型语料库上进行统计NLP.在对文本中的原始单词进行形态规范化的几个初始传递之后,我丢弃了字符串值并改为使用哈希代码.在我的整个语料库中,大约有600,000个独特单词,并且使用默认的java哈希码函数,我得到了大约3.5%的冲突.但是如果我使用SHA-256字符串值然后从消化的字符串生成哈希码,则碰撞率小于0.0001%.谢谢!

---

@benjismith百万分之一太大了......"低于0.0001%"是一种说"完全为0"的倾斜方式？我真的怀疑你看到了SHA-256碰撞,因为从未在任何地方发现过这种情况; 甚至不适用于160位SHA-1.如果你有两个产生相同SHA-256的字符串,安全社区很乐意看到它们; 你会以一种非常模糊的方式闻名世界.参见[SHA函数的比较](https://en.wikipedia.org/wiki/SHA-2#Comparison_of_SHA_functions)

---

@TimSylvester,你误解了.我没有找到SHA-256碰撞.我计算了SHA-256然后将得到的字节序列送入典型的Java"hashCode"函数,因为我需要一个32位散列.那就是我发现碰撞的地方.没什么了不起:)

---

感谢您提供有关碰撞和单词数量的信息.很有帮助.

3> Frederik..：

---

您应该使用String.hashCode().

如果你真的想自己实现hashCode:

不要试图从哈希码计算中排除对象的重要部分以提高性能 - Joshua Bloch,Effective Java

仅使用前五个字符是个坏主意.想想层次名称,如URL:他们都将有相同的散列码(因为他们都开始以"http://",这意味着它们被存储在一个哈希表一样斗下,表现出可怕的性能.

这是一篇关于来自" Effective Java " 的String hashCode的战争故事:

在1.2之前的所有版本中实现的String散列函数检查最多16个字符,在整个字符串中均匀分布,从第一个字符开始.对于大型分层名称集合(例如URL),此哈希函数显示可怕的行为.

4> Pyrolistical..：

---

如果你用Java做这个,那么你为什么要这样做呢？只需调用.hashCode()字符串即可

---

如果您需要在JVM版本和实现之间保持一致,则不应该依赖`.hashCode()`.相反,使用一些已知的算法.

---

`String :: hashCode`的算法在JDK中指定,因此它就像类java.lang.String`的存在一样可移植.

---

我正在将它作为类的一部分,而赋值的一部分是编写几个不同的哈希函数.教授告诉我们为"更好"的人提供外界帮助.

5> Mike Samuel..：

---

GuavaHashFunction(javadoc)提供了不错的非加密散列.

6> Festus Tamak..：

---

Nick提供的这个函数很好但是如果你使用新的String(byte [] bytes)来转换为String,它就失败了.您可以使用此功能来执行此操作.

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

可能这可以帮助别人

7> Pratik Deogh..：

---

// djb2 hash function
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

djb2哈希函数背后的源逻辑 - SO

8> Thomas Porni..：

---

有传言说FNV-1是一个很好的字符串散列函数。

对于长字符串（长于大约200个字符），可以通过MD4哈希函数获得良好的性能。作为一种加密功能，它大约在15年前就被打破了，但是出于非加密目的，它仍然非常好，而且速度惊人。在Java上下文中，您将必须将16位char值转换为32位字，例如，通过将这些值分组为对。可以在sphlib中找到Java中MD4的快速实现。在课堂分配的情况下，可能会造成过大的杀伤力，但值得一试。