put方法方法

  1. public V put(K key, V value) {
  2.     // 根据key计算hashcode，相对于JDK7中hash算法有所简化
  3.     return putVal(hash(key), key, value, false, true);
  4. }

putVal方法方法

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  5.     // 给tab赋值，并判断数组是否为null，如果是则初始化数组，并得到数组大小n
  6.     if ((tab = table) == null || (n = tab.length) == 0)
  7.         n = (tab = resize()).length;
  9.     // 根据hashcode计算出对应的数组下标i，并判断该位置是否存在元素
  10.     // 如果为null，则生成一个Node对象赋值到该数组位置
  11.     // 否则，将该位置对应的元素取出来赋值给p
  12.     if ((p = tab[i = (n - 1) & hash]) == null)
  13.         tab[i] = newNode(hash, key, value, null);
  14.     else {
  15.         // 如果该下标位置存在元素，则进行一系列判断
  17.         Node<K,V> e; K k;
  19.         // 首先判断该下标位置存在的元素的key是否和当前put进来的key是否相等
  20.         // 如果相等，则再后续代码中更新value，并返回oldValue
  21.         if (p.hash == hash &&
  22.             ((k = p.key) == key || (key != null && key.equals(k))))
  23.             e = p;
  25.         // 如果该下标位置存在的元素的类型是TreeNode，表示该位置存的是一颗红黑树
  26.         // 那么就会把新元素添加到红黑树中，并且也会判断新key是否已经存在红黑树中
  27.         // 如果存在则返回该TreeNode，并在后续代码中更新value
  28.         else if (p instanceof TreeNode)
  29.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  30.         else {
  31.             // 否则该位置存的是一个链表，那就要把新元素插入到链表中
  32.             // 因为要看当前链表的长度，所以就需要遍历链表
  33.             // 在遍历链表的过程中，一边记录链表上的元素个数，一边判断是否存在相同的key
  34.             // 遍历到尾节点后，将新元素封装为Node对象并插入到链表的尾部
  35.             // 并且链表上的元素个数如果已经有8个了（不包括新元素对应的节点），则将链表改造为红黑树
  36.             for (int binCount = 0; ; ++binCount) {
  37.                 if ((e = p.next) == null) {
  38.                     p.next = newNode(hash, key, value, null);
  39.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  40.                         treeifyBin(tab, hash);
  41.                     break;
  42.                 }
  43.                 if (e.hash == hash &&
  44.                     ((k = e.key) == key || (key != null && key.equals(k))))
  45.                     break;
  46.                 p = e;
  47.             }
  48.         }
  50.         // 如果key存在相同的，则更新value，并返回oldValue
  51.         if (e != null) { // existing mapping for key
  52.             V oldValue = e.value;
  53.             if (!onlyIfAbsent || oldValue == null)
  54.                 e.value = value;
  55.             afterNodeAccess(e);
  56.             return oldValue;
  57.         }
  58.     }
  60.     // 增加修改次数
  61.     ++modCount;
  63.     // 新元素插入之后，判断是否需要扩容
  64.     if (++size > threshold)
  65.         resize();
  66.     afterNodeInsertion(evict);
  67.     return null;
  68. }

