问题

这周看Java基础方面的知识，学习hashmap的时候，卡在一个问题好久：并发环境下使用hashmap是如何造成死循环的？我看了好几天都没搞明白，最后是老公给讲明白了。
这个问题是在jdk1.7环境下产生，jdk1.8修复了。因为1.7的时候rehash会倒置链表元素，并发情况下会死循环。

基础

  • 非线程安全。
  • key和value都支持null，但key为null只有一个，value为null 可以多个。

  • 初始容量和扩容：

    初始容量是16，扩容是2N。
    创建时如果给定了容量初始值，那hashmap会将其扩充为2的幂次方大小，hashmap总是使用2的幂作为哈希表的大小，为什么呢？一个是为了提高运算速度，因为是位运算；一个是为了提高哈希表的利用率，减少hash冲突。

  • 底层数据结构：jdk1.8之后是数组+链表+红黑树。当链表长度>8，会将链表转为红黑树，以减少搜索时间（将链表转换成红黑树之前会判断，如果数组长度<64，那么会先进行数组扩容，而不是转换为红黑树）

  • 解决hash冲突：链地址法、开放地址法

    分析

    image.png image.png
    如上初始情况hashmap桶数组只有2个位置，先后插入(“3”,”A”) (“7”,”B”) (“5”,”C”)，然后都冲突在 table[0] 了。单线程下rehash 迁移数组过程如下：
    1. void transfer(Entry[] newTable) {
    2.   Entry[] src = table;
    3.   int newCapacity = newTable.length;
    4.   //从Old Entry[]里摘一个元素出来，然后放到new Entry[]中
    5.   for (int j = 0; j < src.length; j++) {
    6.       Entry<K,V> e = src[j];
    7.       if (e != null) {
    8.           src[j] = null;
    9.           // 开始遍历table[0]的每一个节点entry，当前对象 e
    10.           do {
    11.               Entry<K,V> next = e.next;   // 把oldtable[0]处 e后边的链放到临时变量next里，此时next指向 key7
    12.               int i = indexFor(e.hash, newCapacity);  // 重新计算 当前对象e在 newTable里的索引位置
    13.               e.next = newTable[i];   // 把 newTable[i]下边的链放在 e.next 此时e已经组装完好了
    14.               newTable[i] = e;    // 把完整的e放入 newTable[i]里。
    15.               e = next;       // 当前对象指向 next 即key7
    16.           } while (e != null);
    17.       }
    18.   }
    19. }
    多线程下，如果线程1开始执行 如下，执行完第1句，CPU调度切换成线程2了，线程2开始扩容rehash，并且已经完成了rehash操作，如上图。
    1. do {
    2.   Entry<K,V> next = e.next;   // <--假设线程一执行到这里就被调度挂起了
    3.   int i = indexFor(e.hash, newCapacity);
    4.   e.next = newTable[i];
    5.   newTable[i] = e;
    6.   e = next;
    7. } while (e != null);
    这时候 CPU调度又切换成线程1了，那程序是如何执行的？
    1. do {
    2.   Entry<K,V> next = e.next;   // 把oldtable[0]处 e后边的链放到临时变量next里，此时next指向 key7
    3.   int i = indexFor(e.hash, newCapacity);  // 重新计算 当前对象e在 newTable里的索引位置
    4.   e.next = newTable[i];   // 把 newTable[i]下边的链放在 e.next 此时 newTable[0]里的链是指向7->3
    5.   newTable[i] = e;    // 把完整的e放入 newTable[i]里，所以当期e是3，e.next 又指向7->3，此时链就开始死循环了
    6.   e = next;       // 当前对象指向 next 即key7，可是7的next是3，3的next是7，就这样无限循环下去，CPU飙升100%
    7. } while (e != null);