是否可以使用 java 的 hashcode 函数为不同的字符串使用相同的 hashcode？或者如果有可能，那么它的可能性是多少？
问问题
38154 次
12 回答
67
Java 哈希码是 32 位。它散列的可能字符串的数量是无限的。
所以是的，会有碰撞。百分比是没有意义的——有无限数量的项目（字符串）和有限数量的可能散列。
于 2012-04-11T08:26:13.773 回答
30
是的。很多。
看看下面的一对
- “FB”和“Ea”
即使其中的字符不同，也可以返回相同的哈希码。
基本上它是字符串中字符的总和乘以一个整数。
于 2012-04-11T08:26:09.180 回答
8
如果有可能，那么其可能性的百分比是多少？
这不是一个特别有意义的问题。
但是，除非String::hashcode函数或生成对象的方式存在系统性偏差，否则String任何两个不同（不相等）String对象具有相同哈希码的概率将为 2 32中的 1 。
这假设字符串是从所有可能的字符串值的集合中随机选择的。如果您以各种方式限制集合，则概率将与上述数字不同。（例如，“FB”/“Ea”冲突的存在意味着所有 2 个字母字符串的集合中发生冲突的概率高于规范。）
另一件需要注意的事情是，随机选择 2 32 个不同的字符串（来自更大的无偏字符串集）没有哈希冲突的机会非常小。要了解原因，请阅读关于生日悖论的维基百科页面。
实际上，在一组 2 32 个不同的字符串中没有哈希冲突的唯一方法是选择或生成字符串。即使通过选择随机生成的字符串来形成集合，计算量也会很大。为了有效地生成这样的集合，您需要利用String::hashCode算法的属性，（幸运的是）已指定。
于 2012-04-11T08:41:03.177 回答
8
是的，这是完全可能的。字符串（或其他对象类型——假设您将在本例中使用字符串）与集合中的其他字符串具有相同哈希码的概率取决于该集合的大小（假设所有字符串在该系列是独一无二的）。概率分布如下：
- 对于一组大小约为 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/ （看“你应该知道的第二件事”）
于 2014-06-19T11:47:30.910 回答
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;
}
于 2012-04-11T08:25:31.773 回答
6
是的，两个字符串可能具有相同的哈希码 - 如果您查看Wikipedia 文章，您会看到两者都"FB"具有"Ea"相同的哈希码。方法契约中没有任何内容说 ahashCode()应该用于比较相等性，您想使用equals()它。
从 Java 1.2 开始，StringhashCode()通过对字符串的整个文本使用积和算法来实现。
于 2012-04-11T08:30:21.773 回答
4
是的，根据鸽子洞概念的定义，两个不同的字符串可以产生相同的哈希码，并且应该始终编写代码以适应这种情况（通常是不中断。）
于 2012-04-11T08:25:40.540 回答
3
随机字符串的冲突百分比应该是最小的。但是，如果您从外部来源散列字符串，攻击者可以轻松创建数十万个具有相同散列码的字符串。在 java HashMap 中，这些都将映射到同一个存储桶并有效地将映射转换为链表。然后，对地图的访问时间将与地图大小成正比，而不是常数，从而导致拒绝服务攻击。
请参阅此页面关于针对 Web 应用程序平台的有效 DoS 攻击，以获取指向演示文稿的更多信息链接。
于 2012-04-11T11:28:20.503 回答
2
是的，这是可能的，因为 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
于 2018-06-01T09:19:25.357 回答
1
//你可以用-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");
}
}
`
于 2018-12-20T23:09:17.763 回答
1
是的（不仅在 Java 中，它适用于任何语言），它可以为不同的字符串生成相同的哈希码。我在回忆我的教授教过的一条规则，它在这里可能有用-
两个相同的字符串/值必须具有相同的哈希码，但反之则不然。
python中的示例
>>> hash('same-string')
-5833666992484370527
>>> hash('same-string')
-5833666992484370527
可能有另一个字符串可以匹配相同的哈希码，因此我们无法使用哈希码派生密钥。
两个不同字符串具有相同哈希码的原因是由于冲突。
于 2019-01-14T19:58:32.043 回答
-1
"tensada".hashCode()
"friabili".hashCode());
java 哈希函数在这里返回相等的值。
于 2020-10-12T17:45:55.200 回答