深入探究HashMap.put方法实现细节

小蓝 • 2024-12-12 12:47 • 编程

在Java中，HashMap是应用最广泛的数据结构之一，它提供了一种基于键值对（key-value）的存储方式，可以快速地存取、删除和检索数据。其中，put方法是HashMap中最主要的方法之一，本文将从多个方面深入探究HashMap.put方法实现细节。

一、put方法的使用

在Java中，使用put方法将数据放入HashMap中，具体使用方式如下：

HashMap map = new HashMap();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

以上代码将三个键值对放入了HashMap中，即{“A”:1, “B”:2, “C”:3}。通过这种方式，就可以在HashMap中快速地存储和查找数据了。

二、put方法的实现

HashMap的底层实现是基于数组和链表（或红黑树）的，存储数据的时候，HashMap首先根据key的hashCode值来计算其在数组中的位置，然后将该位置上的数组元素作为链表头，如果链表头还没有存储过key-value，那么直接放入，否则需要遍历链表，找到最后一个元素后将其next指向新存储的元素。

下面是HashMap中put方法的重要代码实现：

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    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;
}

在上面的代码中，如果table数组还没有初始化，需要先进行初始化。然后，根据key的hashCode值和table数组的长度，计算其在数组中的位置。接着，遍历在该位置上的链表，如果找到了相同的key-value，则更新value值并返回旧值；如果没有找到，则将新的key-value插入到链表的末尾。

三、关于hash方法

在put方法的实现中，需要先调用hash方法计算key的hashCode值。下面是HashMap中hash方法的代码实现：

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

在上面的代码中，先获取hashSeed的值，如果该值不为0且key是String类型，就调用sun.misc.Hashing.stringHash32方法来计算hashCode值；否则，直接使用key的hashCode值。

为什么要进行h ^= (h >>> 20) ^ (h >>> 12)和h ^= (h >>> 7) ^ (h >>> 4)操作呢？这是为了使hashCode更加分散，从而减少哈希冲突的概率。上述操作使用了位运算，可以大幅提高计算效率。

四、关于扩容

当HashMap中元素数量达到了threshold（容量*负载因子）时，就会自动进行扩容操作。扩容实际上就是创建一个更大的table数组，然后将原来的元素重新分配到新数组中。下面是HashMap中resize方法的代码实现：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

在代码中，首先获取原table数组的长度，然后判断是否达到了最大容量（2的30次方）。如果已达到最大容量，则不再进行扩容。否则，创建一个新的Entry数组，调用transfer方法将原table数组中的元素重新分配到新数组中。最后将table指向新数组，同时更新threshold的值。

五、关于线程安全

HashMap并不是线程安全的，即如果多个线程同时对同一个HashMap进行操作，可能会出现不一致的结果。因此，在并发环境下应该使用ConcurrentHashMap来替代HashMap，后者是线程安全的。

六、小结

通过以上分析，我们深入探究了HashMap.put方法的实现细节。在使用HashMap的过程中，尤其要注意hash方法和扩容的相关实现，同时要在并发场景下使用线程安全的ConcurrentHashMap。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/242169.html