HashMap 并非线程安全的, 在多个线程 put 时, 会造成 key 之间的死循环. 当另一个线程调用这个 key 时, get()方法会一直执行, 导致线程积压, 最终造成 CPU 满.
问题原因分析
HashMap 结构
HashMap 通过一个数组 table[]来存储 key, 当放入一个 key 时, 通过 hash 算法计算 key 的下标, 并存储在数组的 table[i]处. 如果 table[]的尺寸很小, 当放入多个 key 时, 可能会出现下标相同, 这样就会在 table[i]处形成链表. 这时, 原本查找一个 key 需要耗时 O(1), 现在耗时变成了 O(n),n 为链表的长度.
因此, 为了提高查找效率, 当有新的 key 值存入时, 会检查 Hash 表的大小是否超过设定的 thredhold, 超过的话就会增加 Hash 表的大小, 这样子 Hash 表里的元素会重新计算一遍, 这个过程叫做 rehash.
正常的 Rehash 过程
假设原先 hash 的 size 是 2, 存放了三个元素 a,b,c, 都在 table[1]这里, rehash 后 size 为 4.
取出第一个 key 值 a, 计算 hasn 值为 3, 存放在 table[3];
取出第二个 key 值 b, 计算 hash 值为 1, 存放在 table[1];
取出第三个 key 值 c, 计算 hash 值为 3, 存放在 table[3], 与 key 值 a 形成链表, 且 c 的 next 指向了 a.
并发的 Rehash 过程
如果存在线程 1 和线程 2, 在 rehash 之前中, a,b,c 在 table[1]形成了链表, a 的 next 指向了 b, 这时发生了 put 操作, 两个线程同时进行了 rehash.
线程 1 在遍历 Hash 表元素中, 取 a.next 时被挂起.
线程 2 继续完成了 rehash 操作, 重组了链表, 重组结束后, b.next 指向了 a.
线程 1 继续执行, a.next 又指向了 b, 环形链表因此产生了.
这时, 当我们调用到同一链表的其他值时, 就会出现死循环, 线程一直会执行下去.
解决方案
HashTable
HashTable 是同步的, 对此对 HashTable 进行操作时, 都会锁住整个结构. 如果并发地修改, 会抛出异常.
HashTable 不支持在遍历时修改自身的元素, 否则会抛出 ConcurrentModificationException.
ConcurrentHashMap
ConcurrentHashMap 的锁是细粒度的, 将 hash 表分为 16 个桶 (默认), 每次需要时只会锁当前用到的桶. 而且在读是不会锁表, 完全支持并发操作. 只有在 size() 时会锁住整个表, 因此 ConcurrentHashMap 并发时效率更高.
此外, ConcurrentHashMap 则是在遍历迭代时发生改变不会抛出异常.
来源: http://www.bubuko.com/infodetail-2977130.html