一個(gè)集合不包括重復(fù)的元素。這是使用集合的主要原因之一。有三種常見的集合實(shí)現(xiàn)：HashSet、TreeSet和LinkedHashSet。何時(shí)何地使用它們是個(gè)重要的問題。
簡(jiǎn)單來說：
如果你需要一個(gè)快速的集合，你應(yīng)該選擇HashSet；
如果你需要一個(gè)排序的集合，你應(yīng)該選擇TreeSet；
如果你需要一個(gè)可以存儲(chǔ)插入順序的集合，應(yīng)該使用LinkedHashSet。
1.集合接口
集合接口繼承了Collection接口，在集合中，不能有重復(fù)的元素。所有集合中的元素必須是唯一的。你可以簡(jiǎn)單的添加元素到集合中，重復(fù)的會(huì)被自動(dòng)的清除。
2. HashSet vs. TreeSet vs.LinkedHashSet
HashSet 通過hash table來實(shí)現(xiàn)。元素是無序的。 添加、刪除和包含的方法都有固定的時(shí)間復(fù)雜度O(1).
TreeSet 通過樹（算法書中的紅黑樹）結(jié)構(gòu)實(shí)現(xiàn)。集合中的元素是排序的，但是添加、刪除和包含方法時(shí)間復(fù)雜度為O（log（n））。它提供了幾種方法來處理有序集，如：first()，last()，headSet()，lastSet()等。
LinkedHashSet 在HashSet和TreeSet之間。它被實(shí)現(xiàn)為一個(gè)哈希表，其中有一個(gè)鏈表通過它運(yùn)行，因此它提供了插入的順序?；痉椒ǖ臅r(shí)間復(fù)雜度為O(1).
3. TreeSet例子
TreeSet<Integer> tree = new TreeSet<Integer>();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);
Iterator<Integer> iterator = tree.iterator();
System.out.print("Tree set data: ");
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
輸出是排序的如下：
Tree set data: 12 34 45 63
現(xiàn)在我們定一個(gè)名字叫Dog的類如下：
class Dog {
int size;
public Dog(int s) {
size = s;
}
public String toString() {
return size + "";
}
}
讓我們來添加一些dogs到TreeSet如下：
import java.util.Iterator;
import java.util.TreeSet;
public class TestTreeSet {
public static void main(String[] args) {
TreeSet<Dog> dset = new TreeSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}
編譯沒問題，但是運(yùn)行時(shí)候卻發(fā)生了錯(cuò)誤。
Exception in thread "main" java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(Unknown Source)
at java.util.TreeSet.add(Unknown Source)
at collection.TestTreeSet.main(TestTreeSet.java:22)
因?yàn)門reeSet是被排序的，Dog對(duì)象需要實(shí)現(xiàn)java.lang.Comparable's的compareTo() 方法如下：
class Dog implements Comparable<Dog>{
int size;
public Dog(int s) {
size = s;
}
public String toString() {
return size + "";
}
@Override
public int compareTo(Dog o) {
return size - o.size;
}
}
輸出如下：
1 2 3
4. HashSet 例子
HashSet<Dog> dset = new HashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
輸出：
5 3 2 1 4
5. LinkedHashSet 例子
LinkedHashSet<Dog> dset = new LinkedHashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
輸出的順序和插入的順序是一樣的。
2 1 3 5 4
6.性能測(cè)試
以上方法測(cè)試三個(gè)類add()方法上性能。
public static void main(String[] args) {
Random r = new Random();
HashSet<Dog> hashSet = new HashSet<Dog>();
TreeSet<Dog> treeSet = new TreeSet<Dog>();
LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
// start time
long startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
hashSet.add(new Dog(x));
}
// end time
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
treeSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet: " + duration);
// start time
startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
linkedSet.add(new Dog(x));
}
// end time
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet: " + duration);
}
通過下面的輸出，我們可以清晰看到HashSet是最快的。
HashSet: 2244768
TreeSet: 3549314
LinkedHashSet: 2263320
- 測(cè)試并不精確，但是可以反映出TreeSet由于被排序而慢的多的基本思想。
