TreeMap put()会默默删除其他条目吗？

Question

我经历了一些非常怪异的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)中删除了大范围的键,则key1在添加keyN时保持不变,但是当添加keyQ时会掉出来,在行下面还有~300个键
• 不幸的是,当keyN踢出key1的地图的大小是不一样的地图的大小时keyQ踢出key1的,所以它可能不是一个有限的尺寸问题
• 如果我使用HashMap,则key1仍保留在地图中
• 自定义键类MyKey对Comparable,equals和hashCode使用相同的逻辑.

我最初使用TreeMap是因为我希望使用大型数据集,而TreeMap的内存效率更高一些.HashMap将是一个很好的选择,但看到TreeMap以这种方式表现仍然令人震惊 - 任何人都对这里发生的事情有所了解？

Answer 1

如果比较时,TreeMap认为两个条目相等,则结果为0.因此,如果key1和keyN'与'0'比较,则key1将被putN()覆盖.即使 这样也是如此!key1.equals(keyN).因此,虽然您可能认为这两个键不相等,因此插入一个不应该覆盖另一个,TreeMap如果您的equals和比较函数彼此不一致,则会认为不同.

请注意,这种行为可能会因地图中元素的数量而有所不同,因为它取决于实际比较两个比较方法评估为0的元素.基本上,事情会像你说的那样"诡异".

来自TreeMap的javadocs:

... map使用compareTo(或compare)方法执行所有键比较,因此从排序映射的角度来看,通过此方法认为相等的两个键相等...

并从可比较的javadocs(感谢@Brian):

强烈建议(尽管不要求)自然排序与equals一致.这是因为没有显式比较器的有序集(和有序映射)在与自然顺序与equals不一致的元素(或键)一起使用时表现得"奇怪".特别是,这样的有序集(或有序映射)违反了集合(或映射)的一般契约,它是根据等于方法定义的.