Java中HashMap的put方法实现原理

发布时间：2023-05-11

一、数据结构介绍

HashMap是Java中常用的一种集合，是基于一定的hash算法实现的Key-value数据结构。HashMap类继承于AbstractMap类，实现了Map接口。HashMap的底层实现是数组加链表或红黑树，通过key的hash值来找到其在数组中的位置，然后将其存储在该位置的链表或红黑树中。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ...
}

二、put方法

put方法是HashMap中最关键的方法之一，它负责将一个键值对存储到Map中。put方法有两个参数，第一个是key，第二个是value，该方法的返回值是被替换的value，如果之前没有关联的value则返回null。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以看到，put方法的核心是putVal方法，该方法对外部不可见，它将key-value对插入到HashMap中，并且可以进行扩容和重新哈希处理。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

三、put实现原理

put方法主要通过以下几个步骤实现：

  1. 如果table为null，或者table数组长度为0，执行resize方法进行初始化，否则直接用当前table数组存储值。
  2. 通过(key.hash) & (n-1)计算key的哈希值，并找到它在table中需要存储的位置 i。
  3. 检查table[i]的这个位置是否已经有了值(e)，如果没有，就把新的键值对放到table[i]的位置上。
  4. 如果已经存在节点e，即table[i]位置已被占用，则需要进一步判断e和新插入元素的key是否相同，如果相同，则覆盖原本的值，否则，需要判断e所在节点的类型，如果是红黑树节点，则插入红黑树，否则在链表末尾追加节点。
  5. 如果链表长度超过TREEIFY_THRESHOLD(默认值为8)时，则将链表转化成红黑树。TREEIFY_THRESHOLD是为了避免链表过长导致查询时间复杂度增加。
  6. 在插入节点后，判断是否超过容量阈值(threshold)，如果超过，进行扩容操作，将table数组长度翻倍。

四、实战应用

下面是一个简单的HashMap使用示例，通过put方法向map中存储数据。

HashMap<Integer, String> map = new HashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
System.out.println(map.get(1)); //"one"
System.out.println(map.get(2)); //"two"
System.out.println(map.get(3)); //"three"

五、总结

本篇文章介绍了Java中HashMap的put方法实现原理，分别通过数据结构介绍、put方法、put实现原理和实战应用等方面进行了详细阐述。 为了保证HashMap的效率，需要在设计key的时候尽量避免哈希冲突，这样可以减少链表的长度，提高HashMap的查询效率。同时需要注意TREEIFY_THRESHOLD的值，这个值设置过小会导致链表膨胀成红黑树的过快，大大降低查询性能。

推荐文章