测试代码
注意 要在 JDK 7 下运行，JDK7以后否则扩容机制和 hash 的计算方法都变了
1. public static void main(String[] args) { 2. 3. // 测试 java 7 中哪些数字的 hash 结果相等 4. 5. System.out.println("长度为16时，桶下标为1的key"); 6. for (int i = 0; i < 64; i++) { 7. if (hash(i) % 16 == 1) { 8. System.out.println(i); 9. } 10. } 11. System.out.println("长度为32时，桶下标为1的key"); 12. for (int i = 0; i < 64; i++) { 13. if (hash(i) % 32 == 1) { 14. System.out.println(i); 15. } 16. } 17. // 1, 35, 16, 50 当大小为16时，它们在一个桶内 18. 19. final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 20. // 放 12 个元素 21. 22. map.put(2, null); 23. map.put(3, null); 24. map.put(4, null); 25. map.put(5, null); 26. map.put(6, null); 27. map.put(7, null); 28. map.put(8, null); 29. map.put(9, null); 30. map.put(10, null); 31. map.put(16, null); 32. map.put(35, null); 33. map.put(1, null); 34. 35. System.out.println("扩容前大小[main]:"+map.size()); 36. new Thread() { 37. @Override 38. 39. public void run() { 40. // 放第 13 个元素, 发生扩容 41. 42. map.put(50, null); 43. System.out.println("扩容后大小[Thread-0]:"+map.size()); 44. } 45. }.start(); 46. new Thread() { 47. @Override 48. 49. public void run() { 50. // 放第 13 个元素, 发生扩容 51. 52. map.put(50, null); 53. System.out.println("扩容后大小[Thread-1]:"+map.size()); 54. } 55. }.start(); 56. 57. 58. } 59. 60. 61. final static int hash(Object k) { 62. int h = 0; 63. if (0 != h && k instanceof String) { 64. return sun.misc.Hashing.stringHash32((String) k); 65. } 66. h ^= k.hashCode(); 67. h ^= (h >>> 20) ^ (h >>> 12); 68. return h ^ (h >>> 7) ^ (h >>> 4); 69. }
死链复现
调试工具使用 idea
在 HashMap 源码 590 行加断点
int newCapacity = newTable.length;
断点的条件如下，目的是让 HashMap 在扩容为 32 时，并且线程为 Thread-0 或 Thread-1 时停下来
1. newTable.length==32 && 2. ( 3. Thread.currentThread().getName().equals("Thread-0")|| 4. 5. Thread.currentThread().getName().equals("Thread-1") 6. )
断点暂停方式选择 Thread，否则在调试 Thread-0 时，Thread-1 无法恢复运行 运行代码，程序在预料的断点位置停了下来，输出
长度为16时，桶下标为1的key
1
16
35
50
长度为32时，桶下标为1的key
1
35
扩容前大小[main]:12
接下来进入扩容流程调试
在 HashMap 源码 594 行加断点
1. Entry<K,V> next = e.next; // 593 2. 3. if (rehash) // 594 4. // ...
这是为了观察 e 节点和 next 节点的状态，Thread-0 单步执行到 594 行，再 594 处再添加一个断点（条件Thread.currentThread().getName().equals("Thread-0")） 这时可以在 Variables 面板观察到 e 和 next 变量，使用 view as -> Object 查看节点状态
1. e (1)->(35)->(16)->null 2. next (35)->(16)->null
在 Threads 面板选中 Thread-1 恢复运行，可以看到控制台输出新的内容如下，Thread-1 扩容已完成
newTable[1] (35)->(1)->null
扩容后大小:13
这时 Thread-0 还停在 594 处， Variables 面板变量的状态已经变化为
1. e (1)->null 2. next (35)->(1)->null
为什么呢，因为 Thread-1 扩容时链表也是后加入的元素放入链表头，因此链表就倒过来了，但 Thread-1 虽然结 果正确，但它结束后 Thread-0 还要继续运行
接下来就可以单步调试（F8）观察死链的产生了
下一轮循环到 594，将 e 搬迁到 newTable 链表头
下一轮循环到 594，将 e 搬迁到 newTable 链表头
1. newTable[1] (35)->(1)->null 2. e (1)->null 3. next null
再看看源码
1. e.next = newTable[1]; 2. 3. // 这时 e (1,35) 4. // 而 newTable[1] (35,1)->(1,35) 因为是同一个对象 5. 6. 7. 8. newTable[1] = e; 9. 10. // 再尝试将 e 作为链表头, 死链已成 11. 12. 13. 14. e = next; 15. 16. // 虽然 next 是 null, 会进入下一个链表的复制, 但死链已经形成了
源码分析
HashMap 的并发死链发生在扩容时
1. void transfer(Entry[] newTable, boolean rehash) { 2. int newCapacity = newTable.length; 3. for (Entry<K,V> e : table) { 4. while(null != e) { 5. Entry<K,V> next = e.next; 6. // 1 处 7. 8. if (rehash) { 9. e.hash = null == e.key ? 0 : hash(e.key); 10. } 11. int i = indexFor(e.hash, newCapacity); 12. // 2 处 13. 14. // 将新元素加入 newTable[i], 原 newTable[i] 作为新元素的 next 15. 16. e.next = newTable[i]; 17. newTable[i] = e; 18. e = next; 19. } 20. } 21. }
假设 map 中初始元素是
原始链表，格式：[下标] (key,next) [1] (1,35)->(35,16)->(16,null)
线程 a 执行到 1 处 ，此时局部变量 e 为 (1,35)，而局部变量 next 为 (35,16) 线程 a 挂起
线程 b 开始执行 第一次循环
[1] (1,null)
第二次循环
[1] (35,1)->(1,null)
第三次循环
[1] (35,1)->(1,null) [17] (16,null)
切换回线程 a，此时局部变量 e 和 next 被恢复，引用没变但内容变了：e 的内容被改为 (1,null)，而 next 的内 容被改为 (35,1) 并链向 (1,null)
第一次循环
[1] (1,null)
第二次循环，注意这时 e 是 (35,1) 并链向 (1,null) 所以 next 又是 (1,null) [1] (35,1)->(1,null)
第三次循环，e 是 (1,null)，而 next 是 null，但 e 被放入链表头，这样 e.next 变成了 35 （2 处）
[1] (1,35)->(35,1)->(1,35)
已经是死链了
小结
究其原因，是因为在多线程环境下使用了非线程安全的 map 集合
JDK 8 虽然将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），但仍不意味着能 够在多线程环境下能够安全扩容，还会出现其它问题（如扩容丢数据）
