TreeSet内部使用TreeMap,因此在使用Treeset时是否需要实现Hashcode方法？

Question

我想知道这是什么意思时的javadoc的TreeSet说

这个类实现了由TreeMap实例支持的Set接口？

在下面的示例中,我还没有实现该Hashcode方法,但仍按预期工作,即它能够对对象进行排序.请注意,我故意没有实现一致的Equals实现来检查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);
}

}

这个例子打印[Tom Ben, Tom jon, Tom Wik].因此,基于compareTo方法和hashcode()方法的排序在这种情况下看起来微不足道.但是,Treeset由TreeMap支持,所以内部if TreeMap用于排序,如何TreeMap散列对象？

Answer 1

我想你提出了两个问题.

1,为什么你的代码有效？

正如Avi在这个主题上所写:

当你不重写的hashCode()方法,你的类继承自对象的默认的hashCode()方法,这给每一个对象不同的散列码.这意味着t1和t2有两个不同的哈希码,即使你要比较它们,它们也是相同的.根据特定的HashMap实现,地图是免费的,以分开存放.

这意味着它不必单独存储它们,但它可能.试试这段代码:

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

我的输出如下:

true
true
true
false
false
false
false
false
false

这意味着其中一些人不在其中.

2,当Treeset的javadocs说'这个类实现了由TreeMap实例支持的Set接口'时,它意味着什么？

这意味着java 1.7中的TreeSet类如下所示:

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.

这意味着TreeSet类下面有一个映射,并且有很多方法只被委托给它.

我希望我能帮忙.

Answer 2

确实，TreeSet 内部使用了 TreeMap。TreeMap 不需要为关键对象实现 hashCode 和 equals 方法。TreeMap内部使用红黑树，这是一种自平衡二叉搜索树。该树中的顺序是通过使用compareTo方法（关键对象实现Comparable接口）或compare方法（假设在构造TreeMap时定义了比较器，在本例中实际上是TreeSet）来维护的。希望它能清除。

Answer 3

您ComparisonObject正在使用hashCode上定义的方法Object。尝试添加多个不同的ComparisonLogic，两个字段具有相同的值，然后看看会发生什么。