TreeSet utilizza internamente TreeMap, quindi è necessario implementare il metodo Hashcode quando si utilizza Treeset

Question

Vorrei sapere cosa significa quando javadocs per TreeSet dice "Questa classe implementa l'interfaccia Set, supportata da un'istanza TreeMap"? Nell'esempio seguente, non ho implementato il metodo Hashcode e ancora funziona come da aspettativa, è in grado di ordinare gli oggetti. Si noti che non ho implementato intenzionalmente l'implementazione Equals coerente per verificare il comportamento TreeSet.

import java.util.TreeSet; 


public class ComparisonLogic implements Comparable<ComparisonLogic>{ 

String field1; 
String field2; 

public String toString(){ 
    return field1+" "+field2; 
} 

ComparisonLogic(String field1,String field2){ 
    this.field1= field1; 
    this.field2= field2; 

} 
public boolean equal(Object arg0){ 
    ComparisonLogic obj = (ComparisonLogic) arg0; 

    if(this.field1.equals(obj.field1)) 
     return true; 
    else 
     return false; 
} 

public int compareTo(ComparisonLogic arg0){ 
    ComparisonLogic obj = (ComparisonLogic) arg0; 
    return this.field2.compareToIgnoreCase(obj.field2); 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    ComparisonLogic x = new ComparisonLogic("Tom", "jon"); 
    ComparisonLogic y = new ComparisonLogic("Tom", "Ben"); 
    ComparisonLogic z = new ComparisonLogic("Tom", "Wik"); 

    TreeSet<ComparisonLogic> set = new TreeSet<ComparisonLogic>(); 
    set.add(x); 
    set.add(y); 
    set.add(z); 
    System.out.println(set); 
} 

} 

questo esempio stampe [Tom Ben, Tom jon, Tom Wik] .Così si ordinamento basa sul metodo compareTo e hashCode() metodo sembra insignificante in questo scenario.However, TreeSet è sostenuta da TreeMap, così internamente se TreeMap è usato per l'ordinamento, in che modo treeMap esegue l'hashing dell'oggetto?

Answer 1

Il ComparisonObject utilizza il metodo hashCode definito su Object. Prova ad aggiungere un numero diverso di ComparisonLogic, con gli stessi valori per entrambi i campi, e guarda cosa succede.

Answer 2

Penso che tu stia ponendo due domande.

1, perché il codice funziona?

Come Avi scrisse this argomento:

Quando non l'override del metodo hashCode(), la classe eredita il hashCode di default() il metodo da Object, che dà ogni oggetto un codice hash distinta . Ciò significa che t1 e t2 hanno due codici hash diversi, anche se dovessi confrontarli, sarebbero uguali. A seconda della particolare implementazione di hashmap, la mappa è gratis per archiviarli separatamente.

Ciò significa che non è necessario memorizzarli separatamente, ma potrebbe. Prova di questo codice:

TreeSet<ComparisonLogic> set = new TreeSet<ComparisonLogic>(); 
    set.add(new ComparisonLogic("A", "A")); 
    set.add(new ComparisonLogic("A", "B")); 
    set.add(new ComparisonLogic("A", "C")); 
    set.add(new ComparisonLogic("B", "A")); 
    set.add(new ComparisonLogic("B", "B")); 
    set.add(new ComparisonLogic("B", "C")); 
    set.add(new ComparisonLogic("C", "A")); 
    set.add(new ComparisonLogic("C", "B")); 
    set.add(new ComparisonLogic("C", "C")); 
    set.add(new ComparisonLogic("A", "A")); 

    System.out.println(set.remove(new ComparisonLogic("A", "A"))); 
    System.out.println(set.remove(new ComparisonLogic("A", "B"))); 
    System.out.println(set.remove(new ComparisonLogic("A", "C"))); 
    System.out.println(set.remove(new ComparisonLogic("B", "A"))); 
    System.out.println(set.remove(new ComparisonLogic("B", "B"))); 
    System.out.println(set.remove(new ComparisonLogic("B", "C"))); 
    System.out.println(set.remove(new ComparisonLogic("C", "A"))); 
    System.out.println(set.remove(new ComparisonLogic("C", "B"))); 
    System.out.println(set.remove(new ComparisonLogic("C", "C"))); 

L'uscita per me è stata la seguente:

true 
true 
true 
false 
false 
false 
false 
false 
false 

Questo significa che alcuni di loro erano lì alcuni di loro non.

2, Che cosa significa quando javadocs per Treeset dice "Questa classe implementa l'interfaccia Set, supportata da un'istanza TreeMap"?

significa che la classe TreeSet in Java 1.7 è simile al seguente:

public class TreeSet<E> extends AbstractSet<E> 
implements NavigableSet<E>, Cloneable, java.io.Serializable 
{ 
/** 
* The backing map. 
*/ 
private transient NavigableMap<E,Object> m; 

TreeSet(NavigableMap<E,Object> m) { 
    this.m = m; 
} 

... (lots of other code)  

public boolean contains(Object o) { 
    return m.containsKey(o); 
} 

etc. 

Ciò significa che v'è una mappa sotto la classe TreeSet e c'è un sacco di metodi che è delegata solo ad essa .

Spero di poter aiutare.

Answer 3

TreeSet utilizza internamente TreeMap oggetto 'm' per oggetti archivio come coppia di valori-chiave che implica che la chiamata

set.add(x); 

internamente chiama metodo put di TreeMap:

public boolean add(E e) { 
    return m.put(e, PRESENT)==null; 
} 

metodo Ora mettere internamente chiama o confronta se viene fornito Comparator o nel tuo caso utilizza il metodo "compareTo" della classe ComparisonLogic.

Non usa mai hashcode o hash esplicitamente utilizza invece compare (oggetto o1) (fornito durante l'implementazione di Comparable) o compare (oggetto o1, oggetto o2) (fornito durante l'implementazione di Comparator) per determinare la presenza di Object nell'insieme.

quindi per rispondere alla domanda non è necessario implementare il metodo hashcode() a meno che non lo si utilizzi nell'implementazione del metodo di confronto (confronto o confronto).

Answer 4

È vero che TreeSet utilizza internamente TreeMap. TreeMap non ha bisogno di avere il metodo hashCode e Equals implementato per gli oggetti chiave. TreeMap utilizza internamente l'albero rosso-nero che è un albero di ricerca binaria autobilanciata. L'ordine in questo albero viene mantenuto utilizzando il metodo compareTo (l'interfaccia chiave implementa l'interfaccia comparabile) o il metodo di confronto (il comparatore fornito viene definito durante la costruzione di TreeMap, in questo caso per TreeSet in realtà). Spero che si cancella.