hashMap小记

2019-06-07 11:46:04  卢浮宫  版权声明:本文为站长原创文章,转载请写明出处


一、前言

    一直想写一下hashMap的相关总结,今天算是正式进行了吧。


二、重大变更

    简要说明jdk1.8相较于jdk1.7还是有很大区别的,这里会简要说一些1.7的版本,主要内容还是放在了1.8上的


三、首先从put来说吧

    ①在1.7中hashMap是一个数组,数组里面是一个个链表元素。

    ②其容量保持在2的n次方,也就是说每次扩容会是原来的2倍

    ③默认的负载因子为0.75 (关于负载因子后面会单独出一片文章)

    ④在进行插入第一个元素时会初始化数组大小

    ⑤拿到key的hash值并去寻找对应的数组下标

    ⑥遍历对应下标的链表,查看是否存在这个对应的key

    ⑦如果有则直接覆盖,没有则写入到该链表中(hash()和equals()结合来检测是否存在相同key)


四、jdk1.8中hashMap的变化 

    我们知道hashMap是根据key的hash()值来找到对应下标然后遍历其所属链表的。那么如果这个查到的链表长度是很大的就会增加整个操作的复杂度,这个复杂度是O(n)

    于是乎,在1.8中就引入了红黑树,也就是说在1.8中hashMap是由数组+链表+红黑树组成的

    在应对上述复杂度问题时,jdk1.8会在链表长度超出8时自动使用红黑树代替链表进行存储以降低其复杂度


五、get流程

    ①根据key拿到对应的数组下标

    ②遍历下标对应的链表

    ③直到找到对应的key (equals()判断)


六、jdk1.7中的ConcurrentHashMap

    在一次多线程操作中我使用hashMap进行数据读取和存储发现给出下面异常  java.util.ConcurrentModificationException

    查资料就开始了ConcurrentHashMap的使用之旅

    下面介绍下ConcurrentHashMap是如何支持并发操作的


七、ConcurrentHashMap如何支持并发操作

    在1.7中ConcurrentHashMap使用分段锁的机制来实现并发操作的

    ConcurrentHashMap是由一个个的segment组成的,也就是说数据是放在一个个的segment中的,如果每一个segment支持了线程安全的话,那么整个ConcurrentHashMap也就是线程安全的了

    总结:jdk1.7中是用segment来进行颗粒拆分,在put是锁住segment,在get时不进行加锁。但是由于其复杂度受链表长度影响所以在其链表长度过高时效率还是很低。

    

八、jdk1.8中的ConcurrentHashMap

    jdk8中摒弃了复杂的分段锁机制,主要有:

    1、不采用segment而采用node,锁住node来实现减小锁粒度。
    2、设计了MOVED状态 当resize的中过程中 线程2还在put数据,线程2会帮助resize。
    3、使用3个CAS操作来确保node的一些操作的原子性,这种方式代替了锁。
    4、sizeCtl的不同值来代表不同含义,起到了控制的作用



更多精彩请关注guangmuhua.com


最新评论:

sj
2019-06-21 10:35:37
1楼