Java HashMap工作原理深入探讨(深入解析Java HashMap的工作原理)

一、HashMap简介

HashMap 是 Java 中非常常用的一个数据结构，它基于散列（Hash）原理实现，用于存储键值对（Key-Value Pair）。HashMap 允许使用任何类型的对象作为键或值，它提供了迅捷的查找、插入和删除操作。本文将深入探讨 HashMap 的工作原理。

二、HashMap 的核心原理

HashMap 的核心原理是基于数组和链表（或红黑树）实现的。它通过散列函数将键映射到数组中的一个位置，形成数组的索引。如果两个键的散列值相同或不同但映射到同一个索引，会出现冲突。HashMap 使用链表或红黑树来解决冲突。

三、HashMap 的数据结构

HashMap 的数据结构重点包括以下几个部分：

• 数组：用于存储键值对的数组，数组的长度是 2 的幂。
• 链表：当数组的某个索引位置出现冲突时，将冲突的键值对存储在链表中。
• 红黑树：当链表的长度超过一定阈值时，链表会转换成红黑树，以尽大概缩减损耗查找高效。

四、HashMap 的构造方法

HashMap 提供了多个构造方法，以下是一个常用的构造方法示例：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Initial Capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAX_ARRAY_SIZE)
        initialCapacity = MAX_ARRAY_SIZE;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = (int)(initialCapacity * loadFactor);
    this.table = new Entry[initialCapacity];
    this.size = 0;
}

在这个构造方法中，initialCapacity 即 HashMap 的初始容量，loadFactor 即负载因子。负载因子是衡量 HashMap 满的程度的一个标准，当 HashMap 中的元素数量约为容量与负载因子的乘积时，HashMap 会进行扩容操作。

五、HashMap 的 put 方法

HashMap 的 put 方法用于向 HashMap 中添加一个键值对。以下是 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 (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

首先，计算键的散列值，然后依散列值和数组长度计算出数组索引。接下来，遍历链表（或红黑树），如果找到相同的键，则替换对应的值。如果没有找到相同的键，则将新的键值对添加到链表（或红黑树）中。

六、HashMap 的 get 方法

HashMap 的 get 方法用于获取指定键的值。以下是 get 方法的核心实现：

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next)
        if (e.hash == hash && ((key == e.key) || key.equals(e.key)))
            return e.value;
    return null;
}

与 put 方法类似，首先计算键的散列值，然后依散列值和数组长度计算出数组索引。接下来，遍历链表（或红黑树），如果找到相同的键，则返回对应的值。如果没有找到相同的键，则返回 null。

七、HashMap 的扩容操作

当 HashMap 中的元素数量约为容量与负载因子的乘积时，HashMap 会进行扩容操作。以下是扩容操作的核心实现：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAX_ARRAY_SIZE) {
        if (size > MAX_ARRAY_SIZE)
            throw new OutOfMemoryError();
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
}

扩容操作会创建一个新的数组，其长度是原数组的两倍。然后，遍历原数组中的所有键值对，并将它们重新散列到新数组中。这个过程称为重新散列（Rehashing）。

八、HashMap 的线程平安性

HashMap 不是线程平安的，如果多个线程同时访问 HashMap，并且至少有一个线程在结构上修改了 map（添加或删除任何元素），这就必须外部同步。

以下是一个使用 HashMap 的单纯示例，展示了怎样在外部同步 HashMap：

Map map = new HashMap<>();
synchronized (map) {
    map.put("key1", "value1");
    String value = map.get("key1");
    System.out.println("Value: " + value);
}

在这个示例中，我们使用 synchronized 关键字来确保对 HashMap 的访问是线程平安的。

九、总结

HashMap 是 Java 中一个非常高效的数据结构，它基于散列原理实现，提供了迅捷的查找、插入和删除操作。本文深入探讨了 HashMap 的工作原理，包括数据结构、构造方法、put 和 get 方法、扩容操作以及线程平安性等方面。懂得 HashMap 的工作原理对于优化 Java 程序的性能具有重要意义。

本文由IT视界版权所有,禁止未经同意的情况下转发