TreeSet与HashSet的区别

时间:2024-08-06 08:36:32

Set是java中一个不包含重复元素的collection。更正式地说,set 不包含满足 e1.equals(e2) 的元素对 e1e2,并且最多包含一个 null 元素。正如其名称所暗示的,此接口模仿了数学上的 set 抽象。

HashSet与TreeSet都是基于Set接口的实现类。其中TreeSet是Set的子接口SortedSet的实现类。Set接口及其子接口、实现类的结构如下所示:

|——SortedSet接口——TreeSet实现类
Set接口——|——HashSet实现类
  
              |——LinkedHashSet实现类

HashSet实现Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。它不保证集合的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用 null 元素。HashSet为基本操作提供了稳定性能,这些基本操作包括 add、remove、contains 和 size,假定哈希函数将这些元素正确地分布在桶中。对此集合进行迭代所需的时间与 HashSet 实例的大小(元素的数量)和底层 HashMap 实例(桶的数量)的“容量”的和成比例。因此,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。HashSet的实现是不同步的。如果多个线程同时访问一个集合,而其中至少一个线程修改了该集合,那么它必须
保持外部同步。

当需要向HashSet中放置元素时,应该为要存放到散列表的各个对象定义hashCode()和equals();

例如:

import
java.util.HashSet;
import java.util.Iterator;
public class HashSetTest
{
         public static void main(String[] args)
        
{
                 HashSet hs=new HashSet();
                
/**//*hs.add("one");
                 hs.add("two");
                
hs.add("three");
                 hs.add("four");*/
                
hs.add(new Student(1,"zhangsan"));
                 hs.add(new
Student(2,"lishi"));
                 hs.add(new
Student(3,"wangwu"));
                 hs.add(new
Student(1,"zhangsan"));
               
                 Iterator
it=hs.iterator();
                 while(it.hasNext())
                
{
                         System.out.println(it.next());
                
}
         }
}
class Student        
//HashSet要重写hashCode和equals方法
{
         int num;
         String
name;
         Student(int num,String name)
         {
                
this.num=num;
                 this.name=name;
         }
        
public String toString()
         {
                 return "num :"+num+"
name:"+name;
         }
         public int hashCode()
        
{
                 return num*name.hashCode();
         }
        
public boolean equals(Object o)
         {
                 Student
s=(Student)o;
                 return num==s.num &&
name.equals(s.name);
         }
}

TreeSet类实现 Set 接口,该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素,根据使用的构造方法不同,可能会按照元素的自然顺序 进行排序,或按照在创建 set 时所提供的比较器进行排序。是一个有序集合,元素中安升序排序,缺省是按照自然顺序进行排序,意味着TreeSet中元素要实现Comparable接口;我们可以构造TreeSet对象时,传递实现了Comparator接口的比较器对象.

例如:

import java.util.*;

public class TreeSetTest {
         public static void
main(String[] args)
         {
                 //TreeSet ts=new
TreeSet();
                 TreeSet ts=new TreeSet(new
Students.compareToStudent());
                 ts.add(new
Students(2,"zhangshan"));
                 ts.add(new
Students(3,"lishi"));
                 ts.add(new
Students(1,"wangwu"));
                 ts.add(new
Students(4,"maliu"));
               
                 Iterator
it=ts.iterator();
                 while(it.hasNext())
                
{
                         System.out.println(it.next());
                
}               
         }
}
class Students implements
Comparable
{
         int num;
         String name;
        
Students(int num,String name)
         {
                
this.num=num;
                 this.name=name;
         }
        
static class compareToStudent implements Comparator        
//定义一个内部类来实现比较器
         {
                 public int compare(Object o1,
Object o2) {
                         Students
s1=(Students)o1;
                         Students
s2=(Students)o2;
                         int rulst= s1.num > s2.num ? 1 :
(s1.num==s2.num ? 0 :-1);
                        
if(rulst==0)
                         {
                                
rulst=s1.name.compareTo(s2.name);
                         }               

                         return rulst;
                 }               

         }
         public int compareTo(Object o)                
//写具体的比较方法
         {
                 int result;
                
Students s=(Students)o;
                 result=num >s.num ? 1:(num==s.num
? 0 : -1);
                 if(result==0)
                
{
                         result=name.compareTo(s.name);
                
}
                 return result;
         }
         public String
toString()
         {
                 return num+":"+name;
        
}
}

HashSet是基于Hash算法实现的,其性能通常优于TreeSet,我们通常都应该使用HashSet,在我们需要排序的功能时,我门才使用TreeSet;

compareTo这个方法,当等于的时候就返回0,当大于就返回1,当小于就返回-1,就这么简单。

TreeSet类型是Java SE中唯一可实现自动排序的类型,用法如下:

import java.util.Comparator;

public class MyComparator<T> implements
Comparator<T> {

public int compare(T arg0, T arg1) {
        if
(arg0.equals(arg1)) {
            return 0;
        }
        return
((Comparable<T>) arg0).compareTo(arg1) * -1;
   
}

}

import java.util.Iterator;
import
java.util.TreeSet;

public class TreeSetTest {

/** *//**
     * @param args
     */
   
public static void main(String[] args) {

MyComparator<String> myComparator = new
MyComparator<String>();

// /////////////////////不添加自定义排序
       
TreeSet<String> treeSet1 = new TreeSet<String>();
       
treeSet1.add("c");
        treeSet1.add("a");
       
treeSet1.add("b");

Iterator<String> iterator1 =
treeSet1.iterator();
        while (iterator1.hasNext()) {
           
System.out.println(iterator1.next());
        }

// /////////////////////添加自定义排序
       
TreeSet<String> treeSet2 = new
TreeSet<String>(myComparator);
        treeSet2.add("c");
       
treeSet2.add("a");
        treeSet2.add("b");

Iterator<String> iterator2 =
treeSet2.iterator();
        while (iterator2.hasNext()) {
           
System.out.println(iterator2.next());
        }
   
}

}

运行结果:
a
b
c
c
b
a