集合之四

HashSet
实现Set接口的hash table(哈希表)，依靠HashMap来实现的。
我们应该为要存放到散列表的各个对象定义hashCode()和equals()。

import  java.util. * ;
class  HashSetTest
... {
    public static void main(String[] args)
    ...{
        HashSet hs=new HashSet();
        /**//*hs.add("one");
        hs.add("two");
        hs.add("three");
        hs.add("one");*/
        hs.add(new Student(1,"zhangsan"));
        hs.add(new Student(2,"lisi"));
        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
... {
    int num;
    String name;
    Student(int num,String name)
    ...{
        this.num=num;
        this.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);
    }
    public String toString()
    ...{
        return num+":"+name;
    }
}

散列表
散列表又称为哈希表。散列表算法的基本思想是：
  以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。
当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子(load factor)来决定何时对散列表进行再散列。例如：如果负载因子是0.75，当散列表中已经有75%的位置已经放满，那么将进行再散列。
负载因子越高(越接近1.0)，内存的使用效率越高，元素的寻找时间越长。负载因子越低(越接近0.0)，元素的寻找时间越短，内存浪费越多。
HashSet类的缺省负载因子是0.75。
TreeSet
TreeSet是依靠TreeMap来实现的。
TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。
我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。
HashSet和TreeSet的比较

import  java.util. * ;
class  TreeSetTest
... {
    public static void main(String[] args)
    ...{
        TreeSet ts=new TreeSet(new Student.StudentComparator());
        /**//*ts.add("winsun");
        ts.add("weixin");
        ts.add("mybole");*/
        ts.add(new Student(2,"lisi"));
        ts.add(new Student(1,"wangwu"));
        ts.add(new Student(3,"zhangsan"));
        ts.add(new Student(3,"mybole"));
        
        Iterator it=ts.iterator();
        while(it.hasNext())
        ...{
            System.out.println(it.next());
        }
    }
}

class  Student  implements  Comparable
... {
    int num;
    String name;
    static class StudentComparator implements Comparator
    ...{
        public int compare(Object o1,Object o2)
        ...{
            Student s1=(Student)o1;
            Student s2=(Student)o2;
            int result=s1.num > s2.num ? 1 : (s1.num==s2.num ? 0 : -1);
            if(result==0)
            ...{
                result=s1.name.compareTo(s2.name);
            }
            return result;
        }
    }
    Student(int num,String name)
    ...{
        this.num=num;
        this.name=name;
    }
    
    public int compareTo(Object o)
    ...{
        Student s=(Student)o;
        return num > s.num ? 1 : (num==s.num ? 0 : -1);
    }
    public String toString()
    ...{
        return num+":"+name;
    }
}

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