哈希图中的冲突

问题描述

我已经阅读了有关Hashmap冲突的信息，并采用了以下示例.由于我无法理解什么是碰撞以及如何避免发生碰撞.示例如下

I have read about the Hashmap collision and took the following example. Since i am not able to understand what is collision and how to avoid collision is occurs. The example is follows

import java.util.*;
class JavaCollision{
public static void main(String args[]){

 HashMap<Person, String> map=new HashMap<Person, String>();
 Person p1 = new Person(1,"ABC");
 Person p2 = new Person(2,"DEF");
 Person p3 = new Person(1,"XYZ");
 Person p4 = new Person(1,"PQR");
 Person p5 = new Person(1,"PQR");
 System.out.println("Adding Entries ....");
 map.put(p1,"ONE");
 map.put(p2,"TWO");
 map.put(p3,"THREE");
 map.put(p4,"FOUR");
 map.put(p5,"FIVE");

 System.out.println("\nComplete Map entries \n" + map);

/* System.out.println("\nAccessing non-collided key");
 System.out.println("Value = "+map.get(p2));
 System.out.println("\nAccessing collided key");
 System.out.println("Value = " + map.get(p1));*/
 System.out.println("P1 hashcode is:"+map.get(p1).hashCode()+" And value is:"+map.get(p1));
 System.out.println("P2 hashcode is:"+map.get(p2).hashCode()+" And value is:"+map.get(p2));
 System.out.println("P3 hashcode is:"+map.get(p3).hashCode()+" And value is:"+map.get(p3));
 System.out.println("P4 hashcode is:"+map.get(p4).hashCode()+" And value is:"+map.get(p4));
 System.out.println("P5 hashcode is:"+map.get(p5).hashCode()+" And value is:"+map.get(p5));
}
}

Person.java

Person.java

public class Person {
private int id;
private String name;

public Person(int id, String name) {
    this.id = id; this.name = name;
}

public String getName() {
    return name;
}

public int getId() {
    return id;
}

public void setId(int id) {
    this.id = id;
}

public void setName (String name) {
    this.name = name;
}

public int hashCode(){
    System.out.println("Called hashcode for:"+id+" - "+name);
    return id;
}

public boolean equals(Object obj){
    System.out.println("Called equals on ="+id+" - "+name+" to compare with "+((Person)obj));
    boolean result=false;
    if(obj instanceof Person){
        if( ((Person)obj).getId() == id  && ((Person)obj).getName().equals(name) ){
            result=true;
            System.out.println("Result is true");
        }
    }
    return result;
}
public String toString() {
    return id+" . "+name;
}
}

结果是

Adding Entries ....
Called hashcode for:1 - ABC
Called hashcode for:2 - DEF
Called hashcode for:1 - XYZ
Called equals on =1 - XYZ to compare with 1 . ABC
Called hashcode for:1 - PQR
Called equals on =1 - PQR to compare with 1 . ABC
Called equals on =1 - PQR to compare with 1 . XYZ
Called hashcode for:1 - PQR
Called equals on =1 - PQR to compare with 1 . ABC
Called equals on =1 - PQR to compare with 1 . XYZ
Called equals on =1 - PQR to compare with 1 . PQR
Result is true

Complete Map entries
{1 . ABC=ONE, 1 . XYZ=THREE, 1 . PQR=FIVE, 2 . DEF=TWO}
Called hashcode for:1 - ABC
Called hashcode for:1 - ABC
P1 hashcode is:78406 And value is:ONE
Called hashcode for:2 - DEF
Called hashcode for:2 - DEF
P2 hashcode is:83500 And value is:TWO
Called hashcode for:1 - XYZ
Called equals on =1 - XYZ to compare with 1 . ABC
Called hashcode for:1 - XYZ
Called equals on =1 - XYZ to compare with 1 . ABC
P3 hashcode is:79801726 And value is:THREE
Called hashcode for:1 - PQR
Called equals on =1 - PQR to compare with 1 . ABC
Called equals on =1 - PQR to compare with 1 . XYZ
Called hashcode for:1 - PQR
Called equals on =1 - PQR to compare with 1 . ABC
Called equals on =1 - PQR to compare with 1 . XYZ
P4 hashcode is:2158258 And value is:FIVE
Called hashcode for:1 - PQR
Called equals on =1 - PQR to compare with 1 . ABC
Called equals on =1 - PQR to compare with 1 . XYZ
Called equals on =1 - PQR to compare with 1 . PQR
Result is true
Called hashcode for:1 - PQR
Called equals on =1 - PQR to compare with 1 . ABC
Called equals on =1 - PQR to compare with 1 . XYZ
Called equals on =1 - PQR to compare with 1 . PQR
Result is true
P5 hashcode is:2158258 And value is:FIVE

在此结果中，p4和p5具有相同的哈希码.如何避免在哈希图中使用相同的哈希码.我们能否通过返回哈希码来避免冲突.

In this result p4 and p5 having same hashcode. How to avoid the same hashcode using in hashmap. Can we able to avoid the collision by returning hashcode.

推荐答案

正确，但这不是这里的问题.问题是p4和p5具有相同的 key ，即 id 的值.地图不包含重复项，因此p4被p5覆盖，因为它们具有相同的 id ，而不仅仅是相同的哈希码.

Correct, but that's not the issue here. The issue is that p4 and p5 have the same key, i.e. the value of id. A Map doesn't contain duplicates, so p4 was overwritten by p5, because they have the same id, not just the same hashcode.

无需避免在HashMaps中发生冲突，这不是这里的问题.

There is no need to avoid collisions in HashMaps, and that isn't the problem here.

是的，但这不是这里的问题.如果要在此映射中同时使用p4和p5，则必须给它们提供不同的键.在这种情况下，这意味着您的 equals()方法基于在 id 和 name 上，因此您的 hashCode()方法应该是:

Yes, but that's not the issue here. If you want both p4 and p5 in this map, you will have to give them different keys. What that means in this case is that as your equals() method is based on both id and name, so should your hashCode() method be:

public int hashCode()
{
    return id+name.hashCode(); // for example
}

这篇关于哈希图中的冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！