學(xué)習(xí)java數(shù)據(jù)結(jié)構(gòu)的重要性及分類總結(jié)

有一個(gè)問(wèn)題困擾著許多初學(xué)java的新手們，那就是有必要去學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)嗎？雖然你可能沒(méi)有特意去看一些數(shù)據(jù)結(jié)構(gòu)的專業(yè)書(shū)籍，你仍然可以用java做一份還過(guò)得去的工作，不過(guò)并不是說(shuō)你完全沒(méi)有接觸到數(shù)據(jù)結(jié)構(gòu)，因?yàn)閖ava已經(jīng)在底層幫你做了太多，在你和數(shù)據(jù)結(jié)構(gòu)打交道的時(shí)候，你所做更多的是在調(diào)用 API 。當(dāng)你的代碼量累積到一定程度的時(shí)候，就會(huì)想要去加強(qiáng)數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)知識(shí)了。

打個(gè)比方，你可以把java看做是自動(dòng)檔轎車，數(shù)據(jù)結(jié)構(gòu)呢就是變速箱的工作原理。你完全可以不知道變速箱怎樣工作，就把自動(dòng)檔的車子開(kāi)上路，而且未必就比懂得的人慢。寫(xiě)程序這件事，和開(kāi)車一樣，經(jīng)驗(yàn)可以起到很大作用，但如果你不知道底層是怎么工作的，就永遠(yuǎn)只能開(kāi)車，既不會(huì)修車，也不能造車。如果你對(duì)這兩件事都不感興趣也就罷了，數(shù)據(jù)結(jié)構(gòu)懂得用就好。但若你此生在編程領(lǐng)域還有點(diǎn)更高的追求，數(shù)據(jù)結(jié)構(gòu)是繞不開(kāi)的課題。

此外，很重要的一點(diǎn)是，數(shù)據(jù)結(jié)構(gòu)也是通向各種實(shí)用算法的基石，所以學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)都是提升內(nèi)力的事情。這里推薦一本書(shū)《Java數(shù)據(jù)結(jié)構(gòu)和算法》，這本書(shū)以一種易懂的方式教授如何安排和操縱數(shù)據(jù)的問(wèn)題，它使用java語(yǔ)言說(shuō)明重要的概念，而避免了C/C++語(yǔ)言的復(fù)雜性，以便集中精力論述數(shù)據(jù)結(jié)構(gòu)和算法。經(jīng)驗(yàn)豐富的作者RorbertLafore先生提供了許多簡(jiǎn)單明了的例子，避免了對(duì)于這類例題常見(jiàn)的冗長(zhǎng)、繁鎖的數(shù)學(xué)證明。在本書(shū)的每一章后都有問(wèn)題和練習(xí)，使讀者有機(jī)會(huì)測(cè)試自己的理解程度。

java中的數(shù)據(jù)結(jié)構(gòu)總結(jié)

Iterator it = collection.iterator(); // 獲得一個(gè)迭代子  
while(it.hasNext()) {  
Object obj = it.next(); // 得到下一個(gè)元素  
} 

主要方法:

1、boolean add(Object o)添加對(duì)象到集合

2、boolean remove(Object o)刪除指定的對(duì)象

3、int size()返回當(dāng)前集合中元素的數(shù)量

4、boolean contains(Object o)查找集合中是否有指定的對(duì)象

5、boolean isEmpty()判斷集合是否為空

6、Iterator iterator()返回一個(gè)迭代器

7、boolean containsAll(Collection c)查找集合中是否有集合c中的元素

8、boolean addAll(Collection c)將集合c中所有的元素添加給該集合

9、void clear()刪除集合中所有元素

10、void removeAll(Collection c)從集合中刪除c集合中也有的元素

11、void retainAll(Collection c)從集合中刪除集合c中不包含的元素

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。

主要方法:

1、void add(int index,Object element)在指定位置上添加一個(gè)對(duì)象

2、boolean addAll(int index,Collection c)將集合c的元素添加到指定的位置

3、Object get(int index)返回List中指定位置的元素

4、int indexOf(Object o)返回第一個(gè)出現(xiàn)元素o的位置.

5、Object removeint(int index)刪除指定位置的元素

6、Object set(int index,Object element)用元素element取代位置index上的元素,返回被取代的元素

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）。

主要方法:

1、Boolean add(Object o)將指定元素添加到列表的末尾

2、Boolean add(int index,Object element)在列表中指定位置加入指定元素

3、Boolean addAll(Collection c)將指定集合添加到列表末尾

4、Boolean addAll(int index,Collection c)在列表中指定位置加入指定集合

5、Boolean clear()刪除列表中所有元素

6、Boolean clone()返回該列表實(shí)例的一個(gè)拷貝

7、Boolean contains(Object o)判斷列表中是否包含元素

8、Boolean ensureCapacity(int m)增加列表的容量,如果必須,該列表能夠容納m個(gè)元素

9、Object get(int index)返回列表中指定位置的元素

10、Int indexOf(Object elem)在列表中查找指定元素的下標(biāo)

11、Int size()返回當(dāng)前列表的元素個(gè)數(shù)

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ù)脑兀琫mpty方法測(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è)Set中的可變?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映射。

主要方法:

1、boolean equals(Object o)比較對(duì)象

2、boolean remove(Object o)刪除一個(gè)對(duì)象

3、put(Object key,Object 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)); 

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ì)抽象編程。