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

hashmap

concurrenthashmap

相信

篇

45 条回复 • 2019-03-30 00:38:38 +08:00

1

AntiGameZ

2018-07-23 08:34:30 +08:00

1

赞一下，Github 的文档整理的很有用，面试帮了不少忙

2

crossoverJie

OP

2018-07-23 08:47:50 +08:00

@AntiGameZ #1

3

guoyuchuan

2018-07-23 09:28:07 +08:00

正在看 GitHub 里面的东西，得用只是来充实自己。

4

guoyuchuan

2018-07-23 09:28:58 +08:00

你的博客加载好慢啊，得等一会才能进去

5

nVoxel

2018-07-23 09:32:26 +08:00

主题是不是换过?印象还挺深的~

6

crossoverJie

OP

2018-07-23 09:43:48 +08:00

@nVoxel #5 主题没换就是换了一个配置不想折腾博客了但总得有点新鲜感

7

crossoverJie

OP

2018-07-23 09:45:20 +08:00

@guoyuchuan #4 没办法用的 cloudflare 的 DNS 很慢，迁移到国内又要备案

8

lsmgeb89

2018-07-23 09:48:58 +08:00

只记得完全无锁的实现非常复杂

9

amon

2018-07-23 09:50:10 +08:00

哎？每当关注了一个公众号不久，就在 v 站也看到作者。
幸会幸会！

10

crossoverJie

OP

2018-07-23 10:10:36 +08:00

@amon #9 哈哈 V 站的人都超有趣的很喜欢这里。

11

LostMoonkin

2018-07-23 10:30:07 +08:00

看着博客的背景总感觉我屏幕脏了 /doge

12

chenjian026

2018-07-23 10:59:00 +08:00

阿里的学渣.....

13

crossoverJie

OP

2018-07-23 11:03:46 +08:00

@chenjian026 #12 那篇还有人记着呢

14

orm

2018-07-23 13:59:30 +08:00

博客访问很慢

15

alamaya

2018-07-23 14:31:37 +08:00

当时看的时候觉得最复杂的是扩容那一块，你这篇好象没有涉及

16

crossoverJie

OP

2018-07-23 14:52:03 +08:00

@alamaya #15 嗯扩容那块很复杂，得单独拿一篇讲才行。

17

crossoverJie

OP

2018-07-23 15:01:58 +08:00

@orm #14 看来迁回国内得提上议程了。

18

llxx510200

2018-07-23 16:22:05 +08:00

要是问我红黑树可咋整啊

19

crossoverJie

OP

2018-07-23 16:29:37 +08:00

@llxx510200 #18 这个我觉得能讲清楚为啥快，啥时候翻转这些就差不多了。具体实现确实很复杂

20

liuzhen

2018-07-23 17:10:10 +08:00

楼主博客可以转载到 oschina 吗？会备注原地址

21

beny2mor

2018-07-23 17:14:02 +08:00

mark 一下

22

crossoverJie

OP

2018-07-23 17:52:12 +08:00

@liuzhen #20 可以的。

23

Antidictator

2018-07-23 18:27:39 +08:00 via iPhone

支持一下

24

LuckCode

2018-07-23 18:34:19 +08:00 via iPhone

我去，从博客看到公众号，今天在 v 站看到了作者。
缘分啊，py 交易一下。

25

WildCat

2018-07-23 18:35:11 +08:00

1

支持。最近用 pandoc 把你的 repo 转换成了 epub 在手机上看，受益良多

26

crossoverJie

OP

2018-07-23 18:42:07 +08:00

@LuckCode #24 哈哈我这是广撒网啊你也是哪个网都钻进来了

27

crossoverJie

OP

2018-07-23 18:43:32 +08:00

@WildCat #25 👍 咋搞的呀，可以提个 Issue。

https://github.com/crossoverJie/Java-Interview/issues/new

28

zxq1002

2018-07-23 19:59:31 +08:00 via Android

打开好慢。。

29

WildCat

2018-07-23 20:03:49 +08:00

@crossoverJie 我目前转换的有问题，不过我先开个 issue 抛砖引玉吧

30

crossoverJie

OP

2018-07-23 20:06:55 +08:00

@zxq1002 #28 确实挺慢的，准备转到国内了。

31

shiguiyou

2018-07-24 08:35:47 +08:00

打不开。。。

32

crossoverJie

OP

2018-07-24 10:19:56 +08:00

@shiguiyou #31 多等等卡。。

33

mrrobot97

2018-07-24 10:23:36 +08:00

safari 禁用了 Flash 打开网页后风扇开始怒吼..

34

zpxshl

2018-07-24 12:31:03 +08:00 via Android

我来提（请教）个问题。
1.8 版 concurrentHM，当使用 cas 插入，如何保证结果对其他线程可见。 volatile 不保证数组元素的可见性。

35

crossoverJie

OP

2018-07-24 13:11:58 +08:00

@zpxshl #34

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

tabAt() 方法，它所依赖的是 Unsafe 包中的 getObjectVolatile() 可以保证可见性。

36

zpxshl

2018-07-25 07:55:45 +08:00 via Android

@crossoverJie
#35 getObjectVolatile （）只能保证自己读到的是最新值。
putObjectVolatile 才能保证将值写回主内存。

37

crossoverJie

OP

2018-07-25 09:05:00 +08:00

@zpxshl #36 嗯你不是问的怎么保证可见性嘛，获取到的是最新值就不会有可见性的问题了。

38

zpxshl

2018-07-25 10:04:12 +08:00 via Android

@crossoverJie 可见性...... 是一个变量修改其他线程都可以见到。你获取到最新值，（为空时） cas 插入。此时数组元素被修改，如何保证其他线程见到你的修改？

39

crossoverJie

OP

2018-07-25 10:28:51 +08:00

@zpxshl #38 如何保证其他线程见到你的修改？

其他线程在 tabAt()

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

get 的时候也是一样的：

40

zpxshl

2018-07-25 12:27:44 +08:00 via Android

@crossoverJie 朋友。getObjectVolatile 只是获得主内存的数据。并没有强制将其他线程的工作内存数据刷新回主内存的功能。也就是说当你 cas 修改数组数据后，如果没有将数据缓存刷回主内存。其他线程用 getObjectVolatile 也读不到最新的值。

41

crossoverJie

OP

2018-07-25 13:09:23 +08:00

@zpxshl #40 兄弟，我觉得这没有啥问题呀。

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

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

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

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

如果当前位置依然为空的话就会重复上面的步骤。

42

zpxshl

2018-07-26 22:59:33 +08:00 via Android

@crossoverJie
a 线程，遍历数组的时候在 key 所映射的那个位置是空的，cas 插入成功。
b 线程，同样找到那个位置发现同样为空（ cas 插入的数值对 b 线程不一定可见的），又 cas 插入，那不就出问题啦？

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

44

zpxshl

2018-07-27 15:37:01 +08:00

@crossoverJie 感谢！

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)```

为什么？这么改动？有什么区别吗？