6

私は本当に不気味な TreeMap の動作を経験しており、小さなテスト ケースを絞り込むのに苦労しました。

実行時に提供されるファイルから、多数のキーと値のペアを Map に読み込みたいと考えています。カスタムキークラスを使用しています。後でエントリーを取り戻そうとすると、1 つ以上のエントリーが欠落していることに気付きます。デバッガーといくつかのテスト ケースを使用して、欠落しているエントリが読み取りフェーズ中に確実に消えていることを確認しましたが、何が原因かはわかりません。

基本的：

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) から 1 つまたは 2 つの任意のキーを削除すると、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

TreeMap は、比較したときに結果が 0 の場合、2 つのエントリが等しいと見なします。これは、たとえ !key1.equals(keyN). したがって、これらの 2 つのキーは等しくないため、一方を挿入しても他方が上書きされるべきではないと考えるかもしれませんがTreeMap、equals 関数と比較関数が互いに矛盾している場合は、別の考えになります。

この動作は、マップ内の要素の数によって異なる場合があることに注意してください。これは、compare メソッドで 0 と評価される 2 つの要素を実際に比較することに依存するためです。

TreeMap javadocsから:

...map は、compareTo (または compare) メソッドを使用してすべてのキー比較を実行するため、このメソッドによって等しいと見なされる 2 つのキーは、並べ替えられたマップの観点からは等しい...

およびComparable javadocs から(@Brian に感謝):

自然な順序付けが equals と一致することを強くお勧めします (必須ではありません)。これは、明示的な比較子のないソートされたセット (およびソートされたマップ) が、自然な順序付けが 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 に答える