resize方法源码

  1. final Node<K,V>[] resize() {
  2.     // resize()包括数组初始化和扩容
  4.     // 记录当前数组信息
  5.     Node<K,V>[] oldTab = table;
  6.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  7.     int oldThr = threshold;
  9.     // 计算新数组的数组大小、扩容阈值
  10.     int newCap, newThr = 0;
  12.     // 如果老数组大小大于0，则双倍扩容
  13.     if (oldCap > 0) {
  14.         if (oldCap >= MAXIMUM_CAPACITY) {
  15.             threshold = Integer.MAX_VALUE;
  16.             return oldTab;
  17.         }
  18.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  19.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  20.             newThr = oldThr << 1; // double threshold
  21.     }
  22.     // 表示要初始化数组，但是用户指定了初始化容量
  23.     else if (oldThr > 0) // initial capacity was placed in threshold
  24.         newCap = oldThr;
  25.     // 表示要初始化数组，用默认值
  26.     else {               // zero initial threshold signifies using defaults
  27.         newCap = DEFAULT_INITIAL_CAPACITY;
  28.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  29.     }
  30.     // 用新数组的大小计算新数组的扩容阈值
  31.     if (newThr == 0) {
  32.         float ft = (float)newCap * loadFactor;
  33.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  34.                   (int)ft : Integer.MAX_VALUE);
  35.     }
  36.     threshold = newThr;
  38.     // 生成新数组，并赋值给table属性
  39.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  40.     table = newTab;
  42.     // 如果是扩容，则把老数组上的元素转移到新数组上
  43.     if (oldTab != null) {
  44.         for (int j = 0; j < oldCap; ++j) {
  45.             Node<K,V> e;
  46.             // 遍历数组的每一个位置
  47.             if ((e = oldTab[j]) != null) {
  48.                 oldTab[j] = null;
  50.                 // 如果该位置只有一个元素，则直接转移到新数组上
  51.                 if (e.next == null)
  52.                     newTab[e.hash & (newCap - 1)] = e;
  53.                 // 如果该位置上的元素是TreeNode，则对这颗红黑树进行转移
  54.                 else if (e instanceof TreeNode)
  55.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  56.                 // 否则，该位置上是一个链表，则要转移该链表
  57.                 else { // preserve order
  59.                     // 将当前链表拆分成为两个链表，记录链表的头结点和尾结点
  60.                     Node<K,V> loHead = null, loTail = null;
  61.                     Node<K,V> hiHead = null, hiTail = null;
  62.                     Node<K,V> next;
  64.                     // 遍历链表
  65.                     do {
  66.                         next = e.next;
  67.                         // 加入低位链表
  68.                         if ((e.hash & oldCap) == 0) {
  69.                             if (loTail == null)
  70.                                 loHead = e;
  71.                             else
  72.                                 loTail.next = e;
  73.                             loTail = e;
  74.                         }
  75.                         // 加入高位链表
  76.                         else {
  77.                             if (hiTail == null)
  78.                                 hiHead = e;
  79.                             else
  80.                                 hiTail.next = e;
  81.                             hiTail = e;
  82.                         }
  83.                     } while ((e = next) != null);
  85.                     // 将拆分后的链表转移到新数组上
  86.                     if (loTail != null) {
  87.                         loTail.next = null;
  88.                         newTab[j] = loHead;
  89.                     }
  90.                     if (hiTail != null) {
  91.                         hiTail.next = null;
  92.                         newTab[j + oldCap] = hiHead;
  93.                     }
  94.                 }
  95.             }
  96.         }
  97.     }
  98.     return newTab;
  99. }

splite方法源码

  1. final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  2.     TreeNode<K,V> b = this;
  3.     // Relink into lo and hi lists, preserving order
  4.     TreeNode<K,V> loHead = null, loTail = null;
  5.     TreeNode<K,V> hiHead = null, hiTail = null;
  6.     int lc = 0, hc = 0;
  8.     // 由于红黑树是有链表改造而成，所以链表其实还是存在的
  9.     // 对链表进行高低拆分
  10.     for (TreeNode<K,V> e = b, next; e != null; e = next) {
  11.         next = (TreeNode<K,V>)e.next;
  12.         e.next = null;
  13.         if ((e.hash & bit) == 0) {
  14.             if ((e.prev = loTail) == null)
  15.                 loHead = e;
  16.             else
  17.                 loTail.next = e;
  18.             loTail = e;
  19.             ++lc;
  20.         }
  21.         else {
  22.             if ((e.prev = hiTail) == null)
  23.                 hiHead = e;
  24.             else
  25.                 hiTail.next = e;
  26.             hiTail = e;
  27.             ++hc;
  28.         }
  29.     }
  31.     // 拆分之后，如果存在低位链表，则看链表长度，如果小于等于UNTREEIFY_THRESHOLD
  32.     // 则把节点类型改为Node类型
  33.     if (loHead != null) {
  34.         if (lc <= UNTREEIFY_THRESHOLD)
  35.             tab[index] = loHead.untreeify(map);
  36.         else {
  37.             // 否则，把头结点转移到新节点（红黑树的根节点一定是链表的头节点）
  38.             tab[index] = loHead;
  39.             // 如果存在高位链表，
  40.             if (hiHead != null) // (else is already treeified)
  41.                 loHead.treeify(tab);
  42.         }
  43.     }
  45.     // 和上面类似
  46.     if (hiHead != null) {
  47.         if (hc <= UNTREEIFY_THRESHOLD)
  48.             tab[index + bit] = hiHead.untreeify(map);
  49.         else {
  50.             tab[index + bit] = hiHead;
  51.             if (loHead != null)
  52.                 hiHead.treeify(tab);
  53.         }
  54.     }
  55. }

treeifyBin方法源码

  1. final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.     int n, index; Node<K,V> e;
  4.     // 数组长度如果小于MIN_TREEIFY_CAPACITY(默认为64)，则会扩容
  5.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  6.         resize();
  7.     else if ((e = tab[index = (n - 1) & hash]) != null) {
  9.         // 把链表改造为双向链表，并且把节点类型改为TreeNode
  10.         TreeNode<K,V> hd = null, tl = null;
  11.         do {
  12.             TreeNode<K,V> p = replacementTreeNode(e, null);
  13.             if (tl == null)
  14.                 hd = p;
  15.             else {
  16.                 p.prev = tl;
  17.                 tl.next = p;
  18.             }
  19.             tl = p;
  20.         } while ((e = e.next) != null);
  22.         // 改造为红黑树
  23.         if ((tab[index] = hd) != null)
  24.             hd.treeify(tab);
  25.     }
  26. }