为什么 hashCode() 在遍历具有乘法值的桶时被调用一次？

Question

我有一个关注者class

public class Animal {

    private int hash;

    public Animal(int hash) {
        this.hash = hash;
    }

    @Override
    public int hashCode() {
        System.out.println(hash);
        return hash;
    }
}

还有这段代码

    public static void main(String[] args) {
        Map<Animal, Integer> map = new HashMap<>();
        for (int i = 0; i < 4; i++) {
            map.put(new Animal(16 * i), i);
        }

        Animal an = new Animal(16*4);
        map.put(an, 1);

        for (int i = 5; i < 9; i++) {
            map.put(new Animal(16 * i), i);
        }
        Integer value = map.get(an);
    }

据我所知，所有这些值都应该在一个桶中（由于它们的哈希码）。在最后一次调用 map.get(an) 时，hashCode() 仅被调用一次（根据控制台），但在遍历存储桶并找到具有正确 hashCode() 的条目时不应该调用多次吗？

EDIT1：如果我实施 equals（使用控制台日志记录），它也不会被调用（再次根据控制台），只有当有两个 相同的对象时才会调用它 哈希码（例如，如果我将此添加到我的代码 map.put(new Animal(16*3), 4);，在这种情况下，当从地图获取对象时，hashCode() 被调用两次）。

Answer 1

不，哈希码用于查找存储桶，这需要一次调用 hashcode（在 map.get(an) 的参数上调用）。

然后将桶中的元素与 equals() 进行比较以找到正确的对象。

Answer 2

单个存储桶可能包含具有不同 hashCode 的键，并且将相关存储桶的键的 hashCode 与您要 adding/searching 的键进行比较。但是，hashCode 缓存在 Map.Entry 中，因此无需为 Map 中已有的 Entry 调用密钥的 hashCode 方法：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash; // here the hash code is cached
        this.key = key;
        this.value = value;
        this.next = next;
    }
    ...
}

不过那是一个实现细节。

您可以在此处看到用于定位给定 hash 和 key 的 Entry 的代码：

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // <--- here a cached hash is compared to hash
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&  // <--- here a cached hash is compared to hash
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

hash 与键的缓存 hash 值进行比较，这意味着无需再次调用 hashCode()。

Answer 3

最多你可以预期 hashCode() 被调用。调用次数是 HashMap 的一个实现细节，您不应期望任何特定行为，也不应期望观察到的行为是稳定的。由于 hashCode() 可以以不同的方式实现，甚至成本很高，因此只调用它一次是一个合理的选择，即使需要多次调用它也可以使用返回值而不是对 hashCode() 的新调用。然而，这只是一个猜测，不应假设。

Answer 4

每个人都已经回答了这个问题。我想从 HashMap 中捕获代码以提供更多信息

当我们从 Map 调用 .put 时，在内部他们首先调用 hashKey

在 hash() 方法中，您会看到调用了 hashCode()。

然后在 putVal 方法中，有几个地方被调用，如下所示

这就是为什么我们会多次调用 hashCode() 的原因。

HashMap的实现请查看linkhttps://github.com/frohoff/jdk8u-jdk/blob/master/src/share/classes/java/util/HashMap.java

Answer 5

确定存储桶后，HashMap 将使用 .eqauls 来确定与提供的对象匹配的链表节点。查看实现：

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

Answer 6

map.put(new Animal(16 * i), i);

当你这样做时，Animal 对象是键，它的哈希值将是值 i 的桶。把它想象成 Animal 对象甚至没有存储在地图中。

当您添加所有 9 个项目时，值为 0,16,32,48,...,(16*8)

当您执行 map.get(aa) 时，an 的散列将从 an 对象返回，即 64。

tl;dr 所有对象属于不同的桶（因为它们的哈希值不同）

为什么 hashCode() 在遍历具有乘法值的桶时被调用一次？

Why is hashCode() called once in case of iterating through one bucket with multiply values?

java

equals

hashcode