集合:
Vector的方法都是同步的(Synchronized),是線程安全的(thread-safe)，而ArrayList的方法不是，由于線程的同步必然要影響性能，因此,ArrayList的性能比Vector好。
當(dāng)Vector或ArrayList中的元素超過(guò)它的初始大小時(shí),Vector會(huì)將它的容量翻倍,而ArrayList只增加50%的大小，這樣,ArrayList就有利于節(jié)約內(nèi)存空間。
Hashtable和HashMap
它們的性能方面的比較類似 Vector和ArrayList，比如Hashtable的方法是同步的,而HashMap的不是。
ArrayList和LinkedList
對(duì) 于處理一列數(shù)據(jù)項(xiàng),Java提供了兩個(gè)類ArrayList和LinkedList,ArrayList的內(nèi)部實(shí)現(xiàn)是基于內(nèi)部數(shù)組Object[],所以 從概念上講,它更象數(shù)組，但LinkedList的內(nèi)部實(shí)現(xiàn)是基于一組連接的記錄,所以,它更象一個(gè)鏈表結(jié)構(gòu)，所以,它們?cè)谛阅苌嫌泻艽蟮牟顒e。
（1） 從上面的分析可知,在ArrayList的前面或中間插入數(shù)據(jù)時(shí),你必須將其后的所有數(shù)據(jù)相應(yīng)的后移,這樣必然要花費(fèi)較多時(shí)間，所以,當(dāng)你的操作是在一列 數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間,并且需要隨機(jī)地訪問(wèn)其中的元素時(shí),使用ArrayList會(huì)提供比較好的性能。
（2）而訪問(wèn)鏈表中的某個(gè)元素時(shí),就必須從鏈表的一端開(kāi)始沿著連接方向一個(gè)一個(gè)元素地去查找,直到找到所需的元素為止，所以,當(dāng)你的操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù),并且按照順序訪問(wèn)其中的元素時(shí),就應(yīng)該使用LinkedList了。
（3）如果在編程中,1，2兩種情形交替出現(xiàn),這時(shí),你可以考慮使用List這樣的通用接口,而不用關(guān)心具體的實(shí)現(xiàn)，在具體的情形下,它的性能由具體的實(shí)現(xiàn)來(lái)保證。
設(shè)置集合類的初始大小
在Java 集合框架中的大部分類的大小是可以隨著元素個(gè)數(shù)的增加而相應(yīng)的增加的，我們似乎不用關(guān)心它的初始大小,但如果我們考慮類的性能問(wèn)題時(shí),就一定要考慮盡可能 地設(shè)置好集合對(duì)象的初始大小,這將大大提高代碼的性能，比如,Hashtable缺省的初始大小為101,載入因子為0.75,即如果其中的元素個(gè)數(shù)超過(guò) 75個(gè),它就必須增加大小并重新組織元素，所以,如果你知道在創(chuàng)建一個(gè)新的Hashtable對(duì)象時(shí)就知道元素的確切數(shù)目如為110,那么,就應(yīng)將其初始 大小設(shè)為110/0.75=148,這樣,就可以避免重新組織內(nèi)存并增加大小。
特別要理解的：
Hashtable類
Hashtable繼承Map接口，實(shí)現(xiàn)一個(gè)key-value映射的哈希表。任何非空（non-null）的對(duì)象都可作為key或者value。
添加數(shù)據(jù)使用put(key, value)，取出數(shù)據(jù)使用get(key)，這兩個(gè)基本操作的時(shí)間開(kāi)銷為常數(shù)。
Hashtable 通過(guò)initial capacity和load factor兩個(gè)參數(shù)調(diào)整性能。通常缺省的load factor 0.75較好地實(shí)現(xiàn)了時(shí)間和空間的 均衡。增大load factor可以節(jié)省空間但相應(yīng)的查找時(shí)間將增大，這會(huì)影響像get和put這樣的操作。
使用Hashtable的簡(jiǎn)單示例如下，將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));
要取出一個(gè)數(shù)，比如2，用相應(yīng)的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作為key的對(duì)象將通過(guò)計(jì)算其散列函數(shù)來(lái)確定與之對(duì)應(yīng)的value的位置，因此任何作為key的對(duì)象都必須實(shí)現(xiàn)hashCode和equals方 法。hashCode和equals方法繼承自根類Object，如果你用自定義的類當(dāng)作key的話，要相當(dāng)小心，按照散列函數(shù)的定義，如果兩個(gè)對(duì)象相 同，即obj1.equals(obj2)=true，則它們的hashCode必須相同，但如果兩個(gè)對(duì)象不同，則它們的hashCode不一定不同，如 果兩個(gè)不同對(duì)象的hashCode相同，這種現(xiàn)象稱為沖突，沖突會(huì)導(dǎo)致操作哈希表的時(shí)間開(kāi)銷增大，所以盡量定義好的hashCode()方法，能加快哈希 表的操作。
如果相同的對(duì)象有不同的hashCode，對(duì)哈希表的操作會(huì)出現(xiàn)意想不到的結(jié)果（期待的get方法返回null），要避免這種問(wèn)題，只需要牢記一條：要同時(shí)復(fù)寫(xiě)equals方法和hashCode方法，而不要只寫(xiě)其中一個(gè)。
Hashtable是同步的。
HashMap類
HashMap和Hashtable類似，不同之處在于HashMap是非同步的，并且允許null，即null value和null key。，但 是將HashMap視為Collection時(shí)（values()方法可返回Collection），其迭代子操作時(shí)間開(kāi)銷和HashMap的容量成比 例。因此，如果迭代操作的性能相當(dāng)重要的話，不要將HashMap的初始化容量設(shè)得過(guò)高，或者load factor過(guò)低。
LinkedList類
LinkedList實(shí)現(xiàn)了List接口，允許null元素。此外LinkedList提供額外的get，remove，insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack），隊(duì)列（queue）或雙向隊(duì)列（deque）。
注意LinkedList沒(méi)有同步方法。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)List，則必須自己實(shí)現(xiàn)訪問(wèn)同步。一種解決方法是在創(chuàng)建List時(shí)構(gòu)造一個(gè)同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList類
ArrayList實(shí)現(xiàn)了可變大小的數(shù)組。它允許所有元素，包括null。ArrayList沒(méi)有同步。
size，isEmpty，get，set方法運(yùn)行時(shí)間為常數(shù)。但是add方法開(kāi)銷為分?jǐn)偟某?shù)，添加n個(gè)元素需要O(n)的時(shí)間。其他的方法運(yùn)行時(shí)間為線性。
每個(gè)ArrayList實(shí)例都有一個(gè)容量（Capacity），即用于存儲(chǔ)元素的數(shù)組的大小。這個(gè)容量可隨著不斷添加新元素而自動(dòng)增加，但是增長(zhǎng)算法并 沒(méi)有定義。當(dāng)需要插入大量元素時(shí)，在插入前可以調(diào)用ensureCapacity方法來(lái)增加ArrayList的容量以提高插入效率。
和LinkedList一樣，ArrayList也是非同步的（unsynchronized）。
Vector類
Vector非常類似ArrayList，但是Vector是同步的。由Vector創(chuàng)建的Iterator，雖然和ArrayList創(chuàng)建的 Iterator是同一接口，但是，因?yàn)閂ector是同步的，當(dāng)一個(gè)Iterator被創(chuàng)建而且正在被使用，另一個(gè)線程改變了Vector的狀態(tài)（例 如，添加或刪除了一些元素），這時(shí)調(diào)用Iterator的方法時(shí)將拋出ConcurrentModificationException，因此必須捕獲該 異常。
細(xì)說(shuō)Java之util類:
線性表，鏈表，哈希表是常用的數(shù)據(jù)結(jié)構(gòu)，在進(jìn)行Java開(kāi)發(fā)時(shí)，JDK已經(jīng)為我們提供了一系列相應(yīng)的類來(lái)實(shí)現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu)。這些類均在java.util包中。本文試圖通過(guò)簡(jiǎn)單的描述，向讀者闡述各個(gè)類的作用以及如何正確使用這些類。
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
Collection接口
Collection是最基本的集合接口，一個(gè)Collection代表一組Object，即Collection的元素（Elements）。一些 Collection允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接繼承自Collection的類，Java SDK提供的類都是繼承自Collection的“子接口”如List和Set。
所有實(shí)現(xiàn)Collection接口的類都必須提供兩個(gè)標(biāo)準(zhǔn)的 構(gòu)造函數(shù)：無(wú)參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個(gè)空的Collection，有一個(gè)Collection參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個(gè)新的Collection，這 個(gè)新的Collection與傳入的Collection有相同的元素。后一個(gè)構(gòu)造函數(shù)允許用戶復(fù)制一個(gè)Collection。
如何遍歷Collection中的每一個(gè)元素？不論Collection的實(shí)際類型如何，它都支持一個(gè)iterator()的方法，該方法返回一個(gè)迭代子，使用該迭代子即可逐一訪問(wèn)Collection中每一個(gè)元素。典型的用法如下：
Iterator it = collection.iterator(); // 獲得一個(gè)迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一個(gè)元素
}
由Collection接口派生的兩個(gè)接口是List和Set。
List接口
List是有序的Collection，使用此接口能夠精確的控制每個(gè)元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下標(biāo)）來(lái)訪問(wèn)List中的元素，這類似于Java的數(shù)組。
和下面要提到的Set不同，List允許有相同的元素。
除了具有Collection接口必備的iterator()方法外，List還提供一個(gè)listIterator()方法，返回一個(gè) ListIterator接口，和標(biāo)準(zhǔn)的Iterator接口相比，ListIterator多了一些add()之類的方法，允許添加，刪除，設(shè)定元素， 還能向前或向后遍歷。
實(shí)現(xiàn)List接口的常用類有LinkedList，ArrayList，Vector和Stack。
LinkedList類
LinkedList實(shí)現(xiàn)了List接口，允許null元素。此外LinkedList提供額外的get，remove，insert方法在 LinkedList的首部或尾部。這些操作使LinkedList可被用作堆棧（stack），隊(duì)列（queue）或雙向隊(duì)列（deque）。
注意LinkedList沒(méi)有同步方法。如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)List，則必須自己實(shí)現(xiàn)訪問(wèn)同步。一種解決方法是在創(chuàng)建List時(shí)構(gòu)造一個(gè)同步的List：
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList類
ArrayList實(shí)現(xiàn)了可變大小的數(shù)組。它允許所有元素，包括null。ArrayList沒(méi)有同步。
size，isEmpty，get，set方法運(yùn)行時(shí)間為常數(shù)。但是add方法開(kāi)銷為分?jǐn)偟某?shù)，添加n個(gè)元素需要O(n)的時(shí)間。其他的方法運(yùn)行時(shí)間為線性。
每個(gè)ArrayList實(shí)例都有一個(gè)容量（Capacity），即用于存儲(chǔ)元素的數(shù)組的大小。這個(gè)容量可隨著不斷添加新元素而自動(dòng)增加，但是增長(zhǎng)算法并 沒(méi)有定義。當(dāng)需要插入大量元素時(shí)，在插入前可以調(diào)用ensureCapacity方法來(lái)增加ArrayList的容量以提高插入效率。
和LinkedList一樣，ArrayList也是非同步的（unsynchronized）。
Vector類
Vector非常類似ArrayList，但是Vector是同步的。由Vector創(chuàng)建的Iterator，雖然和ArrayList創(chuàng)建的 Iterator是同一接口，但是，因?yàn)閂ector是同步的，當(dāng)一個(gè)Iterator被創(chuàng)建而且正在被使用，另一個(gè)線程改變了Vector的狀態(tài)（例 如，添加或刪除了一些元素），這時(shí)調(diào)用Iterator的方法時(shí)將拋出ConcurrentModificationException，因此必須捕獲該 異常。
Stack 類
Stack繼承自Vector，實(shí)現(xiàn)一個(gè)后進(jìn)先出的堆棧。Stack提供5個(gè)額外的方法使得Vector得以被當(dāng)作堆棧使用?；镜膒ush和pop方 法，還有peek方法得到棧頂?shù)脑?，empty方法測(cè)試堆棧是否為空，search方法檢測(cè)一個(gè)元素在堆棧中的位置。Stack剛創(chuàng)建后是空棧。
Set接口
Set是一種不包含重復(fù)的元素的Collection，即任意的兩個(gè)元素e1和e2都有e1.equals(e2)=false，Set最多有一個(gè)null元素。
很明顯，Set的構(gòu)造函數(shù)有一個(gè)約束條件，傳入的Collection參數(shù)不能包含重復(fù)的元素。
請(qǐng)注意：必須小心操作可變對(duì)象（Mutable Object）。如果一個(gè)Se t中的可變?cè)馗淖兞俗陨頎顟B(tài)導(dǎo)致Object.equals(Object)=true將導(dǎo)致一些問(wèn)題。
Map接口
請(qǐng)注意，Map沒(méi)有繼承Collection接口，Map提供key到value的映射。一個(gè)Map中不能包含相同的key，每個(gè)key只能映射一個(gè) value。Map接口提供3種集合的視圖，Map的內(nèi)容可以被當(dāng)作一組key集合，一組value集合，或者一組key-value映射。
Hashtable類
Hashtable繼承Map接口，實(shí)現(xiàn)一個(gè)key-value映射的哈希表。任何非空（non-null）的對(duì)象都可作為key或者value。
添加數(shù)據(jù)使用put(key, value)，取出數(shù)據(jù)使用get(key)，這兩個(gè)基本操作的時(shí)間開(kāi)銷為常數(shù)。
Hashtable 通過(guò)initial capacity和load factor兩個(gè)參數(shù)調(diào)整性能。通常缺省的load factor 0.75較好地實(shí)現(xiàn)了時(shí)間和空間的均衡。增大load factor可以節(jié)省空間但相應(yīng)的查找時(shí)間將增大，這會(huì)影響像get和put這樣的操作。
使用Hashtable的簡(jiǎn)單示例如下，將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));
要取出一個(gè)數(shù)，比如2，用相應(yīng)的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作為key的對(duì)象將通過(guò)計(jì)算其散列函數(shù)來(lái)確定與之對(duì)應(yīng)的value的位置，因此任何作為key的對(duì)象都必須實(shí)現(xiàn)hashCode和equals方 法。hashCode和equals方法繼承自根類Object，如果你用自定義的類當(dāng)作key的話，要相當(dāng)小心，按照散列函數(shù)的定義，如果兩個(gè)對(duì)象相 同，即obj1.equals(obj2)=true，則它們的hashCode必須相同，但如果兩個(gè)對(duì)象不同，則它們的hashCode不一定不同，如 果兩個(gè)不同對(duì)象的hashCode相同，這種現(xiàn)象稱為沖突，沖突會(huì)導(dǎo)致操作哈希表的時(shí)間開(kāi)銷增大，所以盡量定義好的hashCode()方法，能加快哈希 表的操作。
如果相同的對(duì)象有不同的hashCode，對(duì)哈希表的操作會(huì)出現(xiàn)意想不到的結(jié)果（期待的get方法返回null），要避免這種問(wèn)題，只需要牢記一條：要同時(shí)復(fù)寫(xiě)equals方法和hashCode方法，而不要只寫(xiě)其中一個(gè)。
Hashtable是同步的。
HashMap類
HashMap和Hashtable類似，不同之處在于HashMap是非同步的，并且允許null，即null value和null key。，但是將HashMap視為Collection時(shí)（values()方法可返回Collection），其迭代子操作時(shí)間開(kāi)銷和HashMap 的容量成比例。因此，如果迭代操作的性能相當(dāng)重要的話，不要將HashMap的初始化容量設(shè)得過(guò)高，或者load factor過(guò)低。
WeakHashMap類
WeakHashMap是一種改進(jìn)的HashMap，它對(duì)key實(shí)行“弱引用”，如果一個(gè)key不再被外部所引用，那么該key可以被GC回收。
總結(jié)
如果涉及到堆棧，隊(duì)列等操作，應(yīng)該考慮用List，對(duì)于需要快速插入，刪除元素，應(yīng)該使用LinkedList，如果需要快速隨機(jī)訪問(wèn)元素，應(yīng)該使用ArrayList。
如果程序在單線程環(huán)境中，或者訪問(wèn)僅僅在一個(gè)線程中進(jìn)行，考慮非同步的類，其效率較高，如果多個(gè)線程可能同時(shí)操作一個(gè)類，應(yīng)該使用同步的類。
要特別注意對(duì)哈希表的操作，作為key的對(duì)象要正確復(fù)寫(xiě)equals和hashCode方法。
盡量返回接口而非實(shí)際的類型，如返回List而非ArrayList，這樣如果以后需要將ArrayList換成LinkedList時(shí)，客戶端代碼不用改變。這就是針對(duì)抽象編程。
（參考：Sun JDK1.4.1 API DOC）
練習(xí)使用工具類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));
}
}
練習(xí)使用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.diybl.com/course/3_program/java/javashl/20071129/89461.html)
聯(lián)系客服
