TreeSet 、HashSet、LinkedHashSet的特点_treeset、hashset的特点

不少大公司的面试题中会问TreeSet和HashSet有什么区别。此外LinkedHashSet也是Set的一种实现类,下面归纳的是三者的特点。

        HashSet是基于哈希表(Hash表)实现的,它不能保证线程安全,其中允许存在null元素,但null元素只能有1个。

        当程序员向HashSet中插入一个对象时, HashSet会调用该对象的hashCode()方法(如果该对象没定义,会调用Object)来得到该对象的hashCode值;然后会根据hashCode值来决定该对象在HashSet中的存放位置,如果遇到两个对象的hashCode值一致的情况则说明它们相等, HashSet同样不会允许插入重复的元素。

        上述描述包含了一层隐藏的含义, HashSet不能保证插入次序和遍历次序一致。

相比之下,LinkedHashSet同样是基于Hash表,它也是根据元素的hashCode值来决定元素的存储位置的,但是它同时也采用了链表的方式来保证插入次序和遍历次序一致。下面可LinketHashSetDemo.java例子看出两者的区别。

 
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
 
public class LinkedHashSetDemo {
 
    public static void main(String[] args) {
 
        Set<String> strHashSet = new HashSet<String>();
 
        Set<String> strLinkedHashSet = new LinkedHashSet<String>();
 
        for(int i = 0; i<10; i++){
 
            strHashSet.add(String.valueOf(i));
 
            strLinkedHashSet.add(String.valueOf(i));
 
        }
 
        Iterator<String> setStringIt = strHashSet.iterator();
 
        while (setStringIt.hasNext())
        {
            System.out.print(setStringIt.next()+" ");
        }
 
        System.out.println();
 
        Iterator<String> linkedSetStringIt = strLinkedHashSet.iterator();
 
        while (linkedSetStringIt.hasNext())
        {
            System.out.print(linkedSetStringIt.next()+" ");
        }
    }
}

        在main函数的第11- 14行中,通过for循环语句向两种集合中依次放入了1-10

        这10个String类型的对象,然后通过迭代器,在第17~21行中通过两个while循环分别按顺序输出它们的值,结果如下。

1 3 2 1 0 7 6 5 4 9 8 
2 0 1 2 3 4 5 6 7 8 9

        第1行是针对HashSet的输出,从中可以看到它的遍历结果和插入的次序不一致;而,第2行是针对LinkedHashSet,输出次序和插入次序一致。

而TreeSet是SortedSet接口的唯一实现类,它是用二叉树存储数据的方式来保证存储的元素处于有序状态,下面来看TreeSetDemo.java例子。

 
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
 
public class TreeSetDemo {
 
    public static void main(String[] args){
 
        Set<String> treeSet = new TreeSet<String>();
 
        treeSet.add("4");
 
        treeSet.add("3");
 
        treeSet.add("1");
 
        treeSet.add("2");
 
        Iterator<String> setStringIt = treeSet.iterator();
 
        while(setStringIt.hasNext()){
 
            System.out.print(setStringIt.next() + " ");
        }
    }
}

        在第4行中,以泛型的方式创建了一个TreeSet,并从第6-9行,以无序的方式插入了4个String对象。注意, TreeSet不允许插入null值,所以运行第10行的代码时会有异常。

        当程序员在第14行通过迭代器遍历TreeSet对象时,会发现输出的次序和插入次序不一致,而且数据已经被排序,结果如下。

1 2 3 4 

        如果TreeSet中存储的不是上例中的基本数据类型,而是自定义的class,那么这个类必须实现Comparable接口中的compareTo方法, TreeSet会根据compareTo中的定义来区分大小,最终确定TreeSet中的次序。

        程序员可以在compareTo方法中定义排序依据。在前面的compareTo方法中,是以学生的id作为判断依据的,如果两个学生的id相等,那么这个方法的返回值是0,说明这两个学生是相等的(是同一个学生)。

        此外,该方法还可以返回1或-1,其中1表示大于,-1表示小于。下面通过SortedStudent.java例子来看TreeSet是如何对自定义类进行排序的。

 
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
 
class SortedStudent {
 
    private int id;
 
    public SortedStudent(int id) {this.id = id;}
 
    public int getId(){return id;}
 
    public boolean equals(SortedStudent stu)
    {
 
        if(stu.getId() == this.id)
        {
            return true;
        }
 
        else {
            return false;
        }
    }
 
 
 
    public int compareTO(Object obj){
 
        if(obj instanceof SortedStudent) {
 
            SortedStudent s = (SortedStudent) obj;
            if(s.getId() == this.getId())
            {
                return 0;
            }
            else{
                return s.getId()>this.getId()?-1:1;
            }
        }else{
 
            return 0;
        }
 
    }
 
 
}
 
public class SortStudentByID{
 
    public static void main(String[] args){
 
        SortedStudent s1 = new SortedStudent(1);
 
        SortedStudent s2 = new SortedStudent(2);
 
        SortedStudent s3 = new SortedStudent(3);
 
        SortedStudent s4 = new SortedStudent(4);
 
        Set<SortedStudent> stuSet = new TreeSet<SortedStudent>();
 
        stuSet.add(s2);
 
        stuSet.add(s4);
 
        stuSet.add(s1);
 
        stuSet.add(s3);
 
        Iterator<SortedStudent> itStu = stuSet.iterator();
        while(itStu.hasNext()){
 
            System.out.println(itStu.next().getId());
        }
    }
}
 

在第2行定义的SortedStudent类的代码中,实现了Compareable接口。在第16行,程序员重写了compareTo方法,在这个方法中,如果两个学生对象的id相等,则认为它们相等,否则将用id的大小来判断大小。

在第38-41行中,虽然程序员用乱序的方式放入了4个学生对象,但TreeSet会自动地对它们进行排序,这可以从第46行的输出结果中得到验证。