从添加一个key~value操作分析起，putVal是一个用final修饰的方法，可知是一个不予许被重写的方法，

传入key的hash值，相对应key~value,

将onlyIfAbsent设置false，意味着当传入的key已经存在时，当前的value会替换掉oldValue，否则只有当value为null时当前value才会替换oldValue

将evict设置为true，目前class中没有具体实现，可以认为没有意义。文档表达：if false, the table is in creation mode.

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

 

分析hash(key)

 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

通过key.hashCode()计算出key的哈希值，然后将哈希值h右移16位，再与原来的h做异或^运算。

 

补充：

“>>>”:按二进制形式把所有的数字向右移动对应位数，低位移出(舍弃)，高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。 其他结构和>>相似。

“^” : 位异或第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0 0^0=0， 1^0=1， 0^1=1， 1^1=0

 

主干流程分析：

1  final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 2                     boolean evict) { 3      Node
      
       [] tab; Node
       
         p; int n, i; 4      //step1:如果初次使用hashMap，进行初始化 5      if ((tab = table) == null || (n = tab.length) == 0) 6          n = (tab = resize()).length; 7      //step2:通过hash和（长度-1）做与操作寻址key索引位置-i，当tab[i]没有存值时直接加入，否则做hash冲突处理 8      if ((p = tab[i = (n - 1) & hash]) == null) 9          tab[i] = newNode(hash, key, value, null);10      else {11          Node
        
          e; K k;12          //step3:判断待添加的key与首元素的key是否相同13          if (p.hash == hash &&14              ((k = p.key) == key || (key != null && key.equals(k))))15              e = p;16          //step4:判断是否为红黑树结构，若是则进入到另一个方法处理17          else if (p instanceof TreeNode)18              //putTreeVal内部进行了遍历，存在相同hash时返回被覆盖的TreeNode，否则返回null。19              e = ((TreeNode
         
          )p).putTreeVal(this, tab, hash, key, value);20          //step5:否则是链表结构，执行相关操作，检查是否存在相同的key，否则添加到尾部，并进行检查是否转成红黑树【当链表长度大于等于8进行转换】21          else {22              for (int binCount = 0; ; ++binCount) {23                  if ((e = p.next) == null) {24                      p.next = newNode(hash, key, value, null);25                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st26                          treeifyBin(tab, hash);27                      break;28                  }29                  if (e.hash == hash &&30                      ((k = e.key) == key || (key != null && key.equals(k))))31                      break;32                  p = e;33              }34          }35          //step6:对已经有存在相同的key进行操作，返回oldValue36          //根据onlyIfAbsent，onlyIfAbsent为false时，意味着当传入的key已经存在时，当前的value会替换掉oldValue，否则只有当value为null时当前value才会替换oldValue37          if (e != null) { // existing mapping for key38              V oldValue = e.value;39              if (!onlyIfAbsent || oldValue == null)40                  e.value = value;41              afterNodeAccess(e);42              return oldValue;43          }44      }45      //step7:对新增元素操作，判断是否达需要扩容46      ++modCount;47      if (++size > threshold)48          resize();49      afterNodeInsertion(evict);50      return null;51  }
         
        
       
      

 

Q：寻址操作 (n - 1) & hash，为什么是n？

在table数组中寻址,利用了按位与操作的一个特点,1&1 才能为 1,那么也就是说,如果数组最大下标为15,那么不管hash是多少都不会大于15，也就不会数组越界

 

Q：如何判断是否扩容？

首先看下threshold的初始化

  /**  * The maximum capacity, used if a higher value is implicitly specified  * by either of the constructors with arguments.  * MUST be a power of two <= 1<<30.  */  //相当于2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; //threshold = 初始容量 * 加载因子。是扩容的门槛。相当于实际使用的容量。 int threshold; //int最大值为2^31，当赋予的初始值比MAXIMUM_CAPACITY大时，这时候再扩容threshold就会造成整型溢出。 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; this.threshold = tableSizeFor(initialCapacity); //返回一个大于等于且最接近 cap 的2的幂次方整数，如给定9，返回2的4次方16 static final int tableSizeFor(int cap) { //让cap-1再赋值给n的目的是另找到的目标值大于或等于原值 int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

再看扩容操作

1  //当HashMap中存在的node节点大于threshold时，hashmap进行扩容。 2  if (++size > threshold) 3          resize(); 4  ​ 5    final Node
      
       [] resize() { 6          Node
       
        [] oldTab = table; 7          int oldCap = (oldTab == null) ? 0 : oldTab.length; 8          int oldThr = threshold; 9          int newCap, newThr = 0;10          if (oldCap > 0) {11              //当容量预扩容比2^30大时，停止扩容12              if (oldCap >= MAXIMUM_CAPACITY) {13                  threshold = Integer.MAX_VALUE;14                  return oldTab;15              }16              //以自身两倍容量进行扩容17              else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&18                       oldCap >= DEFAULT_INITIAL_CAPACITY)19                  newThr = oldThr << 1; // double threshold20          }21          else if (oldThr > 0) // initial capacity was placed in threshold22              newCap = oldThr;23          else {               // zero initial threshold signifies using defaults24              newCap = DEFAULT_INITIAL_CAPACITY;25              newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);26          }27          if (newThr == 0) {28              float ft = (float)newCap * loadFactor;29              newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?30                        (int)ft : Integer.MAX_VALUE);31          }32          threshold = newThr;33          @SuppressWarnings({"rawtypes","unchecked"})34              Node
        
         [] newTab = (Node
         
          [])new Node[newCap];35          table = newTab;36          if (oldTab != null) {37              for (int j = 0; j < oldCap; ++j) {38                  Node
          
            e;39                  if ((e = oldTab[j]) != null) {40                      oldTab[j] = null;41                      if (e.next == null)42                          newTab[e.hash & (newCap - 1)] = e;43                      else if (e instanceof TreeNode)44                          ((TreeNode
           
            )e).split(this, newTab, j, oldCap);45 else { // preserve order46 Node
            
              loHead = null, loTail = null;47 Node
             
               hiHead = null, hiTail = null;48 Node
              
                next;49 do {50 next = e.next;51 if ((e.hash & oldCap) == 0) {52 if (loTail == null)53 loHead = e;54 else55 loTail.next = e;56 loTail = e;57 }58 else {59 if (hiTail == null)60 hiHead = e;61 else62 hiTail.next = e;63 hiTail = e;64 }65 } while ((e = next) != null);66 if (loTail != null) {67 loTail.next = null;68 newTab[j] = loHead;69 }70 if (hiTail != null) {71 hiTail.next = null;72 newTab[j + oldCap] = hiHead;73 }74 }75 }76 }77 }78 return newTab;79 }