java - HashMap 中的碰撞

Question

我已经阅读了有关 Hashmap 冲突的内容并举了以下示例。因为我无法理解什么是碰撞以及如何避免发生碰撞。示例如下

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

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 具有相同的哈希码。如何避免在 hashmap 中使用相同的 hashcode。我们能否通过返回hashcode来避免冲突。

Answer 1

您对 HashMap 中的冲突有一种奇怪的理解。它实际上非常简单 - 当两个对象在内部重新哈希在 HashMap 内完成后具有相同的哈希码时:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

基本上，在计算哈希码后，HashMap 将采用前 16 位，并对后 16 位进行 XOR 操作 - 确保更好的分布。如果在重新哈希之后，两个不同键具有哈希码值 - 这称为哈希冲突。这意味着两个条目最终将位于同一个存储桶中。

但通常这一直是性能瓶颈，因为放置在同一个存储桶中的条目(在达到一定数量后)会被放入完美平衡的红黑树中，并且搜索还是很快的。例如，如果此存储桶中有 2 pow 32 条目，则需要 ma​​x 32 步才能找到该条目；在此树桶中，一般搜索时间为O(logn)。对于 map 本身来说，搜索时间将是O(1) - 常数。

所以不要让自己复杂化 - 虽然您可以测试您的 Key#hashCode 以便它具有更好的哈希码 - 不要这样做，除非您确定存在性能问题(我非常怀疑)。