Java的hashCode可以为不同的字符串生成相同的值吗？

Question

是否可以使用java的哈希码函数为不同的字符串使用相同的哈希码？或者如果可能的话,它的可能性百分比是多少？

Answer 1

Java哈希码是32位.它散列的可能字符串数量是无限的.

所以是的,会有碰撞.百分比毫无意义 - 存在无限数量的项(字符串)和有限数量的可能哈希值.

Answer 2

是.很多.

看看下面的一对

• "FB"和"Ea"

即使其中的字符不相同,也可以返回相同的哈希码.

基本上它是字符串中的字符总和乘以整数.

Answer 3

如果有可能那么它的可能性百分比是多少？

这不是一个特别有意义的问题.

但是,除非在String::hashcode函数或生成String对象的方式中存在某些系统性偏差,否则任何两个不同(不相等)String对象具有相同哈希码的概率将为1 in 2 ³².

这假定从所有可能的String值集合中随机选择字符串.如果以各种方式限制集合,则概率将与上述数字不同.(例如,"FB"/"Ea"碰撞的存在意味着所有2个字母串的集合中的碰撞概率高于标准.)

另一个要注意的是,2个的机会³²不具有散列冲突随机选择(从一个更大的无偏组字符串)不同的字符串是难以察觉的小.要了解原因,请阅读生日悖论上的维基百科页面.

实际上,如果您选择或生成字符串,唯一的方法是在一组2 ^32个不同的字符串中获得无哈希冲突.即使通过选择随机生成的字符串来形成集合也将是计算上昂贵的.要有效地生成这样的集合,您需要利用String::hashCode算法的属性(幸运的是).

Answer 4

是的,完全有可能.字符串(或其他一些对象类型 - 假设您将使用此示例中的字符串)与集合中的其他字符串具有相同哈希码的概率取决于该集合的大小(假设所有字符串都在该系列是独一无二的).概率分布如下:

• 使用一组大小~9,000,你有1%的几率使两个字符串与集合中的哈希冲突
• 使用一组大小~30,000,你有10%的几率使两个字符串与集合中的哈希冲突
• 使用一组大小~77,000,你有50%的几率使两个字符串与集合中的哈希冲突

做出的假设是:

• hashCode函数没有偏差
• 上述集合中的每个字符串都是唯一的

这个网站清楚地解释了它:http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/ (看看"你应该知道的第二件事")

Answer 5

这不会直接回答你的问题,但我希望它有所帮助.

以下是源代码java.lang.String.

/**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using <code>int</code> arithmetic, where <code>s[i]</code> is the
 * <i>i</i>th character of the string, <code>n</code> is the length of
 * the string, and <code>^</code> indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
public int hashCode() {
    int h = hash;
    int len = count;
    if (h == 0 && len > 0) {
    int off = offset;
    char val[] = value;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Answer 6

是的,这是可能的两个字符串具有相同的哈希码-如果你看看在维基百科的文章,你会看到两个"FB"与"Ea"具有相同的哈希码.方法合同中没有任何内容表示hashCode()应该用于比较相等性,您希望将其equals()用于此.

从Java 1.2开始,String hashCode()通过在字符串的整个文本上使用乘积和算法来实现.