代码之家  ›  专栏  ›  技术社区  ›  Xinus

为什么如果实现了hashcode方法,那么对于字典中的键和数据类型,equals方法也必须实现?

  •  2
  • Xinus  · 技术社区  · 15 年前

    数据类型:字典键

    有人能告诉我同时实现它们(hashcode/equals)的重要性吗?因为我认为如果我们实现hashcode方法equals,将会比较hashcodes并给出相等的结果。

    4 回复  |  直到 14 年前
        1
  •  3
  •   Community CDub    8 年前

    问题是,仅仅因为两个对象具有相同的哈希代码并不意味着它们是相等的。

    只有2^32个可能的哈希代码(32位整数)。如果你仔细想想,你会发现可能的字符串的数目要大得多。因此,并非每个字符串都具有唯一的哈希代码。

    还有,很多课程 GetHashCode 方法实现得不好。

    例如,这里是 Point.GetHashCode 从.NET源代码:

    public override int GetHashCode() { 
        return x ^ y; 
    }
    

    注意到 (2, 3) 将具有与相同的哈希代码 (3, 2) 即使他们不平等。虽然那里 are implementations 这并没有表现出这种行为,但从定义上讲,它们仍然不是唯一的。

        2
  •  5
  •   CoderTao    15 年前

    哈希代码不能保证唯一性。例如,在大多数语言中,哈希代码采用2^32值。如果你有一个4个整数的类,你能有多少个该类的唯一状态/实例?(2^32)^4。这意味着即使实现了一个完美的哈希代码,仍然会有2^(32*3)个冲突,其中一对不同的对象具有相同的哈希代码。

    因此,哈希代码被用作第一个“快速”比较,以查找与您正在查找的对象类似的对象。一旦你进入到一组对象中,每个对象上的相等性都会被检查,看看是否有一个正是你要寻找的对象。

        3
  •  4
  •   recursive    15 年前

    仅仅因为哈希代码是相等的并不意味着底层对象是相等的。可能的哈希代码数量有限,因此必然会发生冲突。您应该实现一个健壮的 .Equals() 这样你就可以检验平等了。

        4
  •  0
  •   Aneesh    14 年前

    imho,实现hashcode和equals的原因是:

    哈希表允许快速访问基于键的元素。这是可能的,因为它的实现。

    哈希表在内部使用存储桶来存储其值。把每个桶想象成一个数组。 还有一系列这样的桶。因此,它成为一个二维数组。键的散列码是散列表可以直接跳转到存储值的存储桶的索引的机制。

    如:

    下面我编写了一个类的代码,我将使用它作为哈希图实例的键。

    package com.aneesh.hashtable;  
    import java.util.HashMap;  
    public class Key {
    
    private String key;
    
    public Key(String key){
        this.key = key;
    }
    
    
    @Override
    public int hashCode() {
        return key.hashCode();
    }
    
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Key other = (Key) obj;
        if (key == null) {
            if (other.key != null)
                return false;
        } else if (!key.equals(other.key))
            return false;
        return true;
    }
    
    
    public static void main(String[] args) {
    
        HashMap<Key, String> hashMap = new HashMap<Key, String>();
        hashMap.put(new Key("a"), "java");
        hashMap.put(new Key("k"), "Python");
    
        System.out.println(hashMap.get(new Key("a")));
        System.out.println(hashMap.get(new Key("k")));
    
    }
    }
    

    key类的hashcode实现是简单地返回类型为string的实例变量'key'的hashcode。 “a”的哈希代码=97 “k”=107//的哈希代码是我选择这两个键的原因,这两个键很快就会变得明显。

    当你做HasMult.PoT(新密钥(“A”)、“Java”)时; 哈希表必须找出它必须将key,value放入哪个bucket。其代码是

    int indexofBucket = key.hashCode() % numberOfBuckets //7, where key is "a"
    

    因此,(A,“Java”)的密钥、值对将被存储为第七桶中的第一个元素。

    当你做hashmap.put时(new key(“k”),“python”); 桶指数再次计算为 indexofbucket=key.hashcode()%numberofbuckets//7,其中key=“k”

    这是同一个桶,在第7个索引处。

    现在,当您通过其键检索值时

    hashMap.get(new Key("a"));
    

    哈希表可以计算出索引,因此:

    indexOfBucket = key.hashCode() % numberOfBuckets //7
    

    此时,哈希表将在bucket中找到两个元素。现在,它必须返回哪个元素将通过(在一个简单的实现中,我猜)迭代每个元素并比较键的相等值来决定。如果没有equals,哈希表甚至可能找不到已添加到其中的元素。

    要看到这一点,请注释掉key类的equals实现并运行代码。你会看到

    null  
    null 
    

    将打印为输出,而在实现equals时,您将看到

    "java",  
    "python"
    

    长期受伤的解释,但希望能有所帮助