JAVA數據結構
線性表，鏈表，哈希表是常用的數據結構，在進行
Java
開發時，
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
接口的類都必須提供兩個標準的構造函數：無參數的構造函數用于創建一個空的
Collection
，有一個
Collection
參數的構造函數用于創建一個新的
Collection
，這個新的
Collection
與傳入的
Collection
有相同的元素。后一個構造函數允許用戶復制一個
Collection
。
如何遍歷
Collection
中的每一個元素？不論
Collection
的實際類型如何，它都支持一個
iterator()
的方法，該方法返回一個迭代子，使用該迭代子即可逐一訪問
Collection
中每一個元素。典型的用法如下：
Iterator it = collection.iterator(); //
獲得一個迭代子
while(it.hasNext()) {
Object obj = it.next(); //
得到下一個元素
}
由
Collection
接口派生的兩個接口是
List
和
Set
。
主要方法:
boolean add(Object o)
添加對象到集合
boolean remove(Object o)
刪除指定的對象
int size()
返回當前集合中元素的數量
boolean contains(Object o)
查找集合中是否有指定的對象
boolean isEmpty()
判斷集合是否為空
Iterator iterator()
返回一個迭代器
boolean containsAll(Collection c)查找集合中是否有集合c中的元素
boolean addAll(Collection c)將集合c中所有的元素添加給該集合
void clear()刪除集合中所有元素
void removeAll(Collection c)從集合中刪除c集合中也有的元素
void retainAll(Collection c)從集合中刪除集合c中不包含的元素
?
List
接口
List
是有序的
Collection
，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在
List
中的位置，類似于數組下標）來訪問
List
中的元素，這類似于
Java
的數組。
和下面要提到的
Set
不同，
List
允許有相同的元素。
除了具有
Collection
接口必備的
iterator()
方法外，
List
還提供一個
listIterator()
方法，返回一個
ListIterator
接口，和標準的
Iterator
接口相比，
ListIterator
多了一些
add()
之類的方法，允許添加，刪除，設定元素，還能向前或向后遍歷。
實現
List
接口的常用類有
LinkedList
，
ArrayList
，
Vector
和
Stack
。
主要方法:
void add(int index,Object element)在指定位置上添加一個對象
boolean addAll(int index,Collection c)將集合c的元素添加到指定的位置
Object get(int index)返回List中指定位置的元素
int indexOf(Object o)返回第一個出現元素o的位置.
Object removeint(int index)刪除指定位置的元素
Object set(int index,Object element)用元???????Object set(int index,Object element)用元素element取代位置index上的元素,返回被取代的元素?
?
LinkedList
類
LinkedList
實現了
List
接口，允許
null
元素。此外
LinkedList
提供額外的
get
，
remove
，
insert
方法在
LinkedList
的首部或尾部。這些操作使
LinkedList
可被用作堆棧（
stack
），隊列（
queue
）或雙向隊列（
deque
）。
注意
LinkedList
沒有同步方法。如果多個線程同時訪問一個
List
，則必須自己實現訪問同步。一種解決方法是在創建
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
）。
主要方法:
Boolean add(Object o)將指定元素添加到列表的末尾
Boolean add(int index,Object element)在列表中指定位置加入指定元素
Boolean addAll(Collection c)將指定集合添加到列表末尾
Boolean addAll(int index,Collection c)在列表中指定位置加入指定集合
Boolean clear()刪除列表中所有元素
Boolean clone()返回該列表實例的一個拷貝
Boolean contains(Object o)判斷列表中是否包含元素
Boolean ensureCapacity(int m)增加列表的容量,如果必須,該列表能夠容納m個元素
Object get(int index)返回列表中指定位置的元素
Int indexOf(Object elem)在列表中查找指定元素的下標
Int size()返回當前列表的元素個數
?
Vector
類
Vector
非常類似
ArrayList
，但是
Vector
是同步的。由
Vector
創建的
Iterator
，雖然和
ArrayList
創建的
Iterator
是同一接口，但是，因為
Vector
是同步的，當一個
Iterator
被創建而且正在被使用，另一個線程改變了
Vector
的狀態（例如，添加或刪除了一些元素），這時調用
Iterator
的方法時將拋出
ConcurrentModificationException
，因此必須捕獲該異常。
?
Stack
類
Stack
繼承自
Vector
，實現一個后進先出的堆棧。
Stack
提供
5
個額外的方法使得
Vector
得以被當作堆棧使用。基本的
push
和
pop
方法，還有
peek
方法得到棧頂的元素，
empty
方法測試堆棧是否為空，
search
方法檢測一個元素在堆棧中的位置。
Stack
剛創建后是空棧。
?
Set
接口
Set
是一種不包含重復的元素的
Collection
，即任意的兩個元素
e1
和
e2
都有
e1.equals(e2)=false
，
Set
最多有一個
null
元素。
很明顯，
Set
的構造函數有一個約束條件，傳入的
Collection
參數不能包含重復的元素。
請注意：必須小心操作可變對象（
Mutable Object
）。如果一個
Set
中的可變元素改變了自身狀態導致
Object.equals(Object)=true
將導致一些問題。
?
Map
接口
請注意，
Map
沒有繼承
Collection
接口，
Map
提供
key
到
value
的映射。一個
Map
中不能包含相同的
key
，每個
key
只能映射一個
value
。
Map
接口提供
3
種集合的視圖，
Map
的
內容可以被當作一組key集合，一組value集合，或者一組key-value映射。
主要方法:
boolean equals(Object o)比較對象
boolean remove(Object o)刪除一個對象
put(Object key,Object 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
可以節省空間但相應的查找時間將增大，這會影響像
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
。
如果程序在單線程環境中，或者訪問僅僅在一個線程中進行，考慮非同步的類，其效率較高，如果多個線程可能同時操作一個類，應該使用同步的類。
要特別注意對哈希表的操作，作為
key
的對象要正確復寫
equals
和
hashCode
方法。
盡量返回接口而非實際的類型，如返回
List
而非
ArrayList
，這樣如果以后需要將
ArrayList
換成
LinkedList
時，客戶端代碼不用改變。這就是針對抽象編程。