TreeSet wewnętrznie używa TreeMap, więc czy jest wymagane wdrożenie metody Hashcode podczas korzystania z Treeset

Question

Chciałbym wiedzieć, co to znaczy, gdy javadocs dla TreeSet mówi "Ta klasa implementuje interfejs Set, wspierany przez instancję TreeMap"? W poniższym przykładzie nie zaimplementowałem metody Hashcode i nadal działa ona zgodnie z oczekiwaniem, tzn. Jest w stanie sortować obiekty. Zauważ, że celowo nie zaimplementowałem spójnej implementacji Równości, aby sprawdzić zachowanie 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); 
} 

} 

Ten przykład wypisuje [Ben Tom Tom Jon Tom wik] .Tak jest sortowane w oparciu o metodę CompareTo i hashcode() metoda wygląda nieistotne w tym scenario.However, TreeSet jest wspierany przez TreeMap, tak wewnętrznie, jeśli do sortowania jest używana TreeMap, w jaki sposób obiekt mapuje obiekt?

Answer 1

Twoja ComparisonObject wykorzystuje metodę hashCode zdefiniowaną na Object. Spróbuj dodać kilka różnych ComparisonLogic, z tymi samymi wartościami dla obu pól i zobacz, co się stanie.

Answer 2

Myślę, że stawiasz dwa pytania.

1, dlaczego Twój kod działa?

Jak Avi napisał w this tematu:

Kiedy nie zastąpić metodę hashCode(), klasa dziedziczy domyślne hashCode() metoda z Object, co daje każdy obiekt odrębny kod skrótu . Oznacza to, że t1 i t2 mają dwa różne kody skrótu, nawet gdybyś je porównał, byłyby one równe. W zależności od konkretnej implementacji mapy, mapa jest wolna, aby przechowywać je osobno.

Oznacza to, że nie musi przechowywać ich osobno, ale może. Spróbuj ten kod:

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

Wyjście dla mnie był następujący:

true 
true 
true 
false 
false 
false 
false 
false 
false 

Oznacza to, że niektóre z nich były tam niektóre z nich nie.

2, co to znaczy, gdy javadocs dla Treeset mówi "Ta klasa implementuje interfejs Set, wspierany przez instancję TreeMap"?

Oznacza to, że klasa TreeSet w Javie 1.7 wygląda następująco:

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. 

Oznacza to, że nie jest mapą pod klasie TreeSet i istnieje wiele metod, które są delegowane tylko do niego .

Mam nadzieję, że mogę pomóc.

Answer 3

TreeSet wewnętrznie używa obiektu TreeMap 'm' do obiektów sklepowych jak pary klucz-wartość, która zakłada, że ​​wezwanie

set.add(x); 

wewnętrznie wywołuje metodę put TreeMap:

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

Teraz umieścić metoda wewnętrznie wywołuje albo porównanie, jeśli dostarczony jest Komparator, albo w twoim przypadku używa metody "porównajJako" ComparisonLogic.

W tym przypadku nigdy nie używa jawnie równego lub hashcode zamiast używać metody compareTo (Obiekt o1) (dostarczony podczas implementacji funkcji Porównywalne) lub porównać (Obiekt o1, obiekt o2) (pod warunkiem zastosowania metody Comparator) w celu określenia obecności obiektu w zestawie.

Tak więc, aby odpowiedzieć na twoje pytanie, nie jest wymagane zaimplementowanie metody hashcode(), chyba że używasz jej podczas porównywania (porównywania lub porównywania) implementacji metody.

Answer 4

To prawda, że ​​TreeSet wewnętrznie używa TreeMap. TreeMap nie musi mieć metody hashCode i equals zaimplementowanej dla obiektów kluczy. TreeMap używa wewnętrznie drzewa czerwono-czarnego, które jest samo równoważącym drzewem binarnym. Kolejność w tym drzewie jest utrzymywana przy użyciu metody compareTo (klucz obiekt implementuje interfejs porównywalny) lub metody porównywania (pod warunkiem, że komparator jest zdefiniowany podczas konstruowania TreeMap, w tym przypadku faktycznie dla TreeSet). Mam nadzieję, że to zniknie.