|
集合:
Vector的方法都是同步的(Synchronized),是線程安全的(thread-safe),，而ArrayList的方法不是,，由于線程的同步必然要影響性能，因此,ArrayList的性能比Vector好,。
當Vector或ArrayList中的元素超過它的初始大小時,Vector會將它的容量翻倍,而ArrayList只增加50%的大小,，這樣,ArrayList就有利于節(jié)約內存空間。
Hashtable和HashMap
它們的性能方面的比較類似 Vector和ArrayList,，比如Hashtable的方法是同步的,而HashMap的不是,。
ArrayList和LinkedList
對 于處理一列數據項,Java提供了兩個類ArrayList和LinkedList,ArrayList的內部實現是基于內部數組Object[],所以 從概念上講,它更象數組，但LinkedList的內部實現是基于一組連接的記錄,所以,它更象一個鏈表結構,，所以,它們在性能上有很大的差別,。
（1） 從上面的分析可知,在ArrayList的前面或中間插入數據時,你必須將其后的所有數據相應的后移,這樣必然要花費較多時間，所以,當你的操作是在一列 數據的后面添加數據而不是在前面或中間,并且需要隨機地訪問其中的元素時,使用ArrayList會提供比較好的性能,。
（2）而訪問鏈表中的某個元素時,就必須從鏈表的一端開始沿著連接方向一個一個元素地去查找,直到找到所需的元素為止,，所以,當你的操作是在一列數據的前面或中間添加或刪除數據,并且按照順序訪問其中的元素時,就應該使用LinkedList了。
（3）如果在編程中,1,，2兩種情形交替出現,這時,你可以考慮使用List這樣的通用接口,而不用關心具體的實現,，在具體的情形下,它的性能由具體的實現來保證,。
設置集合類的初始大小
在Java 集合框架中的大部分類的大小是可以隨著元素個數的增加而相應的增加的，我們似乎不用關心它的初始大小,但如果我們考慮類的性能問題時,就一定要考慮盡可能 地設置好集合對象的初始大小,這將大大提高代碼的性能,，比如,Hashtable缺省的初始大小為101,載入因子為0.75,即如果其中的元素個數超過 75個,它就必須增加大小并重新組織元素,，所以,如果你知道在創(chuàng)建一個新的Hashtable對象時就知道元素的確切數目如為110,那么,就應將其初始 大小設為110/0.75=148,這樣,就可以避免重新組織內存并增加大小。
特別要理解的：
Hashtable類
Hashtable繼承Map接口,，實現一個key-value映射的哈希表,。任何非空（non-null）的對象都可作為key或者value。
添加數據使用put(key, value),，取出數據使用get(key),，這兩個基本操作的時間開銷為常數。
Hashtable 通過initial capacity和load factor兩個參數調整性能,。通常缺省的load factor 0.75較好地實現了時間和空間的 均衡,。增大load factor可以節(jié)省空間但相應的查找時間將增大，這會影響像get和put這樣的操作,。
使用Hashtable的簡單示例如下,，將1，2,，3放到Hashtable中,，他們的key分別是”one”，”two”,，”three”：
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一個數,，比如2，用相應的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作為key的對象將通過計算其散列函數來確定與之對應的value的位置,，因此任何作為key的對象都必須實現hashCode和equals方 法,。hashCode和equals方法繼承自根類Object，如果你用自定義的類當作key的話,，要相當小心,，按照散列函數的定義，如果兩個對象相 同,，即obj1.equals(obj2)=true,，則它們的hashCode必須相同，但如果兩個對象不同,，則它們的hashCode不一定不同,，如 果兩個不同對象的hashCode相同，這種現象稱為沖突,，沖突會導致操作哈希表的時間開銷增大,，所以盡量定義好的hashCode()方法，能加快哈希 表的操作,。
如果相同的對象有不同的hashCode,，對哈希表的操作會出現意想不到的結果（期待的get方法返回null）,，要避免這種問題，只需要牢記一條：要同時復寫equals方法和hashCode方法,，而不要只寫其中一個,。
Hashtable是同步的。
HashMap類
HashMap和Hashtable類似,，不同之處在于HashMap是非同步的,，并且允許null，即null value和null key,。,，但 是將HashMap視為Collection時（values()方法可返回Collection），其迭代子操作時間開銷和HashMap的容量成比 例,。因此,，如果迭代操作的性能相當重要的話，不要將HashMap的初始化容量設得過高,，或者load factor過低,。
LinkedList類
LinkedList實現了List接口，允許null元素,。此外LinkedList提供額外的get,，remove，insert方法在 LinkedList的首部或尾部,。這些操作使LinkedList可被用作堆棧（stack）,，隊列（queue）或雙向隊列（deque）。
注意LinkedList沒有同步方法,。如果多個線程同時訪問一個List,，則必須自己實現訪問同步。一種解決方法是在創(chuàng)建List時構造一個同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList類
ArrayList實現了可變大小的數組,。它允許所有元素，包括null,。ArrayList沒有同步,。
size，isEmpty,，get,，set方法運行時間為常數。但是add方法開銷為分攤的常數,，添加n個元素需要O(n)的時間,。其他的方法運行時間為線性。
每個ArrayList實例都有一個容量（Capacity）,，即用于存儲元素的數組的大小,。這個容量可隨著不斷添加新元素而自動增加,，但是增長算法并 沒有定義。當需要插入大量元素時,，在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率,。
和LinkedList一樣，ArrayList也是非同步的（unsynchronized）,。
Vector類
Vector非常類似ArrayList,，但是Vector是同步的。由Vector創(chuàng)建的Iterator,，雖然和ArrayList創(chuàng)建的 Iterator是同一接口,，但是，因為Vector是同步的,，當一個Iterator被創(chuàng)建而且正在被使用,，另一個線程改變了Vector的狀態(tài)（例 如，添加或刪除了一些元素）,，這時調用Iterator的方法時將拋出ConcurrentModificationException,，因此必須捕獲該 異常。
細說Java之util類:
線性表,，鏈表,，哈希表是常用的數據結構，在進行Java開發(fā)時,，JDK已經為我們提供了一系列相應的類來實現基本的數據結構,。這些類均在java.util包中。本文試圖通過簡單的描述,，向讀者闡述各個類的作用以及如何正確使用這些類,。
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
Collection接口
Collection是最基本的集合接口，一個Collection代表一組Object,，即Collection的元素（Elements）,。一些 Collection允許相同的元素而另一些不行。一些能排序而另一些不行,。Java SDK不提供直接繼承自Collection的類,，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。
所有實現Collection接口的類都必須提供兩個標準的 構造函數：無參數的構造函數用于創(chuàng)建一個空的Collection,，有一個Collection參數的構造函數用于創(chuàng)建一個新的Collection,，這 個新的Collection與傳入的Collection有相同的元素。后一個構造函數允許用戶復制一個Collection,。
如何遍歷Collection中的每一個元素,？不論Collection的實際類型如何，它都支持一個iterator()的方法,，該方法返回一個迭代子,，使用該迭代子即可逐一訪問Collection中每一個元素,。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個元素
}
由Collection接口派生的兩個接口是List和Set。
List接口
List是有序的Collection,，使用此接口能夠精確的控制每個元素插入的位置,。用戶能夠使用索引（元素在List中的位置，類似于數組下標）來訪問List中的元素,，這類似于Java的數組,。
和下面要提到的Set不同，List允許有相同的元素,。
除了具有Collection接口必備的iterator()方法外,，List還提供一個listIterator()方法，返回一個 ListIterator接口,，和標準的Iterator接口相比,，ListIterator多了一些add()之類的方法，允許添加,，刪除,，設定元素， 還能向前或向后遍歷,。
實現List接口的常用類有LinkedList,，ArrayList，Vector和Stack,。
LinkedList類
LinkedList實現了List接口,，允許null元素。此外LinkedList提供額外的get,，remove,，insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack）,，隊列（queue）或雙向隊列（deque）,。
注意LinkedList沒有同步方法。如果多個線程同時訪問一個List,，則必須自己實現訪問同步,。一種解決方法是在創(chuàng)建List時構造一個同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList類
ArrayList實現了可變大小的數組。它允許所有元素,，包括null。ArrayList沒有同步,。
size,，isEmpty，get,，set方法運行時間為常數,。但是add方法開銷為分攤的常數,，添加n個元素需要O(n)的時間。其他的方法運行時間為線性,。
每個ArrayList實例都有一個容量（Capacity）,，即用于存儲元素的數組的大小。這個容量可隨著不斷添加新元素而自動增加,，但是增長算法并 沒有定義,。當需要插入大量元素時，在插入前可以調用ensureCapacity方法來增加ArrayList的容量以提高插入效率,。
和LinkedList一樣,，ArrayList也是非同步的（unsynchronized）。
Vector類
Vector非常類似ArrayList,，但是Vector是同步的,。由Vector創(chuàng)建的Iterator，雖然和ArrayList創(chuàng)建的 Iterator是同一接口,，但是,，因為Vector是同步的，當一個Iterator被創(chuàng)建而且正在被使用,，另一個線程改變了Vector的狀態(tài)（例 如,，添加或刪除了一些元素），這時調用Iterator的方法時將拋出ConcurrentModificationException,，因此必須捕獲該 異常,。
Stack 類
Stack繼承自Vector，實現一個后進先出的堆棧,。Stack提供5個額外的方法使得Vector得以被當作堆棧使用,。基本的push和pop方 法,，還有peek方法得到棧頂的元素,，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置,。Stack剛創(chuàng)建后是空棧,。
Set接口
Set是一種不包含重復的元素的Collection，即任意的兩個元素e1和e2都有e1.equals(e2)=false,，Set最多有一個null元素,。
很明顯，Set的構造函數有一個約束條件,，傳入的Collection參數不能包含重復的元素,。
請注意：必須小心操作可變對象（Mutable Object）。如果一個Se t中的可變元素改變了自身狀態(tài)導致Object.equals(Object)=true將導致一些問題。
Map接口
請注意,，Map沒有繼承Collection接口,，Map提供key到value的映射。一個Map中不能包含相同的key,，每個key只能映射一個 value,。Map接口提供3種集合的視圖，Map的內容可以被當作一組key集合,，一組value集合,，或者一組key-value映射。
Hashtable類
Hashtable繼承Map接口,，實現一個key-value映射的哈希表,。任何非空（non-null）的對象都可作為key或者value。
添加數據使用put(key, value),，取出數據使用get(key),，這兩個基本操作的時間開銷為常數。
Hashtable 通過initial capacity和load factor兩個參數調整性能,。通常缺省的load factor 0.75較好地實現了時間和空間的均衡,。增大load factor可以節(jié)省空間但相應的查找時間將增大，這會影響像get和put這樣的操作,。
使用Hashtable的簡單示例如下,，將1，2,，3放到Hashtable中,，他們的key分別是”one”，”two”,，”three”：
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
要取出一個數,，比如2，用相應的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作為key的對象將通過計算其散列函數來確定與之對應的value的位置,，因此任何作為key的對象都必須實現hashCode和equals方 法,。hashCode和equals方法繼承自根類Object，如果你用自定義的類當作key的話,，要相當小心,，按照散列函數的定義，如果兩個對象相 同,，即obj1.equals(obj2)=true,，則它們的hashCode必須相同，但如果兩個對象不同,，則它們的hashCode不一定不同,，如 果兩個不同對象的hashCode相同，這種現象稱為沖突，沖突會導致操作哈希表的時間開銷增大,，所以盡量定義好的hashCode()方法，能加快哈希 表的操作,。
如果相同的對象有不同的hashCode,，對哈希表的操作會出現意想不到的結果（期待的get方法返回null），要避免這種問題,，只需要牢記一條：要同時復寫equals方法和hashCode方法,，而不要只寫其中一個。
Hashtable是同步的,。
HashMap類
HashMap和Hashtable類似,，不同之處在于HashMap是非同步的，并且允許null,，即null value和null key,。，但是將HashMap視為Collection時（values()方法可返回Collection）,，其迭代子操作時間開銷和HashMap 的容量成比例,。因此，如果迭代操作的性能相當重要的話,，不要將HashMap的初始化容量設得過高,，或者load factor過低。
WeakHashMap類
WeakHashMap是一種改進的HashMap,，它對key實行“弱引用”,，如果一個key不再被外部所引用，那么該key可以被GC回收,。
總結
如果涉及到堆棧,，隊列等操作，應該考慮用List,，對于需要快速插入,，刪除元素，應該使用LinkedList,，如果需要快速隨機訪問元素,，應該使用ArrayList。
如果程序在單線程環(huán)境中,，或者訪問僅僅在一個線程中進行,，考慮非同步的類，其效率較高,，如果多個線程可能同時操作一個類,，應該使用同步的類。
要特別注意對哈希表的操作，作為key的對象要正確復寫equals和hashCode方法,。
盡量返回接口而非實際的類型,，如返回List而非ArrayList，這樣如果以后需要將ArrayList換成LinkedList時,，客戶端代碼不用改變,。這就是針對抽象編程。
（參考：Sun JDK1.4.1 API DOC）
練習使用工具類Collections:
import java.util.*;
public class TestCollections{
public static void main(String[] args)
{
CollcetionsTest ct=new CollcetionsTest();
ct.printMap();
}
}
class CollcetionsTest{
HashMap hash=new HashMap();
public void printMap()
{
hash.put("1","value1");
hash.put("2","value2");
hash.put("3","value3");
hash.put("4","value4");
List valueList=new ArrayList(hash.values());
for(int i=0;i<valueList.size();i++)
{
String temp=(String)valueList.get(i);
System.out.println("value"+i+"="+temp); //the sequence is not sure
}
/*wrong useage coz list for binarySearch must be sorted(ascending or descending) first*/
int targetPosition=Collections.binarySearch(valueList,"value3");
System.out.println("$$$$$$position of value3="+targetPosition);
targetPosition=Collections.binarySearch(valueList,"value1");
System.out.println("$$$$$$position of value1="+targetPosition);
/* wrong usage*/
ArrayList testList=(ArrayList)valueList;
for(int i=0;i<testList.size();i++)
{
String temp=(String)testList.get(i);
System.out.println("********testList value"+i+"="+temp); //the sequence is not sure
}
Collections.sort(valueList);
for(int i=0;i<valueList.size();i++)
{
String temp=(String)valueList.get(i);; System.out.println("^^^^^value"+i+"="+temp); //the sequence is not sure
}
System.out.println("maxvalue"+"="+Collections.max(valueList));
System.out.println("minvalue"+"="+Collections.min(valueList));
Set set=hash.keySet();
System.out.println("set size="+set.size());
System.out.println("maxvalue"+"="+Collections.max(set));
System.out.println("minvalue"+"="+Collections.min(set));
targetPosition=Collections.binarySearch(valueList,"value3");
System.out.println("$$$$$$position of value3="+targetPosition);
targetPosition=Collections.binarySearch(valueList,"value1");
System.out.println("$$$$$$position of value1="+targetPosition);
HashMap hash0=new HashMap();
Set set0=hash0.keySet();
System.out.println("^^^^^^^^^set0="+set0.size());
if(!set0.isEmpty()){
int maxKey = ((Integer) Collections.max(set0)).intValue();
}
System.out.println("set0="+set0+"=========="+hash0.keySet());//This means: even if
//there is no value in hash0, hash0.keySet() will not return "null" ,
//that means set0 is not null, though set0 has no value.
//At this time , set0.isEmpty==true while set0.size()==0.
HashSet hset=new HashSet(set);
System.out.println("~~~hset size="+hset.size());
System.out.println("~~~hset maxvalue"+"="+Collections.max(hset));
System.out.println("~~~hset minvalue"+"="+Collections.min(hset));
}
}
練習使用HashMap:
import java.util.*;
public class TestHashmap{
public static void main(String[] args)
{
MapTest map=new MapTest();
map.printMap();
}
}
class MapTest{
HashMap hash=new HashMap();
public void printMap()
{
hash.put("1","value2");
hash.put("2",null);
hash.put("3","value3");
hash.put("4","value4");
String value=(String)hash.get("3");
System.out.println("key 3<===>"+value);
Set set=hash.keySet();
System.out.println("set size="+set.size());
Iterator it=set.iterator();
while(it.hasNext())
{
String temp2=(String)it.next();
System.out.println("keys contained:"+temp2);
}
Collection valuesList=hash.values();//no exception will be reported if collection
//has null values; instead, the null value will be printed as "null" if iterated.
& nbsp; System.out.println("valuesList size="+valuesList.size());
Iterator it2=valuesList.iterator();
while(it2.hasNext())
{
String temp2=(String)it2.next();
System.out.println("values contained:"+temp2);
}
List valueList=new ArrayList(hash.values());
for(int i=0;i<valueList.size();i++)
{
String temp=(String)valueList.get(i);
System.out.println("value"+i+"="+temp); //the sequence is not sure
//can not make sure that the values are displayed according to the input order
}
}
}
文章出處：DIY部落(http://www./course/3_program/java/javashl/20071129/89461.html)
|
