【零基础学java】（HashMap源码解析--链表或红黑树元素添加，元素覆盖）

前言：元素的覆盖并不是简单把要添加的键值对进行整体替换，而是保持哈希值，键不变，对值进行替换，覆盖，并返回被覆盖的值，本篇文章会从源码的角度进行深度解析逻辑背后的代码

数组位置不为null，且元素不重复，挂在下面形成链表或者红黑树。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {    //定义一个局部变量，用来记录哈希表中数组的地址值。         Node<K,V>[] tab;  //临时的第三方变量，用来记录键值对对象的地址值         Node<K,V> p;  //表示当前数组的长度         int n;  //表示索引         int i;  //把哈希表中数组的地址值，赋值给局部变量tab         tab = table;

        if (tab == null || (n = tab.length) == 0){             //1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组     //2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件             //如果没有达到扩容条件，底层不会做任何操作             //如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中    tab = resize();  //表示把当前数组的长度赋值给n     n = tab.length;         }

//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置         i = (n - 1) & hash;//index    //获取数组中对应元素的数据         p = tab[i];

else {             Node<K,V> e;             K k;             //等号的左边：数组中键值对的哈希值             //等号的右边：当前要添加键值对的哈希值             //如果键不一样，此时返回false             //如果键一样，返回true             boolean b1 = p.hash（数组中键值对的哈希值） == hash(要添加键值对的哈希值);             if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){                 e = p;    （执行）

1. } else if (p instanceof TreeNode){                 //判断数组中获取出来的键值对是不是红黑树中的节点                 //如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);             }

2.else {                 //如果从数组中获取出来的键值对不是红黑树中的节点                 //表示此时下面挂的是链表                 for (int binCount = 0; ; ++binCount) {                     if ((e = p.next) == null) {                         //此时就会创建一个新的节点，挂在下面形成链表                         p.next = newNode(hash, key, value, null);    //判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin    //treeifyBin方法的底层还会继续判断                       //判断数组的长度是否大于等于64                         //如果同时满足这两个条件，就会把这个链表转成红黑树                         if (binCount >= TREEIFY_THRESHOLD - 1)                             treeifyBin(tab, hash);                         break;（跳出循环）                     }

数组位置不为null，键重复，元素覆盖

前面进行的步骤一样，主要是下面的条件判断

                    //e：              0x0044  ddd  444                     //要添加的元素： 0x0055   ddd   555                     //如果哈希值一样，就会调用equals方法比较内部的属性值是否相同                     if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){                          break;                     }

    p = e;                 }             }             //如果e为null，表示当前不需要覆盖任何元素    //如果e不为null，表示当前的键是一样的，值会被覆盖             //e:0x0044  ddd  555             //要添加的元素： 0x0055   ddd   555             if (e != null) {                 V oldValue = e.value;                 if (!onlyIfAbsent || oldValue == null){                     //等号的右边：当前要添加的值                     //等号的左边：0x0044的值    e.value = value;（值的覆盖）                 }                 afterNodeAccess(e); return oldValue;（返回被覆盖的值）             }         }

 //threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12         if (++size > threshold){              resize();         }         //表示当前没有覆盖任何元素，返回null         return null;     }