11

I would like to know what it means when javadocs for TreeSet says

This class implements the Set interface, backed by a TreeMap instance?

In the below example, I haven't implemented the Hashcode method and still it is working as per expectation i.e it is able to sort the objects. Notice that I have purposely not implemented a consistent Equals implementation to check the TreeSet behaviour.

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

}

This example prints [Tom Ben, Tom jon, Tom Wik]. So it is sorting based on the compareTo method and hashcode() method looks insignificant in this scenario. However, Treeset is backed by TreeMap, so internally if TreeMap is used for sorting, how is TreeMap hashing the object?

4

4 回答 4

9

我认为你提出了两个问题。

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

正如Avi在此主题中所写：

当您不覆盖 hashCode() 方法时，您的类会从 Object 继承默认的 hashCode() 方法，这会为每个对象提供不同的哈希码。这意味着 t1 和 t2 有两个不同的哈希码，即使你比较它们，它们也是相等的。根据特定的 hashmap 实现，map 可以自由地单独存储它们。

这意味着它不必单独存储它们，但它可能会。试试这个代码：

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说'这个类实现了Set接口，由TreeMap实例支持'是什么意思？

这意味着 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 类下面有一个映射，并且有很多方法只委托给它。

我希望我能帮上忙。

于 2014-01-22T18:22:59.413 回答
5

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

于 2017-02-20T13:33:24.817 回答
1

TreeSet 在内部使用 TreeMap 对象“m”将对象存储为键值对，这意味着调用

set.add(x);

内部调用 TreeMap 的 put 方法：

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

现在 put 方法在内部调用比较，如果提供了比较器，或者在您的情况下使用比较逻辑类“compareTo”方法。

它从不显式使用等于或哈希码，而是使用 compareTo(Object o1)（在实现 Comparable 时提供）或 compare(Object o1, object o2)（在实现 Comparator 时提供）方法来确定集合中 Object 的存在。

因此，要回答您的问题，除非您在比较（compare 或 compareTo）方法实现中使用它，否则不需要实现 hashcode() 方法。

于 2016-09-08T12:43:03.237 回答
0

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

于 2012-06-13T08:57:11.893 回答