TreeSet internamente usa TreeMap, entonces ¿es necesario implementar el método Hashcode cuando usa Treeset

Question

Me gustaría saber qué significa cuando javadocs para TreeSet dice 'Esta clase implementa la interfaz Set, respaldada por una instancia de TreeMap'? En el ejemplo siguiente, no he implementado el método Hashcode y todavía está funcionando según las expectativas, es decir, puede ordenar los objetos. Tenga en cuenta que no he implementado intencionalmente la implementación Equals consistente para verificar el comportamiento de 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); 
} 

} 

Este ejemplo imprime [Tom Ben, Tom jon, Tom Wik] .Así es la clasificación basada en el método compareTo y hashCode() método se parece insignificante en este scenario.However, TreeSet está respaldado por TreeMap, tan internamente si se usa TreeMap para clasificar, ¿cómo se compara el objeto con TreeMap?

Answer 1

Su ComparisonObject está utilizando el método hashCode definido en Object. Intente agregar una cantidad diferente de ComparisonLogic, con los mismos valores para ambos campos, y vea qué sucede.

Answer 2

Creo que estás planteando dos preguntas.

1, ¿Por qué está funcionando su código?

Como Avi escribió en this tema:

Cuando no se sobreescribe el método hashCode(), su clase hereda el hashCode() por defecto método del objeto, lo que da a cada objeto un código hash distinto . Esto significa que t1 y t2 tienen dos códigos hash diferentes, aunque si los comparas, serían iguales. Dependiendo de la implementación particular de hashmap, el mapa es gratis para almacenarlos por separado.

Esto significa que no tiene que almacenarlos por separado, pero podría ser. Prueba este código:

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"))); 

La salida para mí fue la siguiente:

true 
true 
true 
false 
false 
false 
false 
false 
false 

Eso significa que algunas de ellas estaban allí algunas de ellas no.

2, ¿Qué significa cuando javadocs para Treeset dice 'Esta clase implementa la interfaz Set, respaldada por una instancia de TreeMap'?

Esto significa que la clase TreeSet en Java 1.7 tiene el siguiente aspecto:

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. 

Esto significa que hay un mapa debajo de la clase TreeSet y hay una gran cantidad de métodos que sólo se delega a ella .

Espero haber podido ayudar.

Answer 3

TreeSet internamente utiliza TreeMap objeto 'm' para almacenar objetos como par clave-valor que implica que la llamada

set.add(x); 

llama internamente método put de TreeMap:

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

método Ahora ponga internamente las llamadas se comparan si se proporciona Comparator o en su caso utiliza el método "compareTo" de la clase ComparisonLogic.

Nunca utiliza iguales o hashcode explícitamente en su lugar usa compareTo (Object o1) (proporcionado al implementar Comparable) o compara (Object o1, objeto o2) (proporcionado al implementar Comparador) método para determinar la presencia de Object en el conjunto.

así que para responder a su pregunta no es necesario implementar el método hashcode() a menos que lo esté utilizando en su implementación de método de comparación (compare o compare).

Answer 4

Es cierto que TreeSet usa internamente TreeMap. TreeMap no necesita tener hashCode e iguala el método implementado para los objetos clave. TreeMap usa internamente el árbol Rojo-Negro, que es un árbol de búsqueda binaria autoequilibrante. El orden en este árbol se mantiene utilizando el método compareTo (el objeto clave implementa la interfaz Comparable) o el método de comparación (el comparador provisto se define al construir TreeMap, en este caso para TreeSet en realidad). Espero que se aclare.