Java的Set接口

Set接口簡介

Set接口是Collection的子接口，set接口沒有提供額外的方法。

Set集合不允許包含相同的元素，如果試把兩個相同的元素加入同一個 Set 集合中，則添加操作失敗。

Set判斷兩個對象是否相同不是使用 == 運算符，而是根據 equals 方法。

Set接口的執行個體無法像List接口那樣進行雙向輸出。

Set實作類之一：HashSet（散列存放）

HashSet 是 Set 接口的典型實作，由哈希表（實際上是一個 HashMap 執行個體）支援。大多數時候使用 Set 集合時都使用這個實作類。

HashSet 按 Hash 算法來存儲集合中的元素，是以具有很好的存取和查找性能。

HashSet 具有以下特點：

1）不能保證元素的排列順序（裡面不能存放重複元素，而且是采用散列的存儲方式）

2）HashSet 不是線程安全的

3）集合元素可以是 null

當向 HashSet 集合中存入一個元素時，HashSet 會調用該對象的 hashCode() 方法來得到該對象的 hashCode 值，然後根據 hashCode 值決定該對象在 HashSet 中的存儲位置。

HashSet 集合判斷兩個元素相等的标準：兩個對象通過 hashCode() 方法比較相等，并且兩個對象的 equals() 方法傳回值也相等。

HashSet的實作

對于 HashSet 而言，它是基于 HashMap 實作的， HashSet 底層使用 HashMap 來儲存所有元素，是以 HashSet 的實作比較簡單，相關 HashSet 的操作，基本上都是直接調用底層 HashMap 的相關方法來完成。

hashCode() 方法

如果兩個元素的 equals() 方法傳回 true，但它們的 hashCode() 傳回值不相等，hashSet 将會把它們存儲在不同的位置，但依然可以添加成功。

對于存放在Set容器中的對象，對應的類一定要重寫equals()和hashCode(Object obj)方法，以實作對象相等規則。

重寫 hashCode() 方法的基本原則：

1）在程式運作時，同一個對象多次調用 hashCode() 方法應該傳回相同的值

2）當兩個對象的 equals() 方法比較傳回 true 時，這兩個對象的 hashCode() 方法的傳回值也應相等

3）對象中用作 equals() 方法比較的 Field，都應該用來計算 hashCode 值

Set實作類之二：LinkedHashSet

LinkedHashSet 是 HashSet 的子類。

LinkedHashSet 根據元素的 hashCode 值來決定元素的存儲位置，但它同時使用連結清單維護元素的次序，這使得元素看起來是以插入順序儲存的。

LinkedHashSet插入性能略低于HashSet，但在疊代通路Set 裡的全部元素時有很好的性能。

LinkedHashSet 不允許集合元素重複。

Set實作類之三：TreeSet（有序存放）

TreeSet 是 SortedSet 接口的實作類，TreeSet可以確定集合元素處于排序狀态。

Comparator comparator()

Object first()

Object last()

Object lower(Object e)

Object higher(Object e)

SortedSet subSet(fromElement, toElement)

SortedSet headSet(toElement)

SortedSet tailSet(fromElement)

注：    [1]一個普通的類對象是不能向TreeSet集合中加入的，否則會出現異常：java.lang.ClassCastException。

[2]如果要想使用TreeSet則對象所在的類必須實作Comparable接口。

TreeSet的排序方法

TreeSet 兩種排序方法：自然排序和定制排序。預設情況下，TreeSet采用自然排序。

自然排序：

TreeSet 會調用集合元素的 compareTo(Object obj) 方法來比較元素之間的大小關系，然後将集合元素按升序排列。

如果試圖把一個對象添加到TreeSet時，則該對象的類必須實作Comparable接口。

實作 Comparable 的類必須實作 compareTo(Object obj) 方法，兩個對象即通過 compareTo(Object obj) 方法的傳回值來比較大小。

Comparable 的典型實作：

BigDecimal、BigInteger 以及所有的數值型對應的包裝類：按它們對應的數值大小進行比較

Character：按字元的 unicode值來進行比較

Boolean：true 對應的包裝類執行個體大于 false 對應的包裝類執行個體

String：按字元串中字元的 unicode 值進行比較

Date、Time：後邊的時間、日期比前面的時間、日期大

向 TreeSet 中添加元素時，隻有第一個元素無須比較compareTo()方法，後面添加的所有元素都會調用compareTo()方法進行比較。

因為隻有相同類的兩個執行個體才會比較大小，是以向 TreeSet 中添加的應該是同一個類的對象。

對于TreeSet 集合而言，它判斷兩個對象是否相等的唯一标準是：兩個對象通過 compareTo(Object obj) 方法比較傳回值。

