3. List
List是一種有順序的Collection，并允許有重復的元素。除了從Colleciton接口繼承過來的方法之外，List還額外增加了如下一些操作：
Positional access — manipulates elements based on their
numerical position in the list
Search — searches for a specified object in the list and
returns its numerical position
Iteration — extends Iterator semantics to take
advantage of the list's sequential nature
Range-view — performs arbitrary range operations on the
list.
List接口定義如下：
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,
Collection<? extends E> c); //optional
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Range-view
List<E> subList(int from, int to);
}
Java platform提供了兩種general-purpose的List實現類：
·ArrayList：性能最好，相當于可變長度的數組
·LinkedList：適合于插入刪除操作。
關于從Collection繼承過來的操作，有幾點需要注意：
·boolean remove(Object element); 是刪除在List中
第一個出現的element（因為List允許重復元素）
·add和addAll操作，是把元素加入到當前List的隊尾
和Set一樣的是，List也增強了對equals和hashCode操作的約束，任意兩個List的實現類，都可以進行比較，只要他們包含的元素相同，那么equals就返回true
由于List是有順序的，我們可以根據元素的位置來進行操作。比如下面的例子演示了如何交換兩個不同位置的元素：
public static <E> void swap(List<E> a, int i, int j) {
E tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
有了這個函數，我們就可以很容易的得到Collections類中的shuffle方法：
public static void shuffle(List<?> list, Random rnd) {
for (int i = list.size(); i > 1; i--)
swap(list, i - 1, rnd.nextInt(i));
}
既然提到了shuufle，那么來看一下他的一個簡單應用：將傳進來的參數打亂順序
public class Shuffle {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
for (String a : args)
list.add(a);
Colle?ions.shuffle(list, new Random());
System.out.println(list);
}
}
而實際上，我們可以用更簡潔的代碼來完成上面的功能，那就是利用Array的asList方法。
我們前面提到過，List可以看作是可變長度的Array，反過來，我們也可以把Array看成是一種特殊的list。因此，java platform就提供了將ArrayC?%8?換成List的方法asList。但要注意的是，asList方法返回的是一個List，而不是任何一種general-purpose的實現類。因為他返回的這個list并不實現add、remove方法－只能看，不能動。
public class Shuffle {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.shuffle(list);
System.out.println(list);
}
}
List不光實現了Iterator，他還根據自己有序的特性，實現了一種特殊的Iterator－ListIterator：
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove(); //optional
void set(E e); //optional
void add(E e); //optional
}
我們看到，ListIterator能自由的控制遍歷的方向，而且能隨時得到當前所處的位置，另外，也能在遍歷期間進行各種修改操作（add、set、remove）。
還有一點：Iterator只能刪除，不能修改（add、set），而ListIterator可以
為了對比，我還是把原本的Iterator貼出來：
public interface Iterator<E> {
boolean hasNext();
E next();
void remove(); //optional
}
ListIterator不僅僅是擴展了這些方法，連構造方法都多了一個：
除了普通的ListIterator<E> listIterator();
外，還可以用ListIterator<E> listIterator(int index);來獲得指定位置處的listIterator。這樣我們就可以從任意位置，朝任意方向開始遍歷了。
下面關于List中的subList方法，有一點需要注意，那就是subList返回的是一個引用，而不是新創建的List。這就意味這你對subList做的任何操作，都將影響到原來的list（我們稱其為backlist）。因此，subList只能用于臨時的對backlist的局部操作，而且要盡早結束，避免由于其他地方對backlist的修改導致subList出現問題。當然，有一種這種的辦法，就是你根據返回的subList，創建一個新的list。
在Collections類中定義了很多算法，適用于List：
sort — sorts a List using a merge sort algorithm,
which provides a fast, stable sort. (A stable sort is one that does not
reorder equal elements.)
shuffle — randomly permutes the elements in a
List.
reverse — reverses the order of the elements in a
List.
rotate — rotates all the elements in a List by a
specified distance.
swap — swaps the elements at specified positions in a
List.
replaceAll — replaces all occurrences of one specified value
with another.
fill — overwrites every element in a List with the
specified value.
copy — copies the source List into the destination
List.
binarySearch — searches for an element in an ordered
List using the binary search algorithm.
indexOfSubList — returns the index of the first sublist of one
List that is equal to another.
lastIndexOfSubList — returns the index of the last sublist of
one List that is equal to another.
具體內容將在介紹算法時再繼續深入
4. Queue
Queue就是數據結構中介紹的隊列。除了Collection中提供的基本操作外，他還額外提供了一些關于插入、刪除、檢查的操作。
Queue的定義如下：
public interface Queue<E> extends Collection<E> {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
Queue有一個特點，就是它所提供的方法都有兩種形態：
·失敗時拋異常的
·失敗時返回特殊值的（null或者false）
Queue Interface Structure
| |
Throws exception |
Returns special value |
| Insert |
add(e) |
offer(e) |
| Remove |
remove() |
poll() |
| Examine |
element() |
peek() |
前面提到過，Queue是有順序的Collection，而且一般的Queue都遵?%???FIFO，就像數據結構里介紹的那樣。但也有例外，比如priority queue，可以定義自己的排序方式。但不管順序是怎樣的，排在頭部的都是將要被remove()或者poll()方法拿出來的那個元素。而當插入的時候，FIFO的queue當然是插入隊尾，但其他形式的queue則由自身的排序規則決定插入位置
有些queue是由長度限制的，被稱為“bounded queue”，像在java.util.concurrent中實現的一些queue就是bounded，但java.uti8B?%8?的所有queue都是沒有長度限制的。
·add(e)方法當超過queue的長度限制的時候，就將拋出
IllegalStateException；而offer(e)方法是被設計專門用在bounded queue上的，當超過隊列限制時，該方法將返回false
·當隊列為空時，調用remove()方法將拋NoSuchElementException；poll()方法將返回null
·element()和peek()方法和remove()、poll()基本是一樣的，唯一的區別是他們只是取得頭部元素的值，而并不刪除
需要注意的一點是：Queue 實現通常不允許插入
null 元素，盡管某些實現（如
LinkedList）并不禁止插入
null。即使在允許 null 的實現中，也不應該將
null 插入到
Queue 中，因為
null 也用作
poll 方法的一個特殊返回值，表明隊列不包含元素。
與Set和List不同的是，
Queue 實現通常未定義
equals 和
hashCode 方法的基于元素的版本，而是從
Object 類繼承了基于身份的版本，因為對于具有相同元素但有不同排序屬性的隊列而言，基于元素的相等性并非總是定義良好的。
另外，
Queue 接口并未定義
阻塞隊列的方法，而這在并發編程中是很常見的。
java.util.cuncurrent.BlockingQueue
接口定義了那些等待元素出現或等待隊列中有可用空間的方法，這些方法擴展了此接口。
5. Map
Map存儲的是“鍵－值”對，他不允許key重復，每個key最多指向一個value。
下面是Map的定義：
public interface Map<K,V> {
// Basic operations
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();
// Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();
// Interface for entrySet elements
public interface Entry {
K getKey();
V getValue();
V setValue(V value);
}
}
Java platform提供了三種general purpose的Map實現類：HashMap、TreeMap、LinkedHashMap，他們很類似于Set中的HashSet、TreeSet、LinkedHashSet。如果你忘了這三者的區別，那就看下面一個簡單的例子：
public class Freq {
public static void main(String[] args) {
Map<String, Integer> m = new HashMap<String, Integer>();
// Initialize frequency table from command line
for (String a : args) {
Integer freq = m.get(a);
m.put(a, (freq == null) ? 1 : freq + 1);
}
System.out.println(m.size() + " distinct words:");
System.out.println(m);
}
}
運行：
java Freq if it is to be it is up to me to delegate
返回的結果是：
8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}
如果我們將HashMap換成TreeMap，那么將按字母順序輸出：
8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}
如果換成LinkedHashMap，那么將按插入順序輸出：
8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}
和Collecton一樣，所有通用的Map實現類應該提供兩個“標準的”構造方法：一個 void（無參數）構造方法，用于創建空映射；一個是帶有單個
Map
類型參數的構造方法，用于創建一個與其參數具有相同鍵-值映射關系的新映射。實際上，后一個構造方法允許用戶復制任意映射，生成所需類的一個等價映射。盡管無法強制執行此建議（因為接口不能包含構造方法），但是
JDK 中所有通用的Map實現都遵從它。
和Set、List一樣，Map增強了equals和hashCode方法的約束，任意兩個Map的實現類的對象都可以進行比較，只要二者所包含的鍵值對完全相同，那二者就是相等的。
Map 接口提供三種
collection
視圖，允許以鍵集、值集或鍵-值映射關系集的形式查看某個映射的內容。映射
順序 定義為迭代器在映射的 collection
視圖上返回其元素的順序。某些映射實現可明確保證其順序，如
TreeMap 類；另一些映射實現則不保證順序，如
HashMap
類。
keySet — the Set of keys contained in the
Map.
values — The Collection of values contained in the
Map. This Collection is not a Set,
because multiple keys can map to the same value.
entrySet — the Set of key-value pairs contained in
the Map. The Map interface provides a small nested
interface called Map.Entry, the type of the elements in this
Set.
這三種視圖是用來遍歷Map的唯一途徑。