简单剖析Hashmap

时间：2024-01-20 21:20:00

剖析 Java Hashmap 源码

在 Java 的集合框架中，HashMap 是一颗璀璨的明珠。通过深入挖掘其源码，我们将揭开 HashMap 的神秘面纱，理解其底层原理、扩容机制和数据结构。

1. HashMap 源码导读

我们首先来看一段简单的代码，创建一个空的 HashMap：

import java.util.HashMap;

public class HashMapSource {

    public static void main(String[] args) {
        // 创建一个空的 HashMap
        HashMap<String, Integer> map = new HashMap<>();
    }
}

2. HashMap 底层原理 - 数组与链表

HashMap 的底层结构是一个数组，每个数组元素是一个链表的头节点。当我们添加键值对时，首先计算键的哈希码，然后通过哈希码找到对应的数组索引。如果发生哈希冲突，即不同键的哈希码映射到同一个索引，就在该索引处形成一个链表。这就是链表法处理碰撞的方式。

下面是一个简化的示例，演示了如何计算哈希码和确定数组索引：

import java.util.HashMap;

public class HashingExample {

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // 计算键 "Alice" 的哈希码
        int hash = "Alice".hashCode();

        // 根据哈希码确定数组索引
        int index = hash & (map.size() - 1);

        System.out.println("键 \"Alice\" 的哈希码: " + hash);
        System.out.println("对应的数组索引: " + index);
    }
}

3. 扩容机制 - Ensuring Capacity

HashMap 在扩容时，会将数组的长度翻倍，并重新计算每个元素的索引。这一过程在 resize() 方法中实现。我们看一下简化版本的代码：

import java.util.HashMap;

public class ResizeExample {

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>(16);

        // 添加键值对，触发扩容
        map.put("Alice", 95);
        map.put("Bob", 87);
        map.put("Charlie", 92);
    }
}

在这个例子中，初始容量为 16，当添加第四个键值对时，触发了扩容操作。

4. 数据结构 - Node 类的奥秘

HashMap 的每个键值对都存储在一个 Node 类的实例中。这个类有 hash、key、value 和 next 四个字段，用于保存哈希码、键、值以及下一个节点的引用。以下是一个简化的 Node 类：

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 的源码，我们揭示了其底层原理、扩容机制和数据结构。每一行代码都是如何促使 HashMap 这个数据结构在 Java 编程中大放异彩的关键。愿你对 HashMap 有了更深层次的理解，编码的路上更加得心应手！

相关文章