HashMap(JDK-1.8)

一：resize扩容

  1. 当前table Node数组赋给临时变量，并记录老table的初始化容量和加载因子
  2. 如果老初始化容量大于0，新表初始化容量直接扩大为原来的2倍
  3. 循环老table，对新table赋值

1) 如果如果链表只有一个，则进行直接赋值newTab[e.hash & (newCap - 1)] = e

2）如果红黑二叉树：……

3）链表赋值，如果新表位置变化e.hash & oldCap) == 0, 则老表数据在新表位置为（老数组位置i+老数组容量oldCap）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
final Node<K, V>[] resize() {
      Node<K, V>[] oldTab = table;
      int oldCap = (oldTab == null) ? 0 : oldTab.length;// 数组长度
      int oldThr = threshold;// 临界值
      int newCap, newThr = 0;
      if (oldCap > 0) {
          // 扩容
          if (oldCap >= MAXIMUM_CAPACITY) {
              // 原数组长度大于最大容量(1073741824) 则将threshold设为Integer.MAX_VALUE=2147483647
              // 接近MAXIMUM_CAPACITY的两倍
              threshold = Integer.MAX_VALUE;
              return oldTab;
          } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
              // 新数组长度 是原来的2倍，
              // 临界值也扩大为原来2倍
              newThr = oldThr << 1;
          }
      } else if (oldThr > 0) {
          // 如果原来的thredshold大于0则将容量设为原来的thredshold
          // 在第一次带参数初始化时候会有这种情况
          newCap = oldThr;
      } else {
          // 在默认无参数初始化会有这种情况
          newCap = DEFAULT_INITIAL_CAPACITY;// 16
          newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 0.75*16=12
      }
      if (newThr == 0) {
          // 如果新 的容量 ==0
          float ft = (float) newCap * loadFactor;// loadFactor 哈希加载因子 默认0.75,可在初始化时传入,16*0.75=12 可以放12个键值对
          newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
      }
      threshold = newThr;// 将临界值设置为新临界值
      @SuppressWarnings({ "rawtypes", "unchecked" })
      // 扩容
      Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
      table = newTab;
      // 如果原来的table有数据，则将数据复制到新的table中
      if (oldTab != null) {
          // 根据容量进行循环整个数组，将非空元素进行复制
          for (int j = 0; j < oldCap; ++j) {
              Node<K, V> e;
              // 获取数组的第j个元素
              if ((e = oldTab[j]) != null) {
                  oldTab[j] = null;
                  // 如果链表只有一个，则进行直接赋值
                  if (e.next == null)
                      // e.hash & (newCap - 1) 确定元素存放位置
                      newTab[e.hash & (newCap - 1)] = e;
                  //  此处省略红黑树
                  else {
                      // 进行链表复制
                      // 方法比较特殊： 它并没有重新计算元素在数组中的位置
                      // 而是采用了 原始位置加原数组长度的方法计算得到位置
                      Node<K, V> loHead = null, loTail = null;
                      Node<K, V> hiHead = null, hiTail = null;
                      Node<K, V> next;
                      do {
                          next = e.next;
                          // 注意：不是(e.hash & (oldCap-1));而是(e.hash & oldCap)

                          // (e.hash & oldCap) 得到的是 元素的在数组中的位置是否需要移动,示例如下
                          // 示例1：
                          // e.hash=10 0000 1010
                          // oldCap=16 0001 0000
                          //   &   =0  0000 0000       比较高位的第一位 0
                          //结论：元素位置在扩容后数组中的位置没有发生改变

                          // 示例2：
                          // e.hash=17 0001 0001
                          // oldCap=16 0001 0000
                          //   &   =1  0001 0000      比较高位的第一位   1
                          //结论：元素位置在扩容后数组中的位置发生了改变，新的下标位置是原下标位置+原数组长度

                          // (e.hash & (oldCap-1)) 得到的是下标位置,示例如下
                          //   e.hash=10 0000 1010
                          // oldCap-1=15 0000 1111
                          //      &  =10 0000 1010

                          //   e.hash=17 0001 0001
                          // oldCap-1=15 0000 1111
                          //      &  =1  0000 0001

                          //新下标位置
                          //   e.hash=17 0001 0001
                          // newCap-1=31 0001 1111    newCap=32
                          //      &  =17 0001 0001    1+oldCap = 1+16

                          //元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
                          // 0000 0001->0001 0001

                          if ((e.hash & oldCap) == 0) {
                              // 如果原元素位置没有发生变化
                              if (loTail == null)
                                  loHead = e;// 确定首元素
                              // 第一次进入时     e   -> aa  ; loHead-> aa
                              else
                                  loTail.next = e;
                              //第二次进入时        loTail-> aa  ;    e  -> bb ;  loTail.next -> bb;而loHead和loTail是指向同一块内存的，所以loHead.next 地址为 bb  
                              //第三次进入时        loTail-> bb  ;    e  -> cc ;  loTail.next 地址为 cc;loHead.next.next = cc
                              loTail = e;
                              // 第一次进入时         e   -> aa  ; loTail-> aa loTail指向了和  loHead相同的内存空间
                              // 第二次进入时               e   -> bb  ; loTail-> bb loTail指向了和  loTail.next（loHead.next）相同的内存空间   loTail=loTail.next
                              // 第三次进入时               e   -> cc  ; loTail-> cc loTail指向了和  loTail.next(loHead.next.next)相同的内存
                          } else {
                              //与上面同理

                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);//这一块就是 旧链表迁移新链表
                      //总结：1.8中 旧链表迁移新链表    链表元素相对位置没有变化; 实际是对对象的内存地址进行操作 
                      //在1.7中  旧链表迁移新链表        如果在新表的数组索引位置相同，则链表元素会倒置
                      if (loTail != null) {
                          loTail.next = null;// 将链表的尾节点 的next 设置为空
                          newTab[j] = loHead;
                      }
                      if (hiTail != null) {
                          hiTail.next = null;// 将链表的尾节点 的next 设置为空
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }

二、线程安全

JDK-1.7 线程不安全

resize()导致线程不安全

1
2
3
4
5
6
7
transfer()函数逻辑
1. 对索引数组中的元素遍历
2. 对链表上的每一个节点遍历：用 next 取得要转移那个元素的下一个，将 e 转移到新 Hash 表的头部，使用头插法插入节点。
3. 循环2，直到链表节点全部转移
4. 循环1，直到所有索引数组全部转移

经过这几步，我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。这时候就有点头绪了，死锁问题不就是因为1->2的同时2->1造成的吗？所以，HashMap 的死锁问题就出在这个transfer()函数上。
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是码农<br>我为搬砖代言<br/>搬砖很快乐<br><br> 很惭愧<br>只会干体力活<br>谢谢大家