TreeMap put() cancella silenziosamente altre voci?

Question

Ho sperimentato un comportamento TreeMap davvero spettrale e ho avuto qualche problema a restringere un piccolo caso di test, quindi portami con me.

Voglio leggere un gran numero di coppie chiave-valore in una mappa, da un file fornito in fase di esecuzione. Sto usando una classe di chiavi personalizzata. Più tardi, quando vado a ritirare le voci, trovo che uno o più di essi manchino. Usando un debugger e alcuni casi di test, ho determinato che la voce mancante (i) sta scomparendo definitivamente durante la fase di lettura, ma non sono sicuro di cosa lo stia causando.

In sostanza:

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 

... Quindi, in sostanza, l'aggiunta di una nuova chiave per la mappa provoca una voce non correlato a cadere fuori di esso.

• Se ho appena aggiungo key1 e Keyn solo, chiave1 rimane nella mappa - i successivi 500 voci sono in qualche modo importanti
• Se rimuovo uno o due tasti arbitrarie da 2 .. (N-1), key1 è ancora avviato quando keyN è aggiunto
• Se rimuovo un ampio intervallo di chiavi da 2 .. (N-1), la chiave1 rimane quando keyN viene aggiunto, ma cade quando (say) viene aggiunto keyQ, ~ 300 chiavi più in basso sulla linea
• Sfortunatamente la dimensione della mappa quando keyN kick out key1 è non uguale alla dimensione della mappa quando keyQ kicking key1, quindi è probab non è un problema di dimensioni limitate
• Se utilizzo una HashMap, la chiave 1 rimane nella mappa
• Classe chiave personalizzata MyKey utilizza la stessa logica per Comparable, equals e hashCode.

Inizialmente utilizzavo TreeMap perché prevedo di utilizzare set di dati di grandi dimensioni e TreeMap è un po 'più efficiente in termini di memoria. HashMap sarà un'alternativa eccellente, ma è ancora allarmante vedere TreeMap comportarsi in questo modo - qualcuno ha pensieri su cosa sta succedendo qui?

Answer 1

TreeMap pensa che due voci siano uguali se, confrontato, il risultato è 0. Quindi se key1 e keyN 'confrontano a' 0, quindi key1 verrà sovrascritto da keyN che viene messo(). Questo è vero anche se!key1.equals(keyN). Quindi, sebbene tu possa pensare che quelle due chiavi non siano uguali, e quindi l'inserimento di una non dovrebbe sovrascrivere l'altra, lo TreeMap la penserà diversamente se le tue equazioni e le funzioni di confronto sono incoerenti tra loro.

Si noti che questo comportamento può variare in base al numero di elementi nella mappa, perché dipende dal confronto effettivo tra due elementi che il metodo di paragone valuta a 0. Fondamentalmente, le cose agiranno, come dici tu, "spettrali".

Dal TreeMap javadocs:

...mappa esegue tutte confronti chiave utilizzando il suo compareTo (o confrontare) metodo, quindi due chiavi che sono ritenuti uguali con tale metodo, dal punto di vista mappa ordinato, pari ...

e dalla Comparable javadocs (grazie @ Brian):

si raccomanda vivamente (anche se non richiesto) che naturali ordinamenti essere coerenti con eguali. Questo perché i set ordinati (e le mappe ordinate) senza comparatori espliciti si comportano "stranamente" quando vengono utilizzati con elementi (o chiavi) il cui ordinamento naturale è incoerente con gli uguali. In particolare, tale insieme ordinato (o ordinato mappa) viola il contratto generale per set (o mappa), che è definito in termini di metodo equals.

Answer 2

Sei sicuro che keyN non stia sovrascrivendo la chiave 1 in nessuno scenario? Perché mi sembra che sia il tuo caso fantasma.

Answer 3

Mostraci il codice per MyKey. La mia ipotesi è che ci sia qualcosa di sbagliato nel tuo metodo compareTo. Più specificamente, il tuo compareTo non è coerente con equals.