set是用來存儲沒有重復(fù)的元素的。set在java中有三種比較常用實現(xiàn)：HashSet, TreeSet and LinkedHashSet泡孩。所以，不同的時候我們自然需要考慮如何選擇使用不同的set噪伊。這就要我們對于這三種set的特點和實現(xiàn)有一定的了解窿锉。一般來說，如果我們需要一個存取效率比較高的set轧简，我們可以選擇hashset驰坊，如果我們需要一個可以自動給元素排序的set，我們就需要使用treeset哮独，如果我們想要元素按插入的樣子保持順序拳芙，那么我們就可以使用LinkedHashSet。
hashset通過哈希表實現(xiàn)皮璧，元素是不排序的舟扎，所以輸出set的時候元素的順序是隨機(jī)的，add,remove, and contains這三個方法的時間復(fù)雜度都是常數(shù) O(1)恶导。
treeset通過紅黑樹實現(xiàn)浆竭，元素是排好序的浸须，但是相應(yīng)的操作時間復(fù)雜度就增加了惨寿，add,remove, and contains這三個方法的時間復(fù)雜度都是 O(log (n))
LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table
with a linked list running through it, so it provides the order of insertion. The time
complexity of basic methods is O(1)
LinkedHashSet是介于HashSet and TreeSet.之間邦泄。通過一個帶鏈表的哈希表實現(xiàn)，所以它是按插入順序排序的裂垦，保持插入的順序顺囊，基本操作的時間復(fù)雜度和hashset一樣都是常數(shù)時間。
** 注意的是蕉拢，treeset由于需要對元素排序特碳，所以添加的元素需要實現(xiàn)comparable或者comparator，不然就會報錯 **像下面這個例子
import java.util.Iterator;
import java.util.TreeSet;
public class SetTest {
public static void main(String[] args) {
TreeSet<Dog> tree = new TreeSet<>();
tree.add(new Dog(1));
tree.add(new Dog(5));
tree.add(new Dog(3));
Iterator<Dog> iter = tree.iterator();
while(iter.hasNext()) {
System.out.println(iter.next());
}
}
}
class Dog {
private int size;
public Dog(int size) {
this.size = size;
}
}
我們對dog實現(xiàn)comparable接口就可以
class Dog implements Comparable<Dog>{
private int size;
public Dog(int size) {
this.size = size;
}
@Override
public int compareTo(Dog o) {
return this.size - o.size;
}
public String toString() {
return size + " ";
}
}
下面我們簡單的寫一個小程序測試三個set的效率：
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);
}
