HashMap：密室、魔法和碰撞

让我们将 HashMap 想象成一座有秘密房间（桶）的城堡，每个房间前面都有魔法门 - 哈希函数。这个神奇的机制是如何运作的？当两个神奇的实体在同一个地方碰撞时会发生什么？让我们深入了解 HashMap 的秘密世界。首先我们来看看HashMap由什么组成。

HashMap 的基本组成部分

table数组：该数组是主要的数据存储。每个数组单元（或存储桶）都包含一个唯一的索引，其中可以存储值链，甚至在元素数量较多的情况下存储二叉树。

LoadFactor：LoadFactor指定HashMap在扩展之前可以填充多少。默认负载因子为0.75，在节省内存和访问速度之间取得平衡。当 HashMap 已满 75% 时，它会将表的大小加倍并重新分配元素以保持效率。

阈值：阈值是HashMap决定扩表的点。计算公式为（容量 * 负载系数）。例如，如果容量为 16，loadFactor 为 0.75，则阈值将为 12。当 HashMap 达到 12 个元素时，它会增加其大小。

大小跟踪 HashMap 中当前键值对的数量。

HashMap 中的每个键值对都存储在称为 Node 的结构中，其中包含：

密钥 - 密钥对的密钥，
value—该对的值，
hash - 基于 hashCode() 键计算的哈希值，
next - 发生冲突时指向链中下一个元素的链接。

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;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

每个节点在发生碰撞时都会连接到同一个存储桶中的下一个节点，从而创建一个链表。如果存储桶中累积了超过 8 个元素，这些列表会自动变成平衡二叉树。

哈希函数：钥匙如何找到它们的房间

想象一下，HashMap 是一座有许多房间的巨大城堡。每个房间都有一个唯一的号码，但是钥匙如何决定去哪个房间呢？这就是哈希函数的任务，哈希函数是一个神奇的工具，可以帮助确定特定密钥将被放置在哪个桶（房间）中。

当我们添加一个键时，putVal 方法会调用该键的 hashCode() 方法来创建一个哈希值，然后将其细化为均匀分布在各个存储桶中。
索引计算：HashMap使用公式 int index = hashCode & (length- 1) 计算表数组中指向bucket的索引。

这里的hashCode是key通过哈希函数接收到的唯一代码。然后我们对 length - 1 进行按位与运算。这相当于计算哈希码除以桶数的余数，从而确定桶数组中的索引。

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

因此，每个键都经过哈希函数并最终到达自己唯一的房间，其索引是使用按位 AND 计算的。

碰撞检查：如果桶为空，则添加新的键值对。如果不匹配，putVal 检查键是否匹配：

匹配 * — 值已更新。
*不匹配 - 发生冲突 - 进一步了解它们。

碰撞：相互开放的秘密房间

如果两把钥匙最终位于同一个房间（多把钥匙通向一个桶）会发生什么？在 HashMap 中，这称为冲突。这是当两个键具有相同的哈希码并试图进入同一个存储桶时。这什么时候可以实现？例如，我们错误地覆盖了哈希码。

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;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}

在此示例中，KeyWithSameHash 类有一个重写的 hashCode() 方法，该方法为所有实例返回相同的值，导致所有键最终位于表数组的同一单元格中：

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}

对于所有键，hashCode() 值为 42，因此每次添加键时，表中的存储桶索引都会相同。

但是钥匙并没有撞到头，而是打开了额外的门，将房间变成了通往新房间的神奇走廊。这些新房间本质上是解决碰撞的方法。

链表：当具有相同哈希码的两个键最终位于同一个存储桶中时，HashMap 会在该存储桶中创建一个链表。键继续存储在此列表中，如有必要，会使用 equals() 方法进行检查以确保键确实相同。

红黑树：当一个桶中的碰撞次数变得太高（走廊变得太长）时，HashMap将其转换为红黑树。这有助于加快搜索速度并防止重负载下速度变慢。

equals() 和 hashCode() 如何工作

为了使 HashMap 魔法正常工作，具有相同值的两个相同键返回相同的哈希码，并且使用 equals() 方法进行正确比较非常重要。这就像一个咒语，可以检查两个对象是否相同，即使它们可能以不同的方式表示。

hashCode()：每个对象必须有自己唯一的哈希码。这使得HashMap能够高效地找到需要放置key的bucket。
equals()：如果两个对象具有相同的哈希码，则 equals() 方法检查对象是否实际上相同。
如果不存在此检查，HashMap 可能会混淆两个不同的键，从而导致不正确的程序行为。

结论

HashMap 的世界是一个神奇的世界，散列函数和碰撞帮助钥匙找到它们的房间并保持城堡的秩序。由于哈希函数，每个键都有自己的通向唯一索引的路径。当两个钥匙在同一个桶中碰撞时，魔法会继续发挥作用，以链表或红黑树的形式打开新的门来找到正确的路径。

因此，得益于 hashCode()、equals() 和神奇的碰撞走廊，HashMap 仍然是 Java 开发人员武器库中最强大的工具之一，即使在最混乱的情况下也能保证效率和准确性。

以上是HashMap：密室、魔法和碰撞的详细内容。更多信息请关注PHP中文网其他相关文章！