详解Java中HashMap的put方法实现原理

一、HashMap概述

HashMap是Java中常用的一种数据结构，它是基于哈希表实现的一种Map接口。在HashMap中，通过把key映射到数组上来实现快速访问。接下来，我们将针对HashMap的数据结构和put方法进行详解。

二、HashMap的数据结构

在看put方法实现原理之前，首先需要了解HashMap的数据结构，HashMap采用的数据结构是Array+LinkedList，即链表散列。它的核心在于把对象的关键字（key）映射到一个整数上，这个整数将作为一个索引，指向存储这个关键字的实际对象的位置。这个对象可以在数组的这个位置上或者在对应的链表中。

public class HashMap extends AbstractMap
   
    implements Map
    , Cloneable, Serializable {
    /** 存储元素的数组 */
    transient Node
     [] table; 
    /** HashMap的大小 */
    transient int size; 
    /** HashMap被修改的次数 */
    transient int modCount; 
    /** 阈值 */
    int threshold; 
    /** 加载因子 */
    final float loadFactor;
}

     
    
   
  

HashMap中存储元素的数组是Node类型，其中Node类型是一个双向链表结构，它的结构如下：

static class Node implements Map.Entry
    {
    final int hash; // 哈希值
    final K key; // 键
    V value; // 值
    Node
     next; // 指向下一个节点的引用
    ...
}

    
   
  

当在HashMap中添加元素的时候，它会计算出每个键(key)对应的哈希值，然后用哈希值除以数组长度，取得余数，把键(key)放入到相应的数组元素中。在同一个数组元素中，保留了一个链表结构，用来存储有相同哈希值的元素。

三、put方法实现原理

put方法是向HashMap中添加元素的方法，在了解了HashMap的数据结构后，我们来看看put方法的实现原理。

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

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)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

     
    
   
  

HashMap的put方法通过哈希值计算和数组索引计算来存储和定位元素。在执行put方法时，它首先计算出哈希值，然后找到对应的数组元素，如果该元素为null，则说明数组该位置没有元素，直接把新元素插入到数组中。

接下来，如果该元素不为null，则需要看一下当前元素的哈希值是否与新元素相同，如果相同，则需要比较这两个元素是否equals，如果equals返回true，则说明这个键已经存在于HashMap中，则把原来的value返回，否则，用新的value替换掉旧的value。

如果当前元素不为null，并且当前元素的哈希值与新元素的哈希值不同，则需要在当前元素的链表中往后查找，找到相同哈希值的元素，然后比较这两个元素是否equals，如果equals返回true，则说明这个键已经存在于HashMap中，则把原来的value返回，否则，用新的value替换掉旧的value。

在查询过程中，如果该元素为TreeNode类型，则说明该元素已经转换为红黑树，此时，需要执行红黑树结构插入操作。

如果链表的长度达到阈值TREEIFY_THRESHOLD（默认值为8），则需要把链表转换为红黑树结构，从而提高查询效率。

在把元素插入的过程中，如果HashMap中元素的个数达到了阈值，则需要扩大HashMap的容量，使得它可以容纳更多的元素。在扩容过程中，较小容量的哈希表会复制到新表中，并且所有的元素都将会根据它们的哈希值重新分区到新表中。

四、小结

HashMap是Java中的一个重要数据结构，它是一个非常优秀的哈希表实现。在添加元素时，它采用哈希值计算和数组索引定位元素，还采用了链表散列和红黑树结构，使得它的查询效率非常高。因此，在Java开发中，HashMap是一个常见的数据结构，尤其是存储键值对的场景。而理解HashMap的实现原理，则是理解Java中哈希表实现的基础。