首页 ❯

了解哈希映射中等值和哈希代码的工作原理

equals hashcode hashmap java
2022-08-31 16:30:48

我有这个测试代码：

import java.util.*;

class MapEQ {

  public static void main(String[] args) {
   Map<ToDos, String> m = new HashMap<ToDos, String>();
   ToDos t1 = new ToDos("Monday");
   ToDos t2 = new ToDos("Monday");
   ToDos t3 = new ToDos("Tuesday");
   m.put(t1, "doLaundry");
   m.put(t2, "payBills");
   m.put(t3, "cleanAttic");
   System.out.println(m.size());
} }

class ToDos{

  String day;

  ToDos(String d) { day = d; }

  public boolean equals(Object o) {
      return ((ToDos)o).day == this.day;
 }

// public int hashCode() { return 9; }
}

当 is 未注释时返回 2，当它被注释时，它返回 3。为什么？// public int hashCode() { return 9; }m.size()


答案 1

HashMap使用 和 进行条目查找。给定键的查找顺序如下所示：hashCode()==equals()k

  • 用于确定存储条目的存储桶（如果有）k.hashCode()
  • 如果找到，则对于该存储桶中每个条目的键，如果为 ，则返回 的条目k1k == k1 || k.equals(k1)k1
  • 任何其他结果，无相应条目

为了使用示例进行演示，假设我们要创建一个 where 键是“逻辑等效的”，如果它们具有相同的整数值（由类表示）。然后，我们构造一个 ，放入一个条目中，然后尝试覆盖其值并通过键检索值。HashMapAmbiguousIntegerHashMap

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }
}

HashMap<AmbiguousInteger, Integer> map = new HashMap<>();
// logically equivalent keys
AmbiguousInteger key1 = new AmbiguousInteger(1),
                 key2 = new AmbiguousInteger(1),
                 key3 = new AmbiguousInteger(1);
map.put(key1, 1); // put in value for entry '1'
map.put(key2, 2); // attempt to override value for entry '1'
System.out.println(map.get(key1));
System.out.println(map.get(key2));
System.out.println(map.get(key3));

Expected: 2, 2, 2

不要覆盖 hashCode（） 和 equals（）：默认情况下，Java 会为不同的对象生成不同的值，因此使用这些值来映射和放入不同的存储桶中。 没有相应的存储桶，因此它没有值。hashCode()HashMapkey1key2key3

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 2, set as entry 2[1]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 2, get as entry 2[1]
map.get(key3); // map to no bucket
Expected: 2, 2, 2
Output:   1, 2, null

仅覆盖 hashCode（）： 映射并放入同一存储桶，但由于两者且检查失败，它们仍然是不同的条目，因为默认情况下使用 check，并且它们引用不同的实例。 两者都失败并检查 和，因此没有相应的值。HashMapkey1key2key1 == key2key1.equals(key2)equals()==key3==equals()key1key2

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return value;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[2]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[2]
map.get(key3); // map to bucket 1, no corresponding entry
Expected: 2, 2, 2
Output:   1, 2, null

仅覆盖 equals（）：将所有键映射到不同的存储桶中，因为默认为不同的 . 或者检查在这里是无关紧要的，因为从来没有达到需要使用它们的程度。HashMaphashCode()==equals()HashMap

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 2, set as entry 2[1]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 2, get as entry 2[1]
map.get(key3); // map to no bucket
Expected: 2, 2, 2
Actual:   1, 2, null

覆盖 hashCode（） 和 equals（）： 映射 ，并放入同一存储桶中。 检查在比较不同的实例时失败，但检查通过，因为它们都具有相同的值，并且被我们的逻辑视为“逻辑等效”。HashMapkey1key2key3==equals()

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return value;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[1]
map.get(key3); // map to bucket 1, get as entry 1[1]
Expected: 2, 2, 2
Actual:   2, 2, 2

如果hashCode（）是随机的，该怎么办？：将为每个操作分配不同的存储桶，因此您永远不会找到您之前放入的相同条目。HashMap

class AmbiguousInteger {
    private static int staticInt;
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return ++staticInt; // every subsequent call gets different value
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 2, set as entry 2[1]
map.get(key1); // map to no bucket, no corresponding value
map.get(key2); // map to no bucket, no corresponding value
map.get(key3); // map to no bucket, no corresponding value
Expected: 2, 2, 2
Actual:   null, null, null

如果hashCode（）总是一样的呢？：将所有键映射到一个大桶中。在这种情况下，您的代码在功能上是正确的，但使用的实际上是多余的，因为任何检索都需要在O（N）时间内循环访问该单个存储桶中的所有条目（对于Java 8，则为O（logN），相当于使用.HashMapHashMapList

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 0;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[1]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[1]
map.get(key3); // map to bucket 1, get as entry 1[1]
Expected: 2, 2, 2
Actual:   2, 2, 2

如果 equals 总是假呢？：当我们将同一实例与自身进行比较时，检查传递，否则会失败，检查总是会失败，并且被认为是“逻辑上不同的”，并映射到不同的条目，尽管由于相同，它们仍然在同一桶中。==equalskey1key2key3hashCode()

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 0;
    }

    @Override
    public boolean equals(Object obj) {
        return false;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[2]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[2]
map.get(key3); // map to bucket 1, no corresponding entry
Expected: 2, 2, 2
Actual:   1, 2, null

好吧，如果等于现在总是正确的呢？：你基本上是说所有对象都被认为与另一个对象“逻辑上等价”，所以它们都映射到同一个桶（由于相同的），相同的条目。hashCode()

class AmbiguousInteger {
    private final int value;

    AmbiguousInteger(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return 0;
    }

    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value
map.put(new AmbiguousInteger(100), 100); // map to bucket 1, set as entry1[1], override value
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[1]
map.get(key3); // map to bucket 1, get as entry 1[1]
Expected: 2, 2, 2
Actual:   100, 100, 100

答案 2

您覆盖了，但没有覆盖 .必须确保对于两个对象返回 true 的所有情况，都返回相同的值。哈希代码是一个代码，如果两个对象相等，则该代码必须相等（反之亦然）。当您将硬编码值 9 放入时，您将再次满足合约。equalshashCodeequalshashCode

在哈希映射中，仅在哈希存储桶中测试相等性。你的两个星期一对象应该是相等的，但是因为它们返回不同的哈希代码，所以甚至没有调用该方法来确定它们的相等性 - 它们被直接放入不同的桶中，并且甚至不考虑它们相等的可能性。equals


推荐
更多 »
标签
更多 »
php pass-by-reference optional-parameters default-value javascript arrays dom function string object serialization tostring visibility syntax jslint use-strict operators equality equality-operator identity-operator datetime timestamp date-arithmetic redirect angularjs loops foreach iteration scope variables
推荐
更多 »