java TreeSet内部使用TreeMap，那么使用Treeset时是否需要实现Hashcode方法？

TreeSet internally uses TreeMap, so is it required to implement Hashcode method when using Treeset?

提问by Metalhead

I would like to know what it means when javadocsfor TreeSetsays

我想知道javadocsforTreeSet说的是什么意思

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

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

In the below example, I haven't implemented the Hashcodemethod 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 Equalsimplementation to check the TreeSetbehaviour.

在下面的示例中，我还没有实现该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);
}

}

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

此示例打印[Tom Ben, Tom jon, Tom Wik]. 所以它是基于compareTo方法的排序，并且hashcode()方法在这种情况下看起来无关紧要。但是，Treeset是由TreeMap支持的，所以内部如果TreeMap用于排序，如何TreeMap对对象进行哈希处理？

回答by user2424380

I think you are posing two questions.

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

1, Why is your code working?

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

As Aviwrote at thistopic:

正如Avi在该主题中所写：

When you don't override the hashCode() method, your class inherits the default hashCode() method from Object, which gives every object a distinct hash code. This means that t1 and t2 have two different hash codes, even though were you to compare them, they would be equal. Depending on the particular hashmap implementation, the map is freeto store them separately.

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

This means it doesn't have to store them separately but it might. Try this code:

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

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

The output for me was the following:

我的输出如下：

true
true
true
false
false
false
false
false
false

That means some of them were there some of them not.

这意味着他们中的一些人在那里，有些人不在。

2, What it means when javadocs for Treeset says 'This class implements the Set interface, backed by a TreeMap instance'?

2、Treeset 的javadocs 说'这个类实现了Set 接口，由一个TreeMap 实例支持'是什么意思？

It means that the TreeSet class in java 1.7 looks like the following:

这意味着 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.

This means that there is a map underneath the TreeSet class and there is a lot of methods which is only delegated to it.

这意味着在 TreeSet 类下面有一个映射，并且有很多只委托给它的方法。

I hope I could help.

我希望我能帮上忙。

回答by Sohan Lal

It is true that TreeSet internally uses TreeMap. TreeMap doesn't need to have hashCode and equals method implemented for key objects. TreeMap internally uses Red-Black tree which is a self balancing binary search tree. Order in this tree is maintained by using either compareTo method (key object implements Comparable interface) or compare method (provided comparator is defined while constructing TreeMap, in this case for TreeSet actually). Hope it clears.

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

回答by Neelam

TreeSet internally uses TreeMap object 'm' to store objects as key-value pair which implies that the call

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

set.add(x);

internally calls put method of TreeMap:

内部调用TreeMap的put方法：

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

Now put method internally calls either compare if Comparator is provided or in your case uses ComparisonLogic class "compareTo" method.

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

It never uses equals or hashcode explicitly instead uses compareTo(Object o1) (provided while implementing Comparable) or compare(Object o1, object o2) (provided while implementing Comparator) method to determine the presence of Object in the set.

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

so to answer your question it is not required to implement hashcode() method unless you are using it in your comparison (compare or compareTo) method implementation.

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

回答by Russell

Your ComparisonObjectis using the hashCodemethod defined on Object. Try adding a number of different ComparisonLogic's, with the same values for both the fields, and see what happens.

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