8

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

在 Java 中，如果两个线程同时发现现在 HashMap 需要调整大小并且它们都尝试调整大小。在Java中调整HashMap大小的过程中，存储在链表中的bucket中的元素在迁移到新bucket期间会按顺序颠倒，因为java HashMap不会将新元素附加到尾部，而是将新元素附加到头部避免尾部遍历。如果发生竞态条件，那么您将最终陷入无限循环

阅读本文后，我有两个问题：

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

请帮我澄清一下，非常感谢！

4

3 回答 3

9

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

“因为java HashMap不会在尾部追加新元素，而是在头部追加新元素以避免尾部遍历”

如果 HashMap 以插入顺序存储它们，它必须在每次插入时遍历列表或存储一个指向列表末尾的额外指针（并维护它）。无论如何，按插入顺序将元素存储在桶中不会带来任何好处（至少我想不出任何好处）。

您的第二个问题的答案取决于这里：

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

于 2013-04-12T17:43:58.180 回答
3

实际上至少有一个与rehashing相关的竞争条件。看看这个代码片段（它来自 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。不起作用。要么是因为这个，要么是因为其他的原因。以上只是你不应该试图违背合同的一个例子。

于 2013-04-12T14:37:51.477 回答
1

我不知道这个例子是否有效。很明显，它是特定于实现的。我认为它也错过了更大的图景。

HashMap的合同明确状态（强调他们的）：

如果多个线程同时访问一个哈希映射，并且至少有一个线程在结构上修改了映射，则必须在外部进行同步。（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）

如果您违反合同，所有赌注都将取消。地图可以以任意、未指定的方式随意炸毁。

于 2013-04-12T14:37:02.960 回答