關于JAVA集合的那點事

（一） Vector   ArrayList   LinkedList

Vestor,ArrayList,LinkedList這三個類都實作了java.util.List接口；

Vector和ArrayList使用Objec的數組形式來存儲,可直接按序号索引元素，故搜尋速度較快，但在數組中間插入新元素時要設計數組元素的記憶體移動，導緻速度較慢；

LinkedList則是采用了雙向連結清單的存儲方式，插入新元素時隻要指定該元素的前後項即可，速度較快，但是搜尋時要向前或向後周遊，速度較慢

Vector是線程安全的，他的很多方法都實作了線程同步（synchronized），但是性能上來講，Vector會低于ArrayList

（二）HashSet

HashSet 是 Set 接口的常用實作類，構造函數如下：

 public HashSet() {

       map = new HashMap<E,Object>();

 }

從構造函數我們可以看出，實際上HashSet是通過HashMap來實作的，是以HashSet也是采用Hash存儲機制進行資料的存儲。

我們都知道HashSet不允許插入重複的值或對象，但是對于兩個内容相同的對象呢？

運作下面的代碼我便能知曉一二：

public class Test {
	//定義一個内部類
	private static class Demo{
		private int value;
		public Demo(int value){
			this.value=value;
		}		
		//重寫toString方法，便于列印輸出
		public String toString(){
			return ("value="+value);
		}
		//重寫equals方法
		 public boolean equals(Object o) {
	             Demo demo = (Demo) o;
	             return (demo.value == value) ? true : false;
	     }
		 //重寫hashCode方法
		 public int hashCode(){
			 return value;
		 }
	}
	
	public static void main(String[] args) {
		HashSet<Demo> set=new HashSet<Demo>();
		set.add(new Demo(1));
		System.out.println(set);
		set.add(new Demo(1));
		System.out.println(set);
	}	
}
           

運作結果為：

[value=1]

[value=1]

但是當我們把Demo的equals方法或hashCode方法注釋掉一個或者全部注釋掉時我們會發現運作結果變為：

[value=1]

[value=1, value=1]

如果不重寫對象的hashCode方法和equals方法的情況下，HashSet依舊會将内容相同的兩個對象一起存入

那麼為什麼會如此呢？

由于HashSet是依靠HashMap實作的，是以要解答這個問題我們必須搞清楚HashMap内部的存儲機制

通過另一篇文章——深入講解HashMap，我們可以發現，鍵值對在存入HashMap中定義的entry數組時，會先根據鍵（key）對象的hashCode計算出要存儲在數組的那個下标值下，然後在周遊該下标值的entry鍊，如果找到了key與要插入的key相同的entry對象則替換該對象的值，否則，則将此新鍵值對插入到該entry鍊的頭部；

而對于HashSet<E>事實上就相當于HashMap<E,Object>

如果不重寫hashCode方法，那麼我們知道Object預設的hashCode傳回的是一個與記憶體位址相關的數值，兩個不同對象的hashCode傳回值一般是不相同的（當然也有很小的幾率相同），哪怕是這兩個對象的内容完全一緻，是以在插入entry數組的時候，這兩個對象存儲的下标值也有很大的機率不在同一個下标值内，自然就兩個對象都會被存儲在entry數組中；

那麼即使我們重寫了hashCode也還是不夠，因為在entry鍊中，會根據對象的equals方法判斷新添加進來的key時候已經存在，我們知道Object預設的equals方法傳回的是該對象的記憶體位址，自然的，兩個不同對象用equals進行比較時傳回的就是false，也就是此時這兩個對象都會被存儲再同一個entry鍊中。

明白了上面的機制後，我們可以看出，如果我們要實作在HashSet（或者是HashMap的key）中不會被插入内容相同的對象時，我們就必須重寫要插入的對象的hashCode和equals方法，而且這兩個方法要根據該對象的内容來重寫，確定兩個内容相同的對象的hashCode傳回值相同，并使用equals比較時傳回true

（三）TreeSet  TreeMap  HashSet  HashMap

TreeMap它内部是一個樹形結構存儲結構，使用二叉樹對資料進行存儲；

TreeMap是有序的,自然要求元素是可以比較大小的,如果構造函數指定Comparator的話,就使用這個Comparator比較大小

