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

Question

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

Answer 1

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

所以是的，会有碰撞。百分比毫无意义 - 存在无限数量的项（字符串）和有限数量的可能哈希值。

Answer 2

//您可以使用-Xmx2100m运行以下代码，并且可以获得多个结果，足以填满您的控制台

`

import java.util.HashMap;

public class TestHashCollision {
        public static void main(String[] args) {
        final String TEXT = "was stored earlier had the same hash as";
        HashMap<Integer,String> hs=new HashMap<>();
        long t1=System.currentTimeMillis();
        long t2=System.currentTimeMillis();
        for(long l=0;l<Long.MAX_VALUE;l++) {
            String key="d"+l;
            if(hs.containsKey(key.hashCode())) {
                System.out.println("'"+hs.get(key.hashCode())+"' "+TEXT+" '"+key+"'");//System.exit(0);
            } else {
                hs.put(key.hashCode(),key);
            }
            t2=System.currentTimeMillis();
            if(t2-t1>10000) {
                t1=System.currentTimeMillis();
                System.out.println("10 seconds gone! size is:"+hs.size());
            }
        }
        System.out.println("Done"); 
    }
}

`

Answer 3

是（不仅在Java中，它适用于任何语言），它可以为不同的字符串生成相同的哈希码。我记得我的教授教的一条规则，它可能在这里很有用 -

两个相同的字符串/值必须具有相同的哈希码，但反之则不然。

python中的示例

>>> hash('same-string')
-5833666992484370527
>>> hash('same-string')
-5833666992484370527

可能有另一个字符串可以匹配相同的哈希代码，因此我们无法使用哈希代码派生密钥。

两个不同字符串具有相同哈希码的原因是由于冲突。

Answer 4

是。很多。

看看下面的一对

• “FB”和“Ea”

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

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

Answer 5

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

• 使用一组大小~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 6

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

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

但是，除非在String::hashcode函数或生成String对象的方式中存在某些系统性偏差，否则任何两个不同（不相等）String对象将具有相同哈希码的概率将为232中的1。

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

---

需要注意的另一点是，没有哈希冲突的随机选择的232个不同字符串（来自更大的无偏字符串集）的可能性非常小。要了解原因，请阅读Birthday Paradox上的维基百科页面。

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

Answer 7

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

以下是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 8

是的，两个字符串可能具有相同的哈希码 - 如果你看一下Wikipedia article，你会发现"FB"和"Ea"都有相同的哈希码。方法合同中没有任何内容表示应该使用hashCode()来比较相等性，你想使用equals()。

从Java 1.2开始，String通过hashCode()实现using a product sum algorithm over the entire text of the string。

Answer 9

是的，根据鸽子洞概念的定义，两个不同的字符串可以产生相同的哈希码，并且应该始终编写代码以满足这些条件（通常，不会破坏）。

Answer 10

随机字符串的冲突百分比应该是最小的。但是，如果您从外部源散列字符串，攻击者可以轻松创建数十万个具有相同哈希码的字符串。在Java HashMap中，这些都将映射到同一个存储桶，并有效地将地图转换为链接列表。然后，对地图的访问时间将与地图大小成比例而不是恒定，从而导致拒绝服务攻击。

有关演示文稿的更多信息，请参阅Effective DoS attacks against Web Application Plattforms上的此页面。

Answer 11

是的，这是可能的，因为Object类的equals（）和hashCode（）方法之间的契约之一是..........如果两个对象根据equals（）方法不相等那么就没有保证他们的hashCode将是相同的，hashCode可能/可能不相等。即，如果obj1.equals（obj2）返回false，则obj1.hashCode（）== obj2.hashCode（）可能/可能不返回true。例：

    String str1 = "FB";
    String str2 = "Ea";
    System.out.println(str1.equals(str2));// false
    System.out.println(str1.hashCode() == str2.hashCode()); // true