Java HashMap如何工作——内部机制解释

HashMap是Java中最常用的数据结构之一，以其效率著称。HashMap中的数据以键值对的形式存储。

在本文中，我将向您介绍Java中的HashMap。我们将探讨HashMap的常见操作，然后深入了解其内部工作原理。您将了解散列函数以及索引计算是如何进行的。最后，我们将探讨操作的时间复杂度，并简要讨论在并发环境中的行为。

Java中的`HashMap`是什么？

HashMap实现了Map接口，它是Java集合框架的一部分。它基于散列的概念。

散列是一种技术，它使用散列函数将任意大小的输入转换为固定大小的输出。在Java中生成的输出称为散列码，由整数值表示。散列码在HashMap中用于高效的查找和存储操作。

常见操作

正如我们上面讨论的，HashMap中的数据以键值对的形式存储。键是一个唯一的标识符，每个键都与一个值相关联。

以下是HashMap支持的一些常见操作。让我们通过一些简单的代码示例来了解这些方法的作用：

插入

此方法将新的键值对插入到HashMap中。
键值对的插入顺序不会被保持。
在插入过程中，如果已经存在一个键，则将现有的值替换为新传递的值。
你只能向HashMap中插入一个null键，但是可以有多个null值。

此操作的方法签名如下，后跟一个示例：

public V put(K key, V value)

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);

在上面的代码中，我们有一个HashMap示例，其中我们添加了一个类型为String的键和类型为Integer的值。

检索：

获取与给定键关联的值。
如果键在HashMap中不存在，则返回null。

此操作的方法签名如下，后跟一个示例：

public V get(Object key)

Integer value = map.get("apple"); // 返回 1

在上面的代码中，我们正在检索与键apple关联的值。

其他常见操作包括：

remove：移除指定键的键值对。如果找不到键，则返回null。
containsKey：检查特定的键是否存在于HashMap中。
containsValue：检查指定的值是否存在于HashMap中。

HashMap的内部结构

在内部，HashMap使用一个桶或箱的数组。每个桶是一个类型为Node的链表，用于表示HashMap的键值对。

static class Node<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;
    }
}

在上文中，你可以看到用于存储HashMap键值对的Node类的结构。

Node类具有以下字段：

hash：指的是键的hashCode。
key：指的是键值对中的键。
value：指的是与键关联的值。
next：作为指向下一个节点的引用。

HashMap 的基本实现基于哈希表，其性能取决于两个关键参数：初始容量和负载因子。哈希表类的原始javadoc定义了这两个参数如下：

容量是哈希表中的桶数量，初始容量只是在创建哈希表时的容量。
负载因子是衡量哈希表在自动增加容量之前可以变得多满的一个度量。

现在让我们尝试理解在HashMap中，基本操作put和get是如何工作的。

哈希函数

在插入（`put`）键值对时，`HashMap` 首先计算键的哈希码。哈希函数然后为键计算一个整数。类可以使用 `Object` 类的 `hashCode` 方法，或者覆盖此方法并提供自己的实现。（阅读关于哈希码合同在这里）。然后，将哈希码与它的最高16位（h `>>>` 16）进行异或（eXclusive OR）操作，以实现更均匀的分布。

异或是一种位运算，比较两个位，如果位不同则结果为1，如果位相同则结果为0。在此上下文中，使用无符号右移操作符 `>>>` 获得的哈希码与其最高16位进行位运算异或操作，有助于混合位，从而产生更均匀的哈希码。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

上面，您可以看到 `HashMap` 类的静态哈希方法。

想法是为每个键生成唯一的哈希码，但是哈希函数可能会为不同的键产生相同的哈希码。这导致了一个称为冲突的情况。我们将在下一节看到如何处理冲突。

索引计算

一旦生成了键的哈希码，`HashMap` 就会计算在桶数组内的一个索引，以确定键值对将存储在哪里。这是通过位运算与操作完成的，当数组长度是2的幂时，这是计算模数的有效方法。

int index = (n - 1) & hash;

在这里，我们计算的是桶数组的索引，其中 n 是桶数组的长度。

一旦计算出索引，键就会存储在桶数组的该索引位置。然而，如果有多个键最终具有相同的索引，就会发生冲突。在这种情况下，HashMap 采用以下两种方法之一来处理：

链表/链接：数组中的每个桶都是一个节点的链表。如果某个索引位置已经存在键，并且另一个键被散列到相同的索引，它将被添加到列表中。
树化：如果节点数量超过某个阈值，链表将被转换成树（这在 Java 8 中被引入）。

static final int TREEIFY_THRESHOLD = 8;

这是决定树化的阈值。

因此，拥有一个好的散列函数至关重要，它可以均匀地将键分布到各个桶中，并尽量减少冲突的可能性。

检索（get）和删除（remove）操作与插入（put）操作类似。以下是操作步骤：

检索（get）：使用散列函数计算哈希码 -> 计算使用哈希码的索引 -> 遍历链表或树以找到匹配键的节点。
删除（remove）：使用哈希函数计算哈希码 -> 使用哈希码计算索引 -> 从链表或树中删除节点。

时间复杂度

HashMap的基本操作，如put、get和remove，通常提供常数时间性能O(1)，假设键是均匀分布的。在键分布不良且发生许多冲突的情况下，这些操作可能会退化到线性时间复杂度O(n)。

在树化过程中，将长链冲突转换为平衡树，查找操作可以提高到更有效的对数时间复杂度O(log n)。

同步

HashMap的实现不是同步的。如果多个线程并发访问HashMap实例并在映射中遍历，如果任何一个线程在映射中对键值映射进行结构修改（如添加或删除），都会导致ConcurrentModificationException。

为了防止这种情况，您可以使用Collections.synchronizedMap方法创建一个线程安全的实例。

结论

总之，了解HashMap的内部工作原理对于开发人员做出明智决策至关重要。了解键是如何映射的，碰撞是如何发生的，以及如何避免碰撞，可以帮助您高效且有效地使用HashMap。

Java中的HashMap是什么？