为什么containsKey()的Map只调用hashCode()？

Question

我读了接口Map的JavaDoc,它说:

Collections Framework接口中的许多方法都是根据equals方法定义的.例如,对于规范containsKey(Object key)法说:"返回true当且仅当此映射包含一个键的映射关系k,使得 (key==null ? k==null : key.equals(k))".不应将此规范解释为暗示Map.containsKey使用非null参数调用key将导致key.equals(k)对任何键调用k.实现可以自由地实现优化,从而equals避免调用,例如,通过首先比较两个密钥的哈希码.(该Object.hashCode()规范保证具有不等哈希码的两个对象不能相等.)

我的理解是在containsKey()调用时,都会调用hashCode()和equals(),因此我编写了自己的代码来测试它.

HappyDay类将作为键存储在HashMap中,我重写hashCode()和equals()方法,并添加System.out.println("invoking hashCode()" + this.happyHour);并System.out.println("invoking equals()");检查方法是否被调用.

public class HappyDay {

    private final int happyHour;

    public HappyDay(int hh) {
        this.happyHour = hh;
    }

    public int getHappyHour() {
        return this.happyHour;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("invoking equals()");
        if (o == null) {return false;}

        if (o == this) {return true;}

        //this is an easy overridden, if happy hour equal, objects will be equal.
        if (o instanceof HappyDay) {
            HappyDay other = (HappyDay) o;
            int otherHappyHour = other.getHappyHour();
            if (this.happyHour == otherHappyHour) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode() {
        System.out.println("invoking hashCode()" + this.happyHour);
        int hash = 7;
        hash = hash + this.happyHour;
        return hash;
    }
}

public class Main {
    public static void main(String[] args) {
        Map<HappyDay,String> hm = new HashMap<>();

        HappyDay hd1 = new HappyDay(1);
        HappyDay hd2 = new HappyDay(2);

        hm.put(hd1, "hd1");
        hm.put(hd2, "hd2");

        if(hm.containsKey(hd2)){
            System.out.println("found");
        }else{
            System.out.println("not exist");
        }
    }
}

Main类是将两个HappyDay实例放入HashMap,插入后(put()方法),我调用hm.containsKey(hd2),正如我从JavaDoc引用的那样,它应首先调用hashCode()然后调用equals(),但输出是

invoking hashCode()1 //call put()
invoking hashCode()2 //call put()
invoking hashCode()2 //call containsKey()
found

我期待有另一个输出行应该是invoking equals(),任何人都可以解释为什么equals()不被调用？

Answer 1

哈希映射首先检查密钥相等性==; 只有当失败时才会继续检查equals.

现在,您将hd2地图作为键放入,然后containsKey使用相同的对象作为参数进行检查,因此==测试通过并且equals永远不会被调用.

检查地图是否包含给定的键归结为检查是否getEntry(key)返回null.让我们来看看来源:

360     final Entry<K,V> getEntry(Object key) {
361         int hash = (key == null) ? 0 : hash(key.hashCode());
362         for (Entry<K,V> e = table[indexFor(hash, table.length)];
363              e != null;
364              e = e.next) {
365             Object k;
366             if (e.hash == hash &&
367                 ((k = e.key) == key || (key != null && key.equals(k))))
368                 return e;
369         }
370         return null;
371     }

在管线367,我们可以看到,在==测试进行之前一个equals测试.该短路的||完全跳过equals如果测试==通过,这是这里发生了什么.

这可能是实现的,因为它是跳过可能昂贵的equals方法(例如String#equals,必须检查给定字符串的每个字符).该equals合同还规定,o1.equals(o2)应该是如果为真o1 == o2,那么这是一个有效的优化.

让我们稍微修改你的代码来进行健全性检查:

if (hm.containsKey(new HappyDay(2))) {
    System.out.println("found");
} else {
    System.out.println("not exist");
}

现在的输出是:

invoking hashCode()1
invoking hashCode()2
invoking hashCode()2
invoking equals()
found

请注意,这equals是被调用的.这是有道理的,因为我们containsKey使用一个新的但相同的对象进行调用,因此==测试返回false并equals执行测试.

Answer 2

的源代码HashMap说明发生了什么。

该containsKey方法调用getEntry：

360     final Entry<K,V> More ...getEntry(Object key) {
361         int hash = (key == null) ? 0 : hash(key.hashCode());
362         for (Entry<K,V> e = table[indexFor(hash, table.length)];
363              e != null;
364              e = e.next) {
365             Object k;
366             if (e.hash == hash &&
367                 ((k = e.key) == key || (key != null && key.equals(k))))
368                 return e;
369         }
370         return null;
371     }

如果散列匹配，则将keys 与==第一个进行比较。由于您传入原始hd2对象，因此==运算符返回true（它是同一个对象），并且短路||运算符永远不会评估右侧，并且equals不会被调用。

如果您要创建另一个HappyDay，也通过2，==则将屈服false并被equals调用。

至于为什么==首先存在，我不得不猜测，==首先快速执行平均效率更高，并且只有在equals它们不是同一个对象时才会回退到可能更昂贵的调用。