HashMap中put的实现原理

朱雀 2024-03-26 22:12 173阅读 0赞

**先把源码放出来，方便理解过程**

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
    	    //n-table数组的长度，index-key存放在哪个index下标位置，tab和p临时table大小接收
            Node<K,V>[] tab; Node<K,V> p; int n, i;
    		//将全局tab = table判断是否为空，如果为空的情况下，或者长度=0开始对table对table实现扩容
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
    		//计算keyindex值 判断是否发生index冲突 i = (n - 1) & hash计算key对应的index值 p = tab[i]在数组中是否存在
            if ((p = tab[i = (n - 1) & hash]) == null)
    		    //存放index下标位置
                tab[i] = newNode(hash, key, value, null);
            else {
        
                Node<K,V> e; K k;
    			//如果Hash值相同且equals内容也相同，直接覆盖
                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) {
        
    				    //循环链表 如果链表为null的情况下，直接存放追加在next后面
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
    						//如果链表长度大于8且数组容量》=64链表转换成红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
    					//查找链表中是否存在该key，如果存在直接修改value值
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
    			//将新的value覆盖为老的value
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
    		//modCount 新增++
            ++modCount;
    		//扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

### put的过程 ###

（1）判断数组是否为空  
判断Node\[\]数组是否为空，为空的话按照初始长度开辟数组空间

if ((tab = table) == null || (n = tab.length) == 0)
          n = (tab = resize()).length;

（2）计算key-index值  
判断当前数组位置有没有元素，没有的话就把值插到当前位置，有的话就说明遇到了哈希碰撞

if ((p = tab[i = (n - 1) & hash]) == null)
    	 //存放index下标位置
         tab[i] = newNode(hash, key, value, null);

（3）判断Hash值是否相同且equals内容也是否相同

//如果Hash值相同且equals内容也相同，直接覆盖
    if (p.hash == hash &&
       ((k = p.key) == key || (key != null && key.equals(k))))
           e = p;

（4）判断是不是红黑树  
如果是红黑树，则插入到红黑树里面

else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

（5）循环链表 如果链表为null的情况下，直接存放追加在next后面

*  5.1 如果链表为p.next = null的情况下，直接存放追加在next后面,然后我们要检查一下如果链表长度大于8且数组容量>=64链表转换成红黑树

if ((e = p.next) == null) {
        
        p.next = newNode(hash, key, value, null);
    	//如果链表长度大于8且数组容量》=64链表转换成红黑树
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }

*  5.2 查找链表中是否存在该key，如果存在直接修改value值

if (e.hash == hash && 
    ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;

（6）将新的value覆盖为老的value

//将新的value覆盖为老的value
    if (e != null) {
         // existing mapping for key
       V oldValue = e.value;
       if (!onlyIfAbsent || oldValue == null)
          e.value = value;
          afterNodeAccess(e);
          return oldValue;
    }

（7）如果++size大于了threshold那么将进行扩容

if (++size > threshold)
        resize();

### 总结 ###

（1）先判断当前Node\[\]数组是不是为空，为空就新建，不为空就对hash值与容量-1做与运算得到数组下标  
（2）然后会判断当前数组位置有没有元素，没有的话就把值插到当前位置，有的话就说明遇到了哈希碰撞  
（3）遇到哈希碰撞后，如果Hash值相同且equals内容也相同，直接覆盖，就会看下当前链表是不是以红黑树的方式存储，是的话，就会遍历红黑树，看有没有相同key的元素，有就覆盖，没有就执行红黑树插入  
（4）如果是普通链表，则按普通链表的方式遍历链表的元素，判断p.next = null的情况下，直接存放追加在next后面,然后我们要检查一下如果链表长度大于8且数组容量>=64链表转换成红黑树，否则查找到链表中是否存在该key，如果存在直接修改value值，如果没有继续遍历  
（5）如果++size > threshold(阈值)就扩容