java - hashMap的内部实现

Question

我正在了解 hashMap 的内部实现，并且我需要一些相关的帮助。 HashMap在java 8中使用链表存储数据，它使用树形数据结构。下面是节点 Node 类构造函数，您能帮我理解为什么节点具有键的哈希值吗？

Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

Answer 1

您使用散列来计算 HashMap 中元素的位置。如果每次需要碰撞时，向 HashMap 添加一个键都需要重新计算哈希值，那么效率将非常低下 resolved 。不仅如此，某些对象可能具有昂贵的哈希函数(例如，String hashCode 遍历 String 中的每个字符)。总是希望计算一次此类函数并缓存它们以供以后使用(因为您应该 not 更改放置在 Map 中的对象的 hashCode/equals )。

让我们考虑一个半满的 HashMap (n/2)，其中独立元素被放入条目集中。对于添加的任何给定元素，存在 1/2 冲突概率(最小值)。可以填充 HashMap 的条目数量为 n，但默认加载因子为 0.75，这意味着我们有 3n/4 - n/2 = n/4 条目留下来填充。所有这些条目都必须没有哈希冲突，因为我们为每次冲突节省了时间(通过缓存)。假设不发生碰撞的最大可能概率为 1/2，我们看到概率为 1/2n/4 在 HashMap 扩展之前没有发生冲突。这意味着对于任何相当大的 HashMap(n=29+，其中只需填充 0.5*29=(大约 15)个键)，您有超过 99% 的机会得到缓存哈希值节省时间。

tl;dr 它可以节省时间，特别是当添加/查找的冲突变得频繁时。