6

我经历了一些非常诡异的 TreeMap 行为，并且在缩小一个小测试用例时遇到了一些麻烦，所以请耐心等待。

我想从运行时提供的文件中将大量键值对读入 Map。我正在使用自定义键类。后来，当我去拉回条目时，我发现其中一个或多个丢失了。使用调试器和一些测试用例，我确定丢失的条目在读取阶段肯定会消失，但我不确定是什么原因造成的。

基本上：

Map<MyKey,Double> map = new TreeMap<MyKey,Double>();
map.put(key1,value1);

// ... put another ~500 entries into the map ...

assertTrue(map.containsKey(key1)); // passes
if (!map.containsKey(keyN)) { 
    map.put(keyN, valueN); // this code executes
}
assertTrue(map.containsKey(key1)); // FAILS

...因此，从本质上讲，向地图添加一个全新的键会导致一个不相关的条目从其中脱落。

  • 如果我只添加 key1 和 keyN，key1 会保留在地图中——中间的 500 个条目在某种程度上很重要
  • 如果我从 2..(N-1) 中删除一个或两个任意键，则在添加 keyN 时仍会启动 key1
  • 如果我从 2..(N-1) 中删除大量键，则在添加 keyN 时 key1 仍然存在，但在添加（比如说）keyQ 时会消失，大约 300 个键进一步向下
  • 不幸的是，keyN 踢出 key1 时的地图大小与 keyQ 踢出 key1时的地图大小不同，所以这可能不是一个有限大小的问题
  • 如果我改用 HashMap，key1 会保留在地图中
  • 自定义键类 MyKey 对 Comparable、equals 和 hashCode 使用相同的逻辑。

我最初使用 TreeMap 是因为我希望使用大型数据集，而 TreeMap 的内存效率更高一些。HashMap 将是一个不错的选择，但是看到 TreeMap 以这种方式运行仍然令人担忧——有人对这里发生的事情有想法吗？

4

3 回答 3

12

如果比较时结果为 0，TreeMap 认为两个条目相等。因此，如果 key1 和 keyN“比较”为 0，则 key1 将被 put() 中的 keyN 覆盖。这是真的，即使 !key1.equals(keyN)。因此，虽然您可能认为这两个键不相等，因此插入一个不应覆盖另一个，但TreeMap如果您的相等和比较函数彼此不一致，则会认为不同。

请注意，此行为可能会根据地图中元素的数量而有所不同，因为它取决于实际比较两个元素，而比较方法的计算结果为 0。基本上，正如您所说，事情会表现得“诡异”。

从TreeMap javadocs：

...map 使用其 compareTo（或 compare）方法执行所有键比较，因此从排序映射的角度来看，此方法认为相等的两个键是相等的...

并来自Comparable javadocs（感谢@Brian）：

强烈建议（尽管不是必需的）自然排序与 equals 一致。之所以如此，是因为没有显式比较器的排序集（和排序映射）在与自然顺序与等于不一致的元素（或键）一起使用时表现“奇怪”。特别是，这样的排序集合（或排序映射）违反了集合（或映射）的一般合同，该合同是根据 equals 方法定义的。

于 2013-01-31T17:20:11.230 回答
1

向我们展示MyKey. 我的猜测是你的compareTo方法有问题。更具体地说，您compareTo与equals.

于 2013-01-31T17:19:48.390 回答
0

您确定 keyN 在任何情况下都不会覆盖 key1 吗？因为在我看来那是你的幻影案例。

于 2013-01-31T17:18:55.083 回答