V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
crossoverJie
V2EX  ›  程序员

HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!

  •  
  •   crossoverJie ·
    crossoverJie · 2018-07-23 08:22:50 +08:00 · 5447 次点击
    这是一个创建于 2298 天前的主题,其中的信息可能已经有所发展或是发生改变。
    45 条回复    2019-03-30 00:38:38 +08:00
    AntiGameZ
        1
    AntiGameZ  
       2018-07-23 08:34:30 +08:00   ❤️ 1
    赞一下,Github 的文档整理的很有用,面试帮了不少忙
    crossoverJie
        2
    crossoverJie  
    OP
       2018-07-23 08:47:50 +08:00
    guoyuchuan
        3
    guoyuchuan  
       2018-07-23 09:28:07 +08:00
    正在看 GitHub 里面的东西,得用只是来充实自己。
    guoyuchuan
        4
    guoyuchuan  
       2018-07-23 09:28:58 +08:00
    你的博客加载好慢啊,得等一会才能进去
    nVoxel
        5
    nVoxel  
       2018-07-23 09:32:26 +08:00
    主题是不是换过?印象还挺深的~
    crossoverJie
        6
    crossoverJie  
    OP
       2018-07-23 09:43:48 +08:00
    @nVoxel #5 主题没换 就是换了一个配置 不想折腾博客了 但总得有点新鲜感
    crossoverJie
        7
    crossoverJie  
    OP
       2018-07-23 09:45:20 +08:00
    @guoyuchuan #4 没办法 用的 cloudflare 的 DNS 很慢,迁移到国内又要备案
    lsmgeb89
        8
    lsmgeb89  
       2018-07-23 09:48:58 +08:00
    只记得完全无锁的实现非常复杂
    amon
        9
    amon  
       2018-07-23 09:50:10 +08:00
    哎?每当关注了一个公众号不久,就在 v 站也看到作者。
    幸会幸会!
    crossoverJie
        10
    crossoverJie  
    OP
       2018-07-23 10:10:36 +08:00
    @amon #9 哈哈 V 站的人都超有趣的 很喜欢这里。
    LostMoonkin
        11
    LostMoonkin  
       2018-07-23 10:30:07 +08:00
    看着博客的背景总感觉我屏幕脏了 /doge
    chenjian026
        12
    chenjian026  
       2018-07-23 10:59:00 +08:00
    阿里的学渣.....
    crossoverJie
        13
    crossoverJie  
    OP
       2018-07-23 11:03:46 +08:00
    @chenjian026 #12 那篇还有人记着呢
    orm
        14
    orm  
       2018-07-23 13:59:30 +08:00
    博客访问很慢
    alamaya
        15
    alamaya  
       2018-07-23 14:31:37 +08:00
    当时看的时候觉得最复杂的是扩容那一块,你这篇好象没有涉及
    crossoverJie
        16
    crossoverJie  
    OP
       2018-07-23 14:52:03 +08:00
    @alamaya #15 嗯 扩容那块很复杂,得单独拿一篇讲才行。
    crossoverJie
        17
    crossoverJie  
    OP
       2018-07-23 15:01:58 +08:00
    @orm #14 看来迁回国内得提上议程了。
    llxx510200
        18
    llxx510200  
       2018-07-23 16:22:05 +08:00
    要是问我红黑树可咋整啊
    crossoverJie
        19
    crossoverJie  
    OP
       2018-07-23 16:29:37 +08:00
    @llxx510200 #18 这个我觉得能讲清楚为啥快,啥时候翻转这些就差不多了。具体实现确实很复杂
    liuzhen
        20
    liuzhen  
       2018-07-23 17:10:10 +08:00
    楼主博客可以转载到 oschina 吗?会备注原地址
    beny2mor
        21
    beny2mor  
       2018-07-23 17:14:02 +08:00
    mark 一下
    crossoverJie
        22
    crossoverJie  
    OP
       2018-07-23 17:52:12 +08:00
    @liuzhen #20 可以的。
    Antidictator
        23
    Antidictator  
       2018-07-23 18:27:39 +08:00 via iPhone
    支持一下
    LuckCode
        24
    LuckCode  
       2018-07-23 18:34:19 +08:00 via iPhone
    我去,从博客看到公众号,今天在 v 站看到了作者。
    缘分啊,py 交易一下。
    WildCat
        25
    WildCat  
       2018-07-23 18:35:11 +08:00   ❤️ 1
    支持。最近用 pandoc 把你的 repo 转换成了 epub 在手机上看,受益良多
    crossoverJie
        26
    crossoverJie  
    OP
       2018-07-23 18:42:07 +08:00
    @LuckCode #24 哈哈 我这是广撒网啊 你也是哪个网都钻进来了
    crossoverJie
        27
    crossoverJie  
    OP
       2018-07-23 18:43:32 +08:00
    @WildCat #25 👍 咋搞的呀,可以提个 Issue。

    https://github.com/crossoverJie/Java-Interview/issues/new
    zxq1002
        28
    zxq1002  
       2018-07-23 19:59:31 +08:00 via Android
    打开好慢。。
    WildCat
        29
    WildCat  
       2018-07-23 20:03:49 +08:00
    @crossoverJie 我目前转换的有问题,不过我先开个 issue 抛砖引玉吧
    crossoverJie
        30
    crossoverJie  
    OP
       2018-07-23 20:06:55 +08:00
    @zxq1002 #28 确实挺慢的,准备转到国内了。
    shiguiyou
        31
    shiguiyou  
       2018-07-24 08:35:47 +08:00
    打不开。。。
    crossoverJie
        32
    crossoverJie  
    OP
       2018-07-24 10:19:56 +08:00
    @shiguiyou #31 多等等 卡。。
    mrrobot97
        33
    mrrobot97  
       2018-07-24 10:23:36 +08:00
    safari 禁用了 Flash 打开网页后风扇开始怒吼..
    zpxshl
        34
    zpxshl  
       2018-07-24 12:31:03 +08:00 via Android
    我来提(请教)个问题。
    1.8 版 concurrentHM,当使用 cas 插入,如何保证结果对其他线程可见。 volatile 不保证数组元素的可见性。
    crossoverJie
        35
    crossoverJie  
    OP
       2018-07-24 13:11:58 +08:00
    @zpxshl #34

    在 put 判断当前位置为空用 CAS 写入之前调用的是:

    tabAt() 方法,它所依赖的是 Unsafe 包中的 getObjectVolatile() 可以保证可见性。
    zpxshl
        36
    zpxshl  
       2018-07-25 07:55:45 +08:00 via Android
    @crossoverJie
    #35 getObjectVolatile ()只能保证自己读到的是最新值。
    putObjectVolatile 才能保证将值写回主内存。
    crossoverJie
        37
    crossoverJie  
    OP
       2018-07-25 09:05:00 +08:00
    @zpxshl #36 嗯 你不是问的怎么保证可见性嘛,获取到的是最新值就不会有可见性的问题了。
    zpxshl
        38
    zpxshl  
       2018-07-25 10:04:12 +08:00 via Android
    @crossoverJie 可见性...... 是一个变量修改其他线程都可以见到。 你获取到最新值,(为空时) cas 插入。 此时数组元素被修改,如何保证其他线程见到你的修改?
    crossoverJie
        39
    crossoverJie  
    OP
       2018-07-25 10:28:51 +08:00
    @zpxshl #38 如何保证其他线程见到你的修改?

    其他线程在 tabAt()



    这里不就获取了到最新值了嘛?也就是获取到了其他线程的修改。

    get 的时候也是一样的:

    zpxshl
        40
    zpxshl  
       2018-07-25 12:27:44 +08:00 via Android
    @crossoverJie 朋友。getObjectVolatile 只是获得主内存的数据。并没有强制将其他线程的工作内存数据刷新回主内存的功能。 也就是说 当你 cas 修改数组数据后,如果没有将数据缓存刷回主内存。其他线程用 getObjectVolatile 也读不到最新的值。
    crossoverJie
        41
    crossoverJie  
    OP
       2018-07-25 13:09:23 +08:00
    @zpxshl #40 兄弟,我觉得这没有啥问题呀。



    用 CAS 的前提是,遍历数组的时候在 key 所映射的那个位置是空的,也就是没有其他线程使用的时候才会在 2 处利用 CAS 尝试写入一个 Node。

    也就是说写入成功的话是不会有线程竞争的,这样也就不会存在你说的可见性问题(如果这时有线程来做 get ,恰好也定位到这个位置,那在写入线程更新成功之前获取的肯定也是空)。

    如果写入失败,CAS 返回 false,这样就会重新从 1 处再次循环。

    这样如果当前位置有数据了那就会用 synchronized 来写,用 synchronized 的话也不会出现可见性问题。

    如果当前位置依然为空的话就会重复上面的步骤。
    zpxshl
        42
    zpxshl  
       2018-07-26 22:59:33 +08:00 via Android
    @crossoverJie
    a 线程,遍历数组的时候在 key 所映射的那个位置是空的,cas 插入成功。
    b 线程,同样找到那个位置发现同样为空( cas 插入的数值对 b 线程不一定可见的),又 cas 插入,那不就出问题啦?
    crossoverJie
        43
    crossoverJie  
    OP
       2018-07-27 00:59:37 +08:00
    @zpxshl #42

    如果 A 线程写入成功之后 B 线程就算是恰巧在 A 线程还未写入之前判断到是空进入了 CAS 的逻辑。

    由于最终调用的还是 casTabAt()



    底层调用的是 unsafe.compareAndSwapObject 方法,他的期望是当前值为 null ,才会写入一个新的 Node。

    由于该方法是线程安全的,此时当前值已经不为 null 了,所以必定会写入失败。

    还有一个是,虽然是用 volatile 修饰的数组,但是用的是 getObjectVolatile 和 putObjectVolatile,依然可以保证可见性。

    见:

    https://stackoverflow.com/questions/31534706/about-unsafe-getobjectvolatile-usage
    zpxshl
        44
    zpxshl  
       2018-07-27 15:37:01 +08:00
    @crossoverJie 感谢!
    c4f36e5766583218
        45
    c4f36e5766583218  
       2019-03-30 00:38:38 +08:00
    jdk7 先扩容再 put 值;
    ```
    void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
    }
    ```
    jdk8 先 put 值再扩容: ```java.util.HashMap#putVal(int, K, V, boolean, boolean)```

    为什么?这么改动?有什么区别吗?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1324 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 17:46 · PVG 01:46 · LAX 09:46 · JFK 12:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.