TreeMap迭代器行为在删除时不一致

今天，当绑定发现一个bug时，我发现TreeMap迭代器行为在删除对象时有点奇怪。事实上已经我测试不同的用途，在一个简单的例子：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()); 
     } 
    }

然后，对于关键= 4结果为5，而对于key = 5，结果为5，因为链接在移除时被更改。但为什么行为不同。 JIT？即使这是答案，他们是不是应该统一？

来源

2011-09-20 PedroG

您提供的代码将永远不会打印任何内容，因为没有条目具有“X”键。请显示一个简短的*完整的*程序来说明问题。 –

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

@home：很可能 - 但如果OP只给了我们一个完整的程序准备编译并运行，将会更容易重现... –

要回答这个问题，为什么出现这种情况，意见给出了一个暗示

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

AFAIK，这是保持平衡的树的一部分。

这是什么意思，如果你只有一个子节点（或没有），节点本身被删除。如果该节点有两个子节点，则该节点将替换为其后继节点。

如果您始终从开始删除，该节点将被丢弃，您仍然可以使用该节点，但不会被修改。如果从树的中间删除正确的节点，则修改该条目以平衡树，因此在删除后使用条目查看修改的条目。

来源

2011-09-20 20:18:40

见Map.Entry的Javadoc getValue()：

返回与此项对应的值。如果映射已从支持映射中删除（通过迭代器的删除操作），则此调用的结果是未定义的。

一旦你删除了条目，行为是不确定的，因此这可能解释你为什么会得到不同的结果。

注意：另一位用户aix发布了类似的答案，我将对此发表评论，但由于某种原因它被删除/删除。

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

编辑2：感谢埃德的Staub此：我觉得总体思路仍持有，因为Javadoc文档Map.Entry状态：

...更正式，地图项的行为是不确定的，如果在迭代器返回条目之后，除了通过映射条目上的setValue操作之外，支持映射已被修改。

来源

2011-09-20 16:42:34 Peter

但代码调用getKey（）不是getValue（），和getKey（）文档没有说同样的事情 – Bhaskar

一个小问题：佩德罗正在使用getKey（），而不是getValue（），而getKey（）的方法javadocs没有相同的警告。不过，我认为你是对的，特别是Map.Entry类doc更一般地说：'...如果在迭代器返回条目后修改了支持映射，则映射条目的行为是未定义的，除非通过映射上的setValue操作条目。 ' –

@Bhaskar @EdStaub感谢您的信息。埃德，我认为你是对的。一般情况下，如果支持地图已被修改，则可能不会依赖Map.Entry对象。 – Peter

我个人不会称这是一种“奇怪”的行为。这可能不是你所期望的。

TreeMap内部实现了red-black tree。删除节点时，树会重新平衡（请参阅TreeMap.deleteEntry(Entry<K,V> p)），并且有几种情况如何完成这种重新布局，这些重新布局取决于当前树和分别取决于哪个节点。

来源

2011-09-20 19:49:47 jeha

具有完美意义，但getValue（）方法的Map.Entry Javadoc为什么说结果是未定义的？难道它不应该说结果取决于实施吗？ – PedroG

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

TreeMap迭代器行为在删除时不一致

回答

相关问题