JDK1.7中HashMap底层实现原理(4)

重新调整HashMap大小,当多线程的情况下可能产生条件竞争。因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

 五、线程安全

HashMap是线程不安全的,在多线程情况下直接使用HashMap会出现一些莫名其妙不可预知的问题。在多线程下使用HashMap,有几种方案:

A.在外部包装HashMap,实现同步机制

B.使用Map m = Collections.synchronizedMap(new HashMap(...));实现同步(官方参考方案,但不建议使用,使用迭代器遍历的时候修改映射结构容易出错)

D.使用Java.util.HashTable,效率最低(几乎被淘汰了)

E.使用java.util.concurrent.ConcurrentHashMap,相对安全,效率高(建议使用)

注意一个小问题,HashMap所有集合类视图所返回迭代器都是快速失败的(fail-fast),在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器自身的 remove 或 add 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。。因此,面对并发的修改,迭代器很快就会完全失败。

六、关于JDK1.8的问题

JDK1.8的HashMap源码实现和1.7是不一样的,有很大不同,其底层数据结构也不一样,引入了红黑树结构。有网友测试过,JDK1.8HashMap的性能要高于JDK1.7 15%以上,在某些size的区域上,甚至高于100%。随着size的变大,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。当一个链表长度大于8的时候,HashMap会动态的将它替换成一个红黑树(JDK1.8引入红黑树大程度优化了HashMap的性能),这会将时间复杂度从O(n)降为O(logn)。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/75cfb1e5b13aa5f5fa7ff75b3ca349bb.html