在调整大小时,多线程环境中的Hashmap

Question

我正在学习一个教程,它基本上解释了在多线程环境中调整Hashmap大小时发生的竞争条件的原因:

在Java中,如果两个线程同时发现现在HashMap需要调整大小并且它们都尝试调整大小.在Java中的HashMap的调整过程中,存储在链表斗元素迁移到新的水桶中得到逆转,从而因为Java的HashMap不附加在尾部的新元素,而不是它在头部添加新元素避免尾部穿越.如果发生竞争条件,那么最终会出现无限循环

阅读本文后我有两个问题:

1. 为什么每个存储桶的链表按顺序颠倒？
2. 我可以看到可能存在竞争条件,但无法看到无限循环是如何产生的？是因为一个线程可能会将元素头部追尾,而另一个线程以相反的顺序执行它？

请帮我澄清一下,非常感谢!

Answer 1

第一个问题的答案在引用文本中:

"因为java HashMap不会在尾部附加新元素,而是在头部附加新元素以避免尾部遍历"

如果HashMap以插入顺序存储它们,则必须在每次插入时遍历列表,或者存储指向列表末尾的额外指针(并保持它).无论如何以插入顺序将元素存储在桶中都不会带来任何好处(至少我想不出任何好处).

你的第二个问题的答案依赖于此:

http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html

Answer 2

实际上，至少存在一种与重新哈希相关的竞争条件。看一下这段代码片段（来自Sun JDK7）：

boolean oldAltHashing = this.useAltHashing;
this.useAltHashing |= sun.misc.VM.isBooted() && (this.newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ this.useAltHashing;
transfer(newTable, rehash);
this.table = newTable;

这里线程 T1 可能以 结束rehash = true，线程 T2 可能以 结束rehash = false（假设 T1 已经更改了 的值this.useAltHashing）。

现在，猜测哪个线程将写入this.table- 你也不知道，也可以。所以，是否获得一致的内部状态是一个运气问题。

无论如何，正如我在设计评论中提到的，不应该在多线程环境中使用 HashMap。不起作用。要么是因为这个，要么是因为其他原因。上述只是您不应试图违反合同的一个例子。