TreeMap 迭代器的行为在移除元素时不一致

Question

今天在试图发现 bug 时，我发现 TreeMap 迭代器在删除对象时的行为有些奇怪。实际上，在测试不同用法时，我发现了一个简单的例子：

    TreeMap<String, String> map = new TreeMap<String, String>();
    map.put("1", "1");
    map.put("2", "2");
    map.put("3", "3");
    map.put("4", "4");
    map.put("5", "5");

    Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();

     while (iterator.hasNext()) {
        Map.Entry<String, String> entry = iterator.next();
        System.out.println("Before "+entry.getKey());
        iterator.remove();
        System.out.println("After " +entry.getKey());
    }

结果如下：

Before 1
After 1 
Before 2
After 2
Before 3
After 3
Before 4
After 4
Before 5
After 5

但是如果我将它改成：

    TreeMap<String, String> map = new TreeMap<String, String>();
    map.put("1", "1");
    map.put("2", "2");
    map.put("3", "3");
    map.put("4", "4");
    map.put("5", "5");

    Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();

            String key = "4";

    while (iterator.hasNext()) {
        Map.Entry<String, String> entry = iterator.next();
        if(entry.getKey().equals(key)){
            iterator.remove();
            System.out.println(entry.getKey());
        }
    }

当 key = 4 时，由于链接被删除而导致结果为 5；当 key = 5 时，其结果也为 5。但是为什么行为会不同呢？是JIT的缘故吗？即使是这个原因，它们也应该是一致的吧。

- PedroG

---

你提供的代码永远不会打印任何内容，因为没有一个条目有“X”键。请展示一个简短但完整的程序来演示这个问题。 - Jon Skeet

@Jon Skeet：我猜X是3或4的占位符？ - home

@home：很有可能 - 但如果原帖作者提供一个完整的可编译和运行的程序，那么复现将会更加容易。 - Jon Skeet

@Jon Skeet：没有问题，我同意。 - home

对于 X=2，结果是3？这很令人惊讶！我认为应该是2，就像 X=4 时一样是4。 - Bhaskar

@Jon Skeet：希望现在好多了。对于不断的更改，我很抱歉，但我一直在尝试复制确切的问题，例如如果键=“3”，那么它会打印“3”。 - PedroG

Answer 1

请参阅Map.Entry的Javadoc，了解getValue()的含义：

返回与此条目对应的值。如果映射已从支持映射中删除（通过迭代器的remove操作），则此调用的结果未定义。因此，一旦删除条目，行为就变得不确定，这可能解释了为什么您会得到不同的结果。

注意：另一个用户aix发布了类似的答案，我本来想对它进行评论，但由于某些原因被删除/移除了。

编辑：我不确定这个答案是否正确，因为我刚刚注意到OP正在调用 getKey（）而不是 getValue（）。

编辑2：感谢Ed Staub提供的信息：我认为总体思路仍然成立，因为 Map.Entry 的Javadoc声明如下：更正式地说，如果在迭代器返回条目后修改了支持映射，除非通过map entry上的setValue操作，否则会导致地图条目的行为不确定。

- Peter

---

但是代码调用的是getKey()而不是getValue()，而且getKey()的文档并没有说同样的事情。 - Bhaskar

一个小问题：Pedro正在使用getKey()而不是getValue()，并且getKey()的方法javadocs没有相同的警告。然而，我认为你是对的；特别是，Map.Entry类文档更一般地说：“……如果在迭代器返回条目之后修改了支持映射，除非通过映射条目上的setValue操作，否则映射条目的行为是未定义的。” - Ed Staub

@Bhaskar @EdStaub 感谢提供的信息。Ed，我认为你是对的。一般来说，如果后台映射已被修改，则可能无法依赖Map.Entry对象。 - Peter

Answer 2

回答为什么会发生这种情况，评论给出了一个提示。

// If strictly internal, copy successor's element to p and then make p
// point to successor.

据我所知，这是保持树的平衡的一部分。

这意味着如果你只有一个子节点（或没有子节点），那么该节点本身将被移除。如果该节点有两个子节点，则该节点将被其后继节点替代。

如果您总是从开头删除，那么该节点被丢弃，但仍可使用，不过不会被修改。如果您从树的中间删除右侧节点，则修改条目以平衡树，因此在删除后使用条目请注意修改过的条目。

- Peter Lawrey

Answer 3

个人而言，我不认为这是一个“奇怪”的行为。它可能只是不符合您的预期。

TreeMap 内部实现了一个 红黑树。在删除节点时，树会进行平衡处理（请参见 TreeMap.deleteEntry(Entry<K,V> p)），并且有几种情况会影响到平衡处理的方式，具体取决于当前树以及要移除的节点。

- jeha

---

这很有道理，但为什么Map.Entry Javadoc中的getValue()方法说结果是未定义的？它不应该说结果取决于实现吗？ - PedroG

通过声明结果为undefined，API不会对实现它的人施加特定的行为。所以对我来说，它只是取决于实现的同义词。 - jeha