當需要把一個對象放入 TreeSet 中，重寫該對象對應的 equals() 方法時，應保證該方法與 compareTo(Object obj) 方法有一緻的結果：如果兩個對象通過 equals() 方法比較傳回 true，則通過 compareTo(Object obj) 方法比較應傳回 0。

示例：

@Test

public void testTreeSet1() {

Set set = new TreeSet();

// 當Person類沒有實作Comparable接口時，當向TreeSet中添加Person對象時，

報ClassCastException

set.add(new Person("CC", 23));

set.add(new Person("MM", 21));

set.add(new Person("GG", 25));

set.add(new Person("JJ", 24));

set.add(new Person("KK", 20));

set.add(new Person("DD", 20));

for (Object str : set) {

          System.out.println(str);

}

}

public class Person implements Comparable{

private String name;

private Integer age;

//getter&setter&const…

@Override

public int hashCode() {

//return age.hashCode() + name.hashCode();沒下述的健壯性好。

final int prime = 31;

int result = 1;

result = prime * result + ((age == null) ? 0 : age.hashCode());

result = prime * result + ((name == null) ? 0 : name.hashCode());

return result;

}

@Override

public boolean equals(Object obj) {

if (this == obj)

    return true;

if (obj == null)

    return false;

if (getClass() != obj.getClass())

    return false;

Person other = (Person) obj;

if (age == null) {

    if (other.age != null)

        return false;

    } else if (!age.equals(other.age))

        return false;

if (name == null) {

    if (other.name != null)

        return false;

} else if (!name.equals(other.name))

    return false;

return true;

}

//當向TreeSet中添加Person類的對象時，依據此方法，确定按照哪個屬性排列。

@Override

public int compareTo(Object o) {

if(o instanceof Person){

    Person p = (Person)o;

    int i = this.age.compareTo(p.age);

    if(i == 0){

        return this.name.compareTo(p.name);

    }else{

        return i;

    }

}

return 0;

}

}

定制排序：

TreeSet的自然排序是根據集合元素的大小，進行元素升序排列。如果需要定制排序，比如降序排列，可通過Comparator接口的幫助。需要重寫compare(T o1,T o2)方法。

利用int compare(T o1,T o2)方法，比較o1和o2的大小：如果方法傳回正整數，則表示o1大于o2；如果傳回0，表示相等；傳回負整數，表示o1小于o2。

要實作定制排序，需要将實作Comparator接口的執行個體作為形參傳遞給TreeSet的構造器。此時，仍然隻能向TreeSet中添加類型相同的對象。否則發生ClassCastException異常。

使用定制排序判斷兩個元素相等的标準是：通過Comparator比較兩個元素傳回了0。

示例：

測試類：

public void testTreeSet3() {

      TreeSet set = new TreeSet(new Comparator() {

public int compare(Object o1, Object o2) {

    if (o1 instanceof Customer && o2 instanceof Customer) {

        Customer c1 = (Customer) o1;

        Customer c2 = (Customer) o2;

        int i = c1.getId().compareTo(c2.getId());

        if (i == 0) {

            return c1.getName().compareTo(c2.getName());

        }

        return i;

    }

    return 0;

}

      });

      set.add(new Customer("AA", 1003));

      set.add(new Customer("BB", 1002));

      set.add(new Customer("GG", 1004));

      set.add(new Customer("CC", 1001));

      set.add(new Customer("DD", 1001));

      for (Object str : set) {

            System.out.println(str);

      }

}

Customer類：

public class Customer {

private String name;

private Integer id;

//getter&setter&cosntr…

@Override

public int hashCode() {

      final int prime = 31;

      int result = 1;

      result = prime * result + ((id == null) ? 0 : id.hashCode());

      result = prime * result + ((name == null) ? 0 : name.hashCode());

      return result;

}

@Override

public boolean equals(Object obj) {

//……

}

}

Comparable 和 Comparator 接口是幹什麼的？

Java 提供了隻包含一個 compareTo()方法的 Comparable 接口。這個方法可以個給兩個對象排序。具體來說，它傳回負數， 0，正數來表明輸入對象小于，等于，大于已經存在的對象。

Java 提供了包含 compare()和 equals()兩個方法的 Comparator 接口。 compare()方法用來給兩個輸入參數排序，傳回負數， 0，正數表明第一個參數是小于，等于，大于第二個參數。 equals()方法需要一個對象作為參數，它用來決定輸入參數是否和 comparator 相等。隻有當輸入參數也是一個 comparator 并且輸入參數和目前 comparator 的排序結果是相同的時候，這個方法才傳回 true。

HashSet 和 TreeSet 有什麼差別？

HashSet 是由一個 hash 表來實作的，是以，它的元素是無序的。 add()， remove()， contains()方法的時間複雜度是 O(1)。

另一方面， TreeSet 是由一個樹形的結構來實作的，它裡面的元素是有序的。是以， add()，remove()， contains()方法的時間複雜度是 O(logn)。