首页 > 面试被问到concurrent hashmap,赶紧背这几条
头像
cathy_cathy
编辑于 2021-08-05 10:22
+ 关注

面试被问到concurrent hashmap,赶紧背这几条

美团到店事业群平台技术部,秋招火热进行中!

内推方式一:
点击图片链接,查看内推二维码,扫码投简历https://www.cnblogs.com/CATHY-MU/p/15102097.html

内推方式二:
登陆美团招聘官网( https://campus.meituan.com/),选择岗位投递简历,在内推码输入框中填写内推码(OYkaHKQ

平台技术部校招咨询qq群 821133476,入群第一时间获知校招岗位开放信息,第一时间获知补录岗位开放信息,快人一步!

其他文章:
面试被问到.class文件结构,赶紧背这几条!
https://www.nowcoder.com/discuss/684230?source_id=profile_create_nctrack&channel=-1
面试被问到jdk监控工具,赶紧背这几条!
https://www.nowcoder.com/discuss/685100?source_id=profile_create_nctrack&channel=-1
面试被问到操作系统,赶紧背这几条!
https://www.nowcoder.com/discuss/686243?source_id=profile_create_nctrack&channel=-1
面试被问到垃圾回收,赶紧背这几条!
面试被问到散列表,赶紧背这几条!
面试被问到内存管理,赶紧背这几条!
面试被问到arraylist,赶紧背这几条!
面试被问到hashmap,赶紧背这几条!
面试被问到linkedhashmap,赶紧背这几条!

一个concurrentHashMap是一个segment数组
一个segment里是个hashEntry数组
对不同的segment进行操作无需考虑锁竞争

segment也有负载因子、阈值,segment的数量是2的幂,容量也是2的幂。

concurrentHashmap的put:
1.定位到segment
2.如果segment为空,初始化segment
3.对segment调用put

初始化segment

  • 检查计算得到的位置的 Segment 是否为null.
  • 为 null 继续初始化,使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。
  • 再次检查计算得到的指定位置的 Segment 是否为null.
  • 使用创建的 HashEntry 数组初始化这个 Segment.
  • 自旋判断计算得到的指定位置的 Segment 是否为null,使用 CAS 在这个位置赋值为 Segment.

put

  1. tryLock() 获取锁,获取不到使用 scanAndLockForPut 方法继续获取。
  2. 计算 put 的数据要放入的 index 位置,然后获取这个位置上的 HashEntry 。
  3. 遍历 put 新元素,为什么要遍历?因为这里获取的 HashEntry 可能是一个空元素,也可能是链表已存在,所以要区别对待。

    • 如果这个位置上的 HashEntry 不存在:

      1. 如果当前容量大于扩容阀值,小于最大容量,进行扩容。
      2. 直接头插法插入。
    • 如果这个位置上的 HashEntry 存在:

      1. 判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值
      2. 不一致,获取链表下一个节点,直到发现相同进行值替换,或者链表表里完毕没有相同的。

        1. 如果当前容量大于扩容阀值,小于最大容量,进行扩容。
        2. 直接链表头插法插入。
  4. 如果要插入的位置之前已经存在,替换后返回旧值,否则返回 null.

get方法无需加锁,由于其中涉及到的共享变量都使用volatile修饰,volatile可以保证内存可见性,所以不会读取到过期数据。

假设有2^N个segment,那根据元素的高N位就可以判断元素在哪个segment中。

对volatile字段的写入操作happens-before于每一个后续的同一个字段的读操作。

每个HashEntry中的next也是final的,没法对链表最后一个元素增加一个后续entry所以新增一个entry的实现方式只能通过头结点来插入了。

我们要删除 e3这个entry,因为HashEntry中next的不可变,所以我们无法直接把e2的next指向e4,而是将要删除的节点之前的节点复制一份,形成新的链表。

get分两步:1.看看segment中entry的个数,2.找到entry时判断下value是否为空。这种机制如何保证另一个线程增加、删除、修改entry时,本线程不受影响?
1.增加:如果查找时对方对象还没有创建好,value会为空。
2.修改:volitale保证了读到的会是对方写好的
3.删除:看到了对方还没来得及删的问题也不大


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