您的位置:

Java中HashMap的put方法实现原理

一、数据结构介绍

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

public class HashMap extends AbstractMap
   
    implements Map
    , 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[] tab; Node
    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
     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
     )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 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的值,这个值设置过小会导致链表膨胀成红黑树的过快,大大降低查询性能。