Java 集合框架：HashMap 的介绍、使用、原理与源码解析

Java 集合框架：HashMap 的介绍、使用、原理与源码解析

一、HashMap 的介绍

HashMap 是 Java 集合框架中的一种重要数据结构，它实现了 Map 接口，主要用于存储键值对。HashMap 允许 null 值和 null 键，但不保证元素的顺序。其底层是基于哈希表（数组 + 链表/红黑树）的实现，能够以常数时间复杂度（O(1)）进行插入、删除和查找操作。

二、HashMap 的使用

使用 HashMap 时，我们需要导入 java.util.HashMap 包。以下是一个简单的代码示例，展示了 HashMap 的基本用法：

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建 HashMap 对象
        HashMap<String, Integer> map = new HashMap<>();

        // 添加元素
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Orange", 3);
        map.put(null, 0); // 可以插入 null 键

        // 打印 HashMap
        System.out.println("原始 HashMap: " + map);

        // 获取元素
        System.out.println("获取 Apple 的值: " + map.get("Apple"));

        // 移除元素
        map.remove("Banana");
        System.out.println("移除 Banana 后的 HashMap: " + map);

        // 遍历 HashMap
        System.out.println("遍历 HashMap:");
        for (String key : map.keySet()) {
            System.out.println("键: " + key + ", 值: " + map.get(key));
        }
    }
}

三、HashMap 的原理

HashMap 的原理主要基于哈希表。具体过程如下：

1. 哈希函数：当我们将一个键（key）存入 HashMap 时，首先会调用哈希函数计算该键的哈希值。该哈希值会被映射到数组的一个索引位置。

2. 碰撞处理：由于哈希函数可能产生相同的哈希值，HashMap 使用链表或红黑树（当链表长度超过 8 时，自动转换为红黑树）来处理碰撞。每个数组的索引位置可以存储多个键值对。

3. 扩容机制：当 HashMap 的容量达到负载因子（默认为 0.75）时，会自动扩容。扩容时会重新计算每个元素的新索引并调整存储位置。

四、HashMap 源码解析

HashMap 的源码比较复杂，以下是其核心部分的解析：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; // 2^30
    // 默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 存储哈希表数据的数组
    transient Node<K,V>[] table;
    // 当前元素数量
    transient int size;
    // 负载因子
    final float loadFactor;

    // put 方法
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        // 计算存储位置
        int i = indexFor(hash, table.length);
        for (Node<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        // 添加新节点
        modCount++;
        addNode(hash, key, value, i);
        return null;
    }
}

在上述源码中，put 方法负责将键值对插入 HashMap 中，首先会计算哈希值，然后定位存储位置，处理碰撞情况。扩容和再哈希的逻辑在 addNode 和其他内部方法中处理。

五、小结

HashMap 在 Java 中广泛应用，其高效的查找和存储能力使其成为开发者的首选。在使用时，我们需要注意线程安全（可使用 ConcurrentHashMap）以及负载因子与初始容量的选择，以优化性能。在理解了其原理后，我们可以更好地利用 HashMap 这一强大的数据结构。