TreeMap put（）默默刪除其他條目？

我經歷了一些非常恐怖的TreeMap行爲，並且在縮小測試用例方面遇到了一些麻煩，請耐心等待。TreeMap put（）默默刪除其他條目？

我想從運行時提供的文件中將大量的鍵值對讀入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時，鍵下一行
不幸的是，當keyN踢出key1時，map的大小是而不是，因爲keyQ踢出key1時它的大小與map的大小相同，所以它是probab不是有限大小的問題
如果我使用HashMap代替，key1仍然在地圖中
自定義密鑰類MyKey對Comparable，equals和hashCode使用相同的邏輯。

我最初使用的是TreeMap，因爲我期望使用大型數據集，並且TreeMap有更高的內存效率。 HashMap將會是一個很好的選擇，但看到TreeMap的行爲方式仍然令人震驚 - 任何人都會對這裏發生的事情有所想法？

來源

2013-01-31 krivard

同意Steve Kuo。註釋掉你的compareTo/equals/hashCode實現並再次運行你的測試，看看你是否遇到同樣的問題。 – digitaljoel

如果比較結果爲0，TreeMap認爲兩個條目相等。因此，如果key1和keyN'與'0比較，那麼key1將被keyN覆蓋（）。這是真的即使!key1.equals(keyN)。因此，儘管您可能認爲這兩個鍵不相等，因此插入一個不應覆蓋另一個，如果您的等同函數和比較函數彼此不一致，那麼TreeMap會認爲不同。

請注意，此行爲可能因地圖中元素的數量而異，因爲它取決於實際比較比較方法評估結果爲0的兩個元素。基本上，事情將按照您所說的「幽靈般」行事。

從TreeMap javadocs：

...地圖使用其的compareTo執行所有關鍵比（或比較）方法，所以被認爲等於通過該方法兩個密鑰，從所述觀點出發有序映射，相等...

並從Comparable javadocs （謝謝@Brian）：

強烈建議（儘管不要求）自然排序與等於一致。這是因爲排序集（和排序的地圖）沒有明確的比較行爲「奇怪」，當它們與自然排序是與等號不一致的元素（或鍵）使用。特別是，這樣的排序集合（或排序後的映射）違反了集合（或映射）的一般合同，該集合根據等號方法定義爲。

來源

2013-01-31 17:20:11 sharakan

+1這就是'compareTo'一致性子句在javadocs中的原因：「強烈建議（儘管不要求）自然排序與equals一致。這是因爲沒有顯式比較器的排序集（和排序映射）表現得很好當它們與自然順序與平等不一致的元素（或鍵）一起使用時，「奇怪」。（['Comparable']（http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html）） – Brian

@Brian謝謝你的引用，我將它添加到答案中。 – sharakan

是的，就是這樣 - 我錯過的是，實際的keyTo（）調用並不一定會發生在新鍵上，而是作爲樹重新平衡的一部分。謝謝！ – krivard

您確定keyN在任何情況下都不覆蓋key1嗎？因爲在我看來，那是你的幻想案例。

來源

2013-01-31 17:18:55

告訴我們MyKey的編碼。我的猜測是您的compareTo方法有問題。更具體地說，您的compareTo與equals不一致。

來源

2013-01-31 17:19:48

TreeMap put（）默默刪除其他條目？

回答

相關問題