TreeSet内部使用TreeMap，那么使用Treeset时是否需要实现Hashcode方法? [英] TreeSet internally uses TreeMap, so is it required to implement Hashcode method when using Treeset?

问题描述

我想知道当 TreeSet 的 javadocs 说

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

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

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

在下面的示例中，我还没有实现 Hashcode 方法，但它仍然按预期工作，即它能够对对象进行排序.请注意，我故意没有实现一致的 Equals 实现来检查 TreeSet 行为.

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

}

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

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?

推荐答案

我认为您提出了两个问题.

I think you are posing two questions.

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

正如 Avi 在 这个主题:

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

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 free to store them separately.

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

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

我的输出如下:

true
true
true
false
false
false
false
false
false

这意味着有些人在那里，有些人不在.

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

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

意思是java 1.7中的TreeSet类如下所示:

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

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

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内部使用TreeMap，那么使用Treeset时是否需要实现Hashcode方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！