谈谈HashMap线程不安全的体现

   <p>HashMap的原理以及如何实现，之前在 JDK7与JDK8中HashMap的实现 中已经说明了。</p>    <p>那么，为什么说HashMap是线程不安全的呢？它在多线程环境下，会发生什么情况呢？</p>    <h2><strong>1. resize死循环</strong></h2>    <p>我们都知道HashMap初始容量大小为16,一般来说，当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。</p>    <pre>  <code class="language-java">void resize(int newCapacity) {          Entry[] oldTable = table;          int oldCapacity = oldTable.length;          if (oldCapacity == MAXIMUM_CAPACITY) {              threshold = Integer.MAX_VALUE;              return;          }            Entry[] newTable = new Entry[newCapacity];          transfer(newTable, initHashSeedAsNeeded(newCapacity));          table = newTable;          threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);  }</code></pre>    <pre>  <code class="language-java">void transfer(Entry[] newTable, boolean rehash) {          int newCapacity = newTable.length;          for (Entry<K,V> e : table) {              while(null != e) {                  Entry<K,V> next = e.next;                  if (rehash) {                      e.hash = null == e.key ? 0 : hash(e.key);                  }                  int i = indexFor(e.hash, newCapacity);                  e.next = newTable[i];                  newTable[i] = e;                  e = next;              }          }  }</code></pre>    <p>大概看下transfer：</p>    <ol>     <li> <p>对索引数组中的元素遍历</p> </li>     <li> <p>对链表上的每一个节点遍历：用 next 取得要转移那个元素的下一个，将 e 转移到新 Hash 表的头部，使用头插法插入节点。</p> </li>     <li> <p>循环2，直到链表节点全部转移</p> </li>     <li> <p>循环1，直到所有索引数组全部转移</p> </li>    </ol>    <p>经过这几步，我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。这时候就有点头绪了，死锁问题不就是因为1->2的同时2->1造成的吗？所以，HashMap 的死锁问题就出在这个 transfer() 函数上。</p>    <h3><strong>1.1 单线程 rehash 详细演示</strong></h3>    <p>单线程情况下，rehash 不会出现任何问题：</p>    <ul>     <li> <p>假设hash算法就是最简单的 key mod table.length（也就是数组的长度）。</p> </li>     <li> <p>最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在 mod 2以后碰撞发生在 table[1]</p> </li>     <li> <p>接下来的三个步骤是 Hash表 resize 到4，并将所有的  <key,value>  重新rehash到新 Hash 表的过程</p> </li>    </ul>    <p>如图所示：</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/d4001123d2da0044a3b3b5b6e3866985.jpg"></p>    <h3><strong>1.2 多线程 rehash 详细演示</strong></h3>    <p>为了思路更清晰，我们只将关键代码展示出来</p>    <pre>  <code class="language-java">while(null != e) {      Entry<K,V> next = e.next;      e.next = newTable[i];      newTable[i] = e;      e = next;  }</code></pre>    <ol>     <li>Entry<K,V> next = e.next; ——因为是单链表，如果要转移头指针，一定要保存下一个结点，不然转移后链表就丢了</li>     <li>e.next = newTable[i]; ——e 要插入到链表的头部，所以要先用 e.next 指向新的 Hash 表第一个元素（为什么不加到新链表最后？因为复杂度是 O（N））</li>     <li>newTable[i] = e; ——现在新 Hash 表的头指针仍然指向 e 没转移前的第一个元素，所以需要将新 Hash 表的头指针指向 e</li>     <li>e = next ——转移 e 的下一个结点</li>    </ol>    <p>假设这里有两个线程同时执行了 put() 操作，并进入了 transfer() 环节</p>    <pre>  <code class="language-java">while(null != e) {      Entry<K,V> next = e.next; //线程1执行到这里被调度挂起了      e.next = newTable[i];      newTable[i] = e;      e = next;  }</code></pre>    <p>那么现在的状态为：</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/c03224eaf3e5042156ca75e054abadd3.jpg"></p>    <p>从上面的图我们可以看到，因为线程1的 e 指向了 key(3)，而 next 指向了 key(7)，在线程2 rehash 后，就指向了线程2 rehash 后的链表。</p>    <p>然后线程1被唤醒了：</p>    <ol>     <li>执行 e.next = newTable[i] ，于是 key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以 e.next = null ，</li>     <li>执行 newTable[i] = e ，所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了，e 处理完毕。</li>     <li>执行 e = next ，将 e 指向 next，所以新的 e 是 key(7)</li>    </ol>    <p>然后该执行 key(3)的 next 节点 key(7)了:</p>    <ol>     <li>现在的 e 节点是 key(7)，首先执行 Entry<K,V> next = e.next ,那么 next 就是 key(3)了</li>     <li>执行 e.next = newTable[i] ，于是key(7) 的 next 就成了 key(3)</li>     <li>执行 newTable[i] = e ，那么线程1的新 Hash 表第一个元素变成了 key(7)</li>     <li>执行 e = next ，将 e 指向 next，所以新的 e 是 key(3)</li>    </ol>    <p>这时候的状态图为：</p>    <p><img src="https://simg.open-open.com/show/f47720a0bfa6d8bd826cf462a1be0ede.jpg"></p>    <p>然后又该执行 key(7)的 next 节点 key(3)了：</p>    <ol>     <li>现在的 e 节点是 key(3)，首先执行 Entry<K,V> next = e.next ,那么 next 就是 null</li>     <li>执行 e.next = newTable[i] ，于是key(3) 的 next 就成了 key(7)</li>     <li>执行 newTable[i] = e ，那么线程1的新 Hash 表第一个元素变成了 key(3)</li>     <li>执行 e = next ，将 e 指向 next，所以新的 e 是 key(7)</li>    </ol>    <p>这时候的状态如图所示：</p>    <p><img src="https://simg.open-open.com/show/7b3cd701fce49894224cdae347bdc6a8.jpg"></p>    <p>很明显，环形链表出现了！！当然，现在还没有事情，因为下一个节点是 null，所以 transfer() 就完成了，等 put() 的其余过程搞定后，HashMap 的底层实现就是线程1的新 Hash 表了。</p>    <h2><strong>2. fail-fast</strong></h2>    <p>如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。</p>    <p>这个异常意在提醒开发者及早意识到线程安全问题。</p>    <p>顺便再记录一个HashMap的问题：</p>    <p>为什么String, Interger这样的wrapper类适合作为键？String, Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。</p>    <h2><strong>Reference：</strong></h2>    <p>1. http://hwl-sz.iteye.com/blog/1897468?utm_source=tuicool&utm_medium=referral</p>    <p>2. http://github.thinkingbar.com/hashmap-infinite-loop/</p>    <p>3. http://www.importnew.com/7099.html</p>    <p> </p>    <p>来自：http://www.importnew.com/22011.html</p>    <p> </p>