【总结】Java基础之Set：HashSet vs. LinkedHashSet vs. TreeSet

总结平时常用的Collection子接口：Set接口以及其实现类。

Set接口，它和List很像，主要区别是其所有的元素都是不可复重的。List是有序的集合，而Set的排序得看其具体的实现，比如HashSet是无序的，而LinkedHashSet和TreeSet就是有序的。
另外，Set如果要存null元素，那也只能存一个。（去重性）

Set和List的区别表：

	Set	List
元素重复	不可以重复	可以重复
排序	不一定有序：得看具体的实现	有序
按索引取元素，即get(int index)	不可以	可以

注：Set是不能按索引取元素的，原因就是因为Set是无序的。

类图如下：


Set的底层实现比较简单，是基于Map实现的，相当于是Map的Key，以下是实现对应表：

Set	Map
HashSet	HashMap
LinkedHashSet	LinkedHashMap
TreeSet	TreeMap

Set默认都是线程不安全的，想要返回一个线程安全的对象，使用以下方法：

Set s = Collections.synchronizedSet(new HashSet(...));
Set s = Collections.synchronizedSet(new LinkedHashSet(...));
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

1、HashSet
HashSet是常用的Set接口的实现之一。
对于HashSet而言，它是基于HashMap实现的，相当于是HashMap的key。

值得注意的是，对于方法boolean contains(Object o)，HashSe的时间复杂度是O(1)，而ArrayList的contains方法的时间复杂度是O(n)。
所以在List集合的选用上，如果不在意重复的元素以及contain方法的效率，那就用ArrayList，返之就用HashSet。

以下是个人实验：

public void containsPerformanceTest() {
	Set<String> set = new HashSet<String>();
	List<String> list = new ArrayList<String>();
		
	for (int i = 0; i < 1000000; i ++) {
		set.add(i + "");
		list.add(i + "");
	}
		
	long st = System.currentTimeMillis();
	if (set.contains("999799")) {
		System.out.println("set contains method cost: " + (System.currentTimeMillis() - st) + " ms");
		// set contains method cost: 0 ms
	}
		
	long st1 = System.currentTimeMillis();
	if (list.contains("999799")) {
		System.out.println("list contains method cost: " + (System.currentTimeMillis() - st1) + " ms");
		// list contains method cost: 18 ms
	}
}

2、LinkedHashSet
和HashSet不同的是，LinkedHashSet是双向链表的list。其排序是按加入的元素排的（迭代器顺序）。
LinkedHashSet基于LinkedHashMap实现的，相当于是LinkedHashMap的key。和LinkedHashMap一样，是JDK1.4开始的。

3、TreeSet
TreeSet是SortedSet的一个实现，是个有序的Set。它的其中一个构造函数，可以传入Comparator类，返回一个按自定义排序器排序的Set。

TreeSet(Comparator<? super E> comparator) 

-------------------------------------------
参考：
http://docs.oracle.com/javase/6/docs/api/java/util/Set.html
http://stackoverflow.com/questions/769731/why-doesnt-java-util-set-have-getint-index