PUT过程

  1.     public static void main(String[] args){
  2.         HashMap map = new HashMap();
  3.         map.put("java",10);//ok
  4.         map.put("php",10);//ok
  5.         map.put("java",20);//替换value
  6.         System.out.println("map="+map);
  7.     }
  9. 源码解析：
  11.     1. 执行构造器new HashMap，初始化加载因子（0.75），创建一个空数组HashMap$Node[] table = null
  12.     public HashMap() {
  13.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  14.     }
  15.     2. 执行put
  16.     public V put(K key, V value) { //key = "java",value = 10
  17.         return putVal(hash(key), key, value, false, true);
  18.     }
  19.     2.1 对key 进行hash 求值
  20.     static final int hash(Object key) {
  21.         int h;
  22.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  23.     }    
  24.     2.2 
  25.     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  26.                    boolean evict) {
  27.         Node<K,V>[] tab; Node<K,V> p; int n, i; //辅助变量
  28.         如果底层的数组是为空，或者 length = 0， 就扩容到16
  29.         if ((tab = table) == null || (n = tab.length) == 0)
  30.             n = (tab = resize()).length;
  31.         取出hash值对应的table 的索引位置的Node节点，如果为空，就直接把加入的数据直接放在当前node即可
  32.         if ((p = tab[i = (n - 1) & hash]) == null)
  33.             tab[i] = newNode(hash, key, value, null);
  34.         else {
  35.             Node<K,V> e; K k; 辅助变量
  36.                 // 如果table表的索引位置的key的hash值相同和新的key的hash值相同，并满足table现有的节点的key和准备准备添加的key是同一个对象，或者  equals返回真
  37.             if (p.hash == hash &&   
  38.                 ((k = p.key) == key || (key != null && key.equals(k))))
  39.                 e = p;
  40.             else if (p instanceof TreeNode)  //如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
  41.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  42.             else {
  43.                 //如果找到的节点，后面是链表，就循环比较
  44.                 for (int binCount = 0; ; ++binCount) {
  45.                     //如果整个链表，没有和他相同的,就加到该链表的最后
  46.                     if ((e = p.next) == null) {
  47.                         p.next = newNode(hash, key, value, null);
  48.                         //加入后，判断当前链表的个数，是否已经到8个，到8个，后就调用 treeifyBin 转为红黑树
  49.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  50.                             treeifyBin(tab, hash);
  51.                         break;
  52.                     }
  53.                     if (e.hash == hash && //如果在循环比较过程中，发现有相同的，就break，就只是替换value
  54.                         ((k = e.key) == key || (key != null && key.equals(k))))
  55.                         break;
  56.                     p = e;
  57.                 }
  58.             }
  59.             if (e != null) { // existing mapping for key
  60.                 V oldValue = e.value;
  61.                 if (!onlyIfAbsent || oldValue == null)
  62.                     e.value = value;  //新值替换旧值
  63.                 afterNodeAccess(e);
  64.                 return oldValue;
  65.             }
  66.         }
  67.         ++modCount;//每增加一个Node，就size ++
  68.         if (++size > threshold) // threshold 第一次12，第二次24，第三次48.
  69.             resize();
  70.         afterNodeInsertion(evict);
  71.         return null;
  72.     }        
  75.     转为红黑树
  76.     条件：1、table为null，或者大小还没有到64，暂时不树化，而是进行扩容
  77.     否则，才会真正的树化 -> 剪枝
  78.     final void treeifyBin(Node<K,V>[] tab, int hash) {
  79.         int n, index; Node<K,V> e;
  80.         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  81.             resize();
  82.          ............  
  83.     }

扩容机制

node数组的大小大于8，并且map的size大于64才会去树化，
node 数组大于8，会扩容

table 数组大于12会扩容。

参考视频地址
https://www.bilibili.com/video/BV1YA411T76k?p=41&spm_id_from=pageDriver