Java中Set接口及其實現

閑來看看 2012-04-10

展開全文

Java中Set接口及其實現 Set接口及其實現
1.Set接口
Set是對數學上集的抽象,Set中不包含重復的元素.如何界定是否是重復元素?Set最多可含一個null元素;對于任意的非null元素e1和e2,都滿足e1.equals(e2)==false.
Object.hashcode()的約定:
a.在程序的一次執行中,無論何時在同一個java對象上重復調用hashcode(),都必須一致地返回同一個整數值,并不像Object.equals()那樣提供Object是否被修改了的信息,但這個整數值不必在同一個應用程序的多次運行之間保持一致.
b.如果兩個Object通過equals()判斷是相等的,那么,在這兩個Object上調用hashcode()必返回相同的值.
c.如果兩個Object通過equals()判斷是不相等的,那么,并不要求這兩個Object.hashcode()返回不同的整數值.
集合操作:
   并         s1.addAll()原
   交         s1.retainAll(s2)原
非對稱差    s1.remove(s2)
對稱差      Set symmetricDiff = new HashSet(s1);
              symmertricDiff.add(s2);
              Set tmp = new HashSet(s1);
              tmp.retainAll(s2);
              symmertricDiff.removeAll(tmp);
              則,symmertricDiff即為s1和s2的對稱差.
相對補      Set relativeCompl = new HashSet(s1);
              Set tmp = new HashSet(s1);
              tmp.retainAll(s2);
              relativeCompl.removeAll(tmp);
              則,relativeCompl稱為s2的相對補.
2.Set實現
HashSet是使用一個哈希表存儲元素的,是非排序的,可以隨機訪問,是Set的最優性能實現.TreeSet實現了SortedSet接口,使用一個紅黑樹來存儲元素,提供了元素的有序存儲和訪問.
2.1 HashSet
HashSet在底層實現上依賴于HashMap.
    HashSet的代碼片斷:
// Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

public HashSet() {
map = new HashMap<E,Object>();
}

public boolean add(E o) {
return map.put(o, PRESENT)==null;
}

public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

    public boolean contains(Object o) {
       return map.containsKey(o);
    }
從代碼可見,HashSet在底層借用HashMap,使用一個Object類型的啞元值作為HashSet中元素在底層HashMap存儲中的映射值.它抓住了HashMap的鍵不允許重復的特性.對于add()中調用底層映射的put(),將欲添加的元素和一個PRESENT啞元值放入底層map.如果底層Map返回null,說明原來的集合中并不存在該鍵.對于Map接口的put()返回null時有兩種解釋,一是原來的Map中不包含該鍵;另一種可能是原來的Map中已經存儲了該健,但該鍵映射到null.而在HashSet中的add()和remove()等中的返回null只有一種解釋,即原來的集合不包含該元素.這是因為HashSet的底層的映射中存儲的都是一個名為PRESENT的Object類型的對象,不可能是null.

2.2 TreeSet
   Set接口有一個子接口:SortedSet,提供了集合元素的順序存儲,其中元素保持升序排列.為了在加入一個元素到SortedSet實現時能對這些元素排序,元素類型必須實現Comarable接口,或者建立SortedSet時使用Comparator.否則程序在運行時將拋出ClassCastException.
3.使用Set的注意事項
如果Set中存儲了可變對象,當這些對象出現重復元素,從而從根本上違反了Set的約定,Set的行為也變得不確定.所以,在Set中存儲可變對象時,一定要十分小心.同樣,對于Map中的key也一樣,因為Map中的key也是不允許重復的.
    //DupEleSet.java
class DupEleSet{
   public static void main(String [] args)
   {
       Calendar cld=new Calendar.getInstance();
       cld.set(2003,0,1);

Date d1 = cld.getTime();

cld.set(2005,10,2);
Date d2 = cld.getTime();

         Set s = new HashSet();
          s.add(d1);
         s.add(d2);

System.out.println("before modify:"+s);

d1.setTime(d2.getTime());

System.out.println("after modified:"+s);

}
}
上面的程序輸出:
before modify:[Wed Jan 01 21:54:19 cst 2003,Thu Nov 02 21:54:19 cst 2000]
after modifyied:[Wed Jan 01 21:54:19 cst 2000,Thu Nov 02 21:54:19 cst 2000]