HashSet与TreeSet浅析

标签（空格分隔）： java

---

今天来讲讲学到的Java Collection里两种数据结构：TreeSet与HashSet。

一. 区别：

HastSet使用散列表进行存储，元素无序，允许为null
TreeSet是使用树结构来进行存储，元素按字符串顺序排序存储，元素不允许为null

代码演示：

//HashSet
Set set1 = new HashSet();
set1.add("first");
set1.add("second");
set1.add("third");
System.out.println(set1);
//输出结果：[third, first, second]

//TreeSet
Set set2 = new TreeSet();
set2.add("first");
set2.add("second");
set2.add("third");
set2.add("forth");
System.out.println(set2);
//输出结果：[first,forth, second, third]

二. 有关对象的比较：

相较于List，Set没有序列的概念，正如我们所学到的集合，具有非重复性。来看下列代码：

//set is not sequencial,doesn't have positiion
List list = new ArrayList();
list.add(123);
list.add(123);
//about hashSet
Set set1 = new HashSet();
set1.add(123);
set1.add(123);//have no use
System.out.println(set1.size());
//输出结果：1

从上述代码可以看出，不能重复给HashSet加123这个整型元素，但是当我们添加的对象时，情况会有所不同。比如我们有如下这个Person类，并向HashSet中添加Person对象时：

class Person{
    int pid;
    String name;
    public Person(int pid, String name){
        super();
        this.pid = pid;
        this.name = name;
    }
}
public class Test{
    public static void main(String[], args){
        set1.add(new Person(1,"abc"));
        set1.add(new Person(1,"abc"));
        //now they are not actually the same
        System.out.println(set1.size());
        //输出结果：2
    }
}

这里之所以认为先后添加的对象不重复，是因为默认的HashCode函数不会给两个对象赋予相同的hashCode值，而hashCode值不同，则不能认定为相同对象。至于HashCode函数是什么，让我们往下看。

既然我们添加了两个属性一模一样的对象都不会被默认方法认定为重复，那有什么方法来改变这种情况呢？
大家都知道，所有的自定义类都继承于Object类，Object类中有equals方法，专门用来判断两个对象是否相等。讲到这里可能有同学会提出，我在Person类里重写一下equals方法是不是就行了呢？就像这样：

@override
    public boolean equals(object object){
        //to determine the important attribute
        Person p = (Person)object;
        return (this.pid == p.pid);
    }

这样，当两个对象的pid相等时，就认为这两个对象重复，从而不会重复添加到HashSet里了？NONONO！这里就要回到我们刚才提到过的hashCode方法了。。。。呜呜呜呜，寝室断电了，而我又是个严格作息的好孩子，明天见吧（不过睡前先喝一杯牛奶啦）。

---

好了，让我们继续。首先要弄明白为什么要有hashCode这个方法。试想一下，如果对于一个HashSet里的值，每尝试添加一个元素时，都要一一与已有元素作比较，调用equals方法，假设HashSet的size为n，则添加过程总共执行了$$m=1+2+3+...+n-1=(n-1)(n-2)/2$$次equals方法！这是非常耗时的，所以必须采取策略来减少equals方法的调用次数。而HashCode方法会根据对象的属性返回一个哈希码，HashSet把此哈希码转化成一个数组下标，来标记该对象的位置，如果该位置上的链表没有此元素，则代表当前HashSet中无此哈希码的对象，可以添加。如果该位置的链表里有元素，则此时通过HashCode已经无法判断这两个对象是否重复（此时成为conflict），此时再调用equals方法，进一步判断。HashCode工作原理如下：

HashCode工作原理

好了，我们知道，只有当两个对象发生conflict时，我们才调用equals方法来进行判断。那接下来让我们重载hashCode方法，完成最终的目的吧！

@override
public int hashCode(){
    final int prime = 31;  
    int result = 1;  
    result = prime * result + pid;  
    result = prime * result + ((name == null) ? 0 : name.hashCode());  
    return result;
    }

现在，简述一下完整的过程：当有新对象需要添加到HashSet中时，首先hashCode方法判断其hashCode是否已被标记，若未标记，则直接添加，否则，将其与HashSet中相同哈希码的元素用equals方法比较，最后确定是否为重复元素。
用法：一般HashCode与equals方法控制的都是同一个属性，比如，当添加Person对象时，只要其pid相同，就认为不可重复添加：

@override
class Person{
    int pid;
    String name;
    public Person(int pid, String name){
        super();
        this.pid = pid;
        this.name = name;
    }
    @override
    public boolean equals(object object){
        //to determine the important attribute
        Person p = (Person)object;
        return (this.pid == p.pid);
    }
    @override
    public int hashCode(){
        final int prime = 31;  
        int result = 1;  
        result = prime * result + pid;  //note here we choose pid as our important attribute
        return result;
    }

}

public class Test{
    public static void main(String[], args){
        Set set1 = new HashSet();

        set1.add(new Person(1,"abc"));
        set1.add(new Person(1,'abd'));//here we have oerride the hashCode() and equals(), and choose pid as important attribute.
        
        //add the second object, it depends on whether they are the same
        //but when we override the equal method of the class Person, the JVM will know how to campare the two objects,
        //if the two objects are recognized as the same, it will not add the second one.
        //and we can override the hashCode method to select some diffrent objects instead of invoking equals method many times
        
        System.out.prinln(set1.size());
        //输出结果：1
    }
}

有关HashSet的对象比较就到这里啦（好像有点啰嗦，见谅^_）
下面看有关TreeSet：
TreeSet采用的比较方式是实现Campare接口，并重载campareTo方法，来比较两个对象是否相等：

class Person implements Camparable{
    int pid;
    String name;
    public Person(int pid, String name){
        super();
        this.pid = pid;
        this.name = name;
    }

    @override
    public int campareTo(object o){
        //that means when their pid is the same, they are regarded as the same
        Person p = (Person)o;
        return pid-p.pid;
    }
}

方法很简单，返回负值则代表当前对象小于比较对象，其他两种情况类推。
至于TreeSet的原理，也很简单，构建一个二叉树，节点的左子树比它大，右子树它他小。当新对象进入时，对每个节点进行比较，比节点大则进入左子树...这样，至多通过log2(n)次比较就能判断元素是否重复。

三、最后

有关这两种数据结构，还有很多地方还没涉及。可能以后还会作补充，如果希望了解更多，这里给出了官方API的链接
HashSet、TreeSet

第一次写笔记，也是为数不多的使用markdown，希望自己能养成习惯，这里纯粹是个人分享，如有不对或不足的地方，请多多指正！