如果沒有指定Comparator的話,就使用自然排序(元素要實作Comparable接口).

二叉樹,一般查找時間複雜度為 o(lg(n)),這個效率當然沒有HashMap的效率高是以除法是有排序的需求，不然一般都使用HashMap

TreeSet與TreeMap的關系就和HashSet與HashMap的關系一樣

由于TreeSet  TreeMap  用的比較少，是以也未作深入的了解，具體以後有需要再進一步分析

（四）HashMap  Hashtalbe

Hashtable是繼承與Dictionary類，HashMap是Map接口的一個實作（事實上，Hashtable也實作了Map接口）；

Hashtable是線程安全，HashMap是Hashtable的輕量級實作（非線程安全實作），是以HashMap的效率會高于Hashtable

HashMap允許将null作為一個entry的key或者value，而Hashtable不允許。

（五）關于集合的周遊 

package com;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;


public class 容器類的周遊 {
	
	//有序的集合：數組和arraylist的周遊，可通過下标值實作
	 public void bianliArray(String[] a){
		 for(int i=0;i<a.length;i++){
			 System.out.println(i);
		 }
	 }
	 
	 public void bianliArraylist(ArrayList<String> a){
		 for(int i=0;i<a.size();i++){
			 System.out.println(a.get(i));
		 }
	 }
	 
	 //Collection接口定義了一個iterator()方法，該方法傳回一個實作了Iterator接口對象（疊代器），然後再使用疊代器進行疊代周遊	 
	 public void bianliCollection(Collection<String> c){
		 Iterator<String> iterator=c.iterator();
		 while(iterator.hasNext()){
			 System.out.println(iterator.next());
			 /*
			  * 補充： 值得注意的是，當要在疊代過程中删除某個元素，則必須要用該疊代器的remove方法
			  * 而不能使用collection自生的remove方法，這是因為集合進行進入疊代器時會被疊代器鎖定，
			  * 疊代過程隻有疊代器能對此集合進行操作
			  */
		 }	 
	 }
	 
     //java5之後支援了另一種 周遊方式：foreach方式，這種方式的編寫格式簡單整潔，但是隻能用于隻讀的情況，
	 //因為該方法不能對周遊的元素進行修改和删除操作,分析下面的方法的結果可以發現集合中的字元串沒被修改過
	 public void bianliForeach(Collection<String> c){
		 for(String s: c){
			 System.out.println(s);
			 s="被修改過了";
		 }
		 for(String s: c){
			 System.out.println(s);
		 }
	 }
	 //但是分析下面這個程式可以發現集合中的u對象卻是被修改了，從中可以看出什麼麼？。。。。
	 public void bianliForeach1(Collection<User> c){
		 for(User u: c){
			 System.out.println(u.getName());
			 u.setName("被修改過了");
		 }
		 for(User u: c){
			 System.out.println(u.getName());
		 }
	 }
	 
	 /*
	  * 對于map的周遊，由于Map接口沒有定義和collection一樣的iterator方法
	  * 不過在Map中定義裡entrySet和ketSet方法
	  *   entrySet()傳回此映射中包含的映射關系的 Set視圖，
	  *   keySet() 傳回此映射中包含的鍵的 Set 視圖。
	  *   然後在通過set視圖的iterator方法
	 */
	 
	 //用entrySet實作Map的周遊，效率較高
	 public  void entrySetOfMap(Map<String, String>  m){
		 Iterator iterator=m.entrySet().iterator();
		 while(iterator.hasNext()){
			 Map.Entry<String, String> entry=(Map.Entry<String, String>)iterator.next();//Map.Entry鍵值對映射項
			 System.out.println("key="+entry.getKey());
			 System.out.println("value="+entry.getValue());
		 }
	 }
	 
	 //用keySet實作Map的周遊，周遊出key之後還要去map查找對應的value，效率較低
	 public void keySetOfMap(Map<String, String> m){
		 Iterator iterator=m.keySet().iterator();
		 while(iterator.hasNext()){
			 Object key=iterator.next();
			 String value=(String)m.get(key);
			 System.out.println("key="+key);
			 System.out.println("value="+value);
		 }
	 }
	 

}