我尝试编写一个小程序来演示java中只有equals被覆盖而不是hashcode()方法时的哈希冲突。这是为了证明两个不相等的对象可以具有相同哈希码的理论。这是针对询问行为的面试问题。
我创建了200000个对象,将它们存储在一个数组中,然后比较它们,看看哪些是重复的。(为此,在对象创建阶段之后,我使用嵌套For循环迭代对象数组。)对于大约200000个物体,我会遇到9次碰撞。第一个是索引196和121949处的对象。然后我继续打印这些散列码,以显示这两个值是相同的。
然而,我得到了一些非常令人惊讶的行为。如果我迭代嵌套的for循环并打印第一个hashcode冲突,我会得到相同的hashcode值
1867750575
1867750575
对于索引196和121949处的两个对象。
但是,如果我注释掉用于检测所有冲突的嵌套for循环并直接打印索引196和121949处元素的哈希码,我会得到
1829164700
366712642
请注意,我不是在评论这些元素的创建,只是在我检查碰撞的部分。
为什么会发生这种情况,即使我不迭代它们,哈希代码不应该是一致的吗?
附录1:据我所知,根据生日原则,如果我创建了200000个对象,我必须得到一个碰撞,如何迭代每个hascode或不改变任何东西?
附录2:我尝试添加另一个200000大小的数组,只是为了看看冲突索引是否发生变化,它们没有发生变化,所以显然在未提交循环的情况下对二进制文件进行更改不会进行任何更改。所以改变二进制更改哈希码的假设不成立。
这是我的密码
import java.util.HashMap;
public class EmployeeFactory {
private static int counter = 0;
public int id;
public String empName;
EmployeeFactory() {
id = counter;
empName = "employee_" + id;
counter++;
}
@Override
public boolean equals(Object o) {
// If the object is compared with itself then return true
if (o == this) {
return true;
}
if (o == null || o.getClass() != this.getClass()) {
return false;
}
EmployeeFactory emp = (EmployeeFactory) o;
// Compare the data members and return accordingly
return this.id == emp.id;
}
public static void main(String[] args) {
int Obj_Count = 200000;
EmployeeFactory objs[] = new EmployeeFactory[Obj_Count];
for (int i = 0; i < Obj_Count; ++i) {
EmployeeFactory temp = new EmployeeFactory();
objs[i] = temp;
}
//Please try code once un commenting the loop below and once while keeping it commented.
/*
for (int i = 0; i < Obj_Count; ++i)
{
for (int j = i + 1; j < Obj_Count; ++j)
{
if (objs[i].hashCode() == objs[j].hashCode())
{
System.out.println("Objects with IDs " + objs[i].id
+ " and " + objs[j].id + " collided.");
System.out.println("Object Is " + i + "and Obj ID is "+ objs[i].id + " Has Hashcode " + objs[i].hashCode());
System.out.println("Object Is " + j + "and Obj ID is "+ objs[j].id + " Has Hashcode " + objs[j].hashCode());
System.out.println("");
}
}
}
*/
HashMap<EmployeeFactory, EmployeeFactory> hm = new HashMap<EmployeeFactory, EmployeeFactory>();
objs[121949].id = objs[196].id;
hm.put(objs[196], objs[196]);
hm.put(objs[121949], objs[121949]);
System.out.println(hm.get(objs[121949]).empName);
System.out.println(hm.get(objs[196]).empName);
// checking the hashmap
System.out.println(hm.get(objs[121949]).hashCode());
System.out.println(hm.get(objs[196]).hashCode());
// Checking the array
System.out.println(objs[121949].hashCode());
System.out.println(objs[196].hashCode());
}
}
计算输出:
employee_121949
employee_196
1829164700
366712642
1829164700
366712642
未注释的循环输出
Objects with IDs 196 and 121949 collided.
Object Is 196and Obj ID is 196 Has Hashcode 1867750575
Object Is 121949and Obj ID is 121949 Has Hashcode 1867750575
Objects with IDs 62082 and 145472 collided.
Object Is 62082and Obj ID is 62082 Has Hashcode 2038112324
Object Is 145472and Obj ID is 145472 Has Hashcode 2038112324
Objects with IDs 62354 and 105841 collided.
Object Is 62354and Obj ID is 62354 Has Hashcode 2134400190
Object Is 105841and Obj ID is 105841 Has Hashcode 2134400190
Objects with IDs 68579 and 186938 collided.
Object Is 68579and Obj ID is 68579 Has Hashcode 1872358815
Object Is 186938and Obj ID is 186938 Has Hashcode 1872358815
Objects with IDs 105219 and 111288 collided.
Object Is 105219and Obj ID is 105219 Has Hashcode 651156501
Object Is 111288and Obj ID is 111288 Has Hashcode 651156501
Objects with IDs 107634 and 152385 collided.
Object Is 107634and Obj ID is 107634 Has Hashcode 273791087
Object Is 152385and Obj ID is 152385 Has Hashcode 273791087
Objects with IDs 108007 and 146405 collided.
Object Is 108007and Obj ID is 108007 Has Hashcode 1164664992
Object Is 146405and Obj ID is 146405 Has Hashcode 1164664992
Objects with IDs 135275 and 180997 collided.
Object Is 135275and Obj ID is 135275 Has Hashcode 996371445
Object Is 180997and Obj ID is 180997 Has Hashcode 996371445
Objects with IDs 153749 and 184310 collided.
Object Is 153749and Obj ID is 153749 Has Hashcode 254720071
Object Is 184310and Obj ID is 184310 Has Hashcode 254720071
employee_121949
employee_121949
1867750575
1867750575
1867750575
1867750575
Matt Timmermans的回答相当好地涵盖了基本问题,尤其是“你不能期望在不同的跑步之间有任何一致性。”( 1)
默认的对象。hashCode()
实现(也称为标识哈希代码,因为它与系统相同。identityHashCode(obj)
)目前在Hotspot中只是一个带有线程本地种子的伪随机数。很长一段时间以来,对象的内存地址没有任何依赖关系。如果程序的执行是完全确定的,那么散列很可能是可重复的。
还请注意,标识哈希代码是在第一次调用对象时延迟生成的。hashCode()
或系统。identityHashCode()
并且该值存储在该对象中,因此对该对象的后续调用将返回相同的值。如果在另一个线程中运行碰撞检测器循环,将得到完全不同的哈希值,从而产生不同的碰撞。
如果不重写hashCode()
,则会从类对象
继承标识哈希代码函数。
标识哈希代码依赖于您看不到的东西,这些东西在理论上每次运行程序时都会发生变化,例如对象在内存中的最终位置、在您之前创建的对象数量等。您只是不能期望在程序或方法的不同运行之间的标识哈希值具有任何一致性。
然而,如果你两次运行完全相同的程序,并且不是太大,那么很有可能两次都使用相同的哈希值。但是,如果更改程序,则会更改加载和编译类所消耗的内存量,这很可能会通过更改对象在内存中的位置来更改标识哈希。
假设我们有一个冲突,但键值不同,因此根据定义,Hashmap将在该桶中创建一个链表,并将新的键值对添加为现有键值条目的下一个。 我的问题是在这种情况下我们如何迭代哈希图?默认迭代机制是否更改为实际检索所有冲突并存储在同一存储桶位置的键值对?
Hi StackOverFlow成员 reports=表名。 数据库 这是数据库表: 我想 当我运行这段代码时.. 它返回AllTotal
我试图故意制造碰撞。 所以,我有和对象。我已经覆盖了Country的和方法,以便: india.hash代码()==india2.hash代码() 根据JavaHashMap中的冲突解决方案和文章“让这个国家对象在hashmap中”的一部分,如果key1的结果等于key2上的相同操作,那么应该会有冲突。 所以,我放置断点来查看的内容,并查看它的是2。也就是说,它包含两个不同的条目,并且没有link
假设我有这个语法,用Antlr4编写: 我的思维过程是应该与相同;应该是。如果 上面的树似乎是正确的,它再次计算为。 但是当不使用空格时,antlr认为有两个INT-expr。如果 不应该跳过所有空格(使用规则),这意味着两个表达式的解析方式应该相同吗?
问题内容: 来自问题的原因,或者说更确切地说,object .__new__在这两种情况下的工作方式不同 作者对为什么不感兴趣,而对如何感兴趣。 我非常想了解原因,尤其是: 为什么不打印任何参数而不是 为什么没有为testclass3引发错误?(因为除了自我之外没有其他参数) 码 问题答案: 您正在使用旧的Python版本;此错误消息已更新: Python只会抱怨既不支持又不被覆盖的参数。例如,当
我试图在不使用Box2D的情况下为libgdx角色(玩家和敌人)实现碰撞检测。正如我所读到的那样,Box2D支持内置碰撞检测,但由于我的游戏不涉及环境中的任何物理因素,因此我不习惯仅为此使用Box2D。 我发现的许多示例通过为此定义一个边界框(矩形)来启用冲突检测,但我正在寻找一个内置的解决方案。