jdk1.8中hashmap的扩容resize

当hashmap第一次插入元素、元素个数达到容量阀值threshold时，都会扩容resize(),源码：

（假设hashmap扩容前的node数组为旧横向node数组，扩容后的node数组为新横向node数组）

 1   final Node<K,V>[] resize() {

 2          Node<K,V>[] oldTab = table;

 3           int oldCap = (oldTab == null) ? 0 : oldTab.length;

 4          int oldThr = threshold;

 5           int newCap, newThr = 0;

 6           if (oldCap > 0) {

 7               if (oldCap >= MAXIMUM_CAPACITY) {

 8                   threshold = Integer.MAX_VALUE;

 9                   return oldTab;

10              }

11              else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

12                       oldCap >= DEFAULT_INITIAL_CAPACITY)  //注释1

13                  newThr = oldThr << 1; // double threshold

14          }

15          else if (oldThr > 0) // initial capacity was placed in threshold

16              newCap = oldThr;

17          else {               // zero initial threshold signifies using defaults

18              newCap = DEFAULT_INITIAL_CAPACITY;

19              newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

20          }

21          if (newThr == 0) {

22              float ft = (float)newCap * loadFactor;

23              newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

24                        (int)ft : Integer.MAX_VALUE);

25          }

26          threshold = newThr;

27          @SuppressWarnings({"rawtypes","unchecked"})

28              Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

29          table = newTab;

30          if (oldTab != null) {

31              for (int j = 0; j < oldCap; ++j) {  //注释2

32                  Node<K,V> e;

33                  if ((e = oldTab[j]) != null) {//注释3

34                      oldTab[j] = null;

35                      if (e.next == null)       //注释4

36                          newTab[e.hash & (newCap - 1)] = e;

37                      else if (e instanceof TreeNode) //注释5

38                          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

39                      else { // preserve order        //注释6

40                          Node<K,V> loHead = null, loTail = null; //注释7

41                          Node<K,V> hiHead = null, hiTail = null;//注释8

42                          Node<K,V> next;

43                          do {

44                              next = e.next;

45                              if ((e.hash & oldCap) == 0) { //注释9

46                                  if (loTail == null)  //注释10

47                                      loHead = e;

48                                  else

49                                      loTail.next = e;

50                                  loTail = e;

51                             }

52                              else {

53                                  if (hiTail == null)//注释11

54                                      hiHead = e;

55                                  else

56                                      hiTail.next = e;

57                                  hiTail = e;

58                              }

59                          } while ((e = next) != null);

60                          if (loTail != null) {  //注释12

61                              loTail.next = null;

62                              newTab[j] = loHead;

63                          }

64                          if (hiTail != null) {//注释13

65                              hiTail.next = null;

66                               newTab[j + oldCap] = hiHead;

67                          }

68                      }

69                 }

70              }

71          }

72          return newTab;

73      }

注释1：对新横向node数组的长度和容量阀值均扩容为2倍

注释2：遍历旧横向node数组中每个node节点，在后面的代码中对每个node节点重新分配下标位置到新横向node数组

注释3：旧横向node数组中当前节点为空，则跳过

注释4：旧横向node数组中当前节点若只有一个元素（构不成node链表、红黑树），则直接给该node节点分配下标位置到新横向node数组

注释5：旧横向node数组中当前节点是红黑树节点，则直接调用红黑树的split()方法对红黑树进行修剪

注释6：旧横向node数组中当前节点是普通链表头节点，则为该链表重新分配下标到新横向node数组

注释7：旧横向node数组中当前节点下标=重新分配的新横向node数组中当前节点下标，则用loHead 表示旧横向node数组中当前node节点（即链表头），用loTail 表示旧横向node数组中当前node节点的链表尾

注释8：与注释7相反，旧横向node数组中当前节点下标不等于重新分配的新横向node数组中当前节点下标，hiHead表示新横向node数组的链表头节点，hiTail 表示新横向node数组的链表尾节点

注释9：重点，见下图。当“hash值”和“容量”进行与操作时，若结果为0，则当前节点在新旧横向node数组下标相等；否则若结果不为0，则当前节点在新横向node数组下标=该节点在旧横向的下标+旧容量（即旧横向node数组的长度）

注释10：当前节点在新旧横向node数组下标相等，用loTail 、loHead 标识

注释11：当前节点在新旧横向node数组下标不相等，用hiTail、hiHead 标识

注释12：loTail不为空，代表当前节点在新旧横向node数组下标相等

注释13：hiTail 不为空，代表当前节点在新旧横向node数组下标不相等，即当前节点在新横向node数组下标=旧横向的下标+旧容量

巴特西

jdk1.8中hashmap的扩容resize

最新文章

热门文章