3. List
List是一種有順序的Collection，并允許有重復(fù)的元素。除了從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實(shí)現(xiàn)類：
·ArrayList：性能最好，相當(dāng)于可變長度的數(shù)組
·LinkedList：適合于插入刪除操作。
關(guān)于從Collection繼承過來的操作，有幾點(diǎn)需要注意：
·boolean remove(Object element); 是刪除在List中
第一個(gè)出現(xiàn)的element（因?yàn)長ist允許重復(fù)元素）
·add和addAll操作，是把元素加入到當(dāng)前List的隊(duì)尾
和Set一樣的是，List也增強(qiáng)了對(duì)equals和hashCode操作的約束，任意兩個(gè)List的實(shí)現(xiàn)類，都可以進(jìn)行比較，只要他們包含的元素相同，那么equals就返回true
由于List是有順序的，我們可以根據(jù)元素的位置來進(jìn)行操作。比如下面的例子演示了如何交換兩個(gè)不同位置的元素：
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);
}
有了這個(gè)函數(shù)，我們就可以很容易的得到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，那么來看一下他的一個(gè)簡單應(yīng)用：將傳進(jìn)來的參數(shù)打亂順序
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);
}
}
而實(shí)際上，我們可以用更簡潔的代碼來完成上面的功能，那就是利用Array的asList方法。
我們前面提到過，List可以看作是可變長度的Array，反過來，我們也可以把Array看成是一種特殊的list。因此，java platform就提供了將ArrayC?%8?換成List的方法asList。但要注意的是，asList方法返回的是一個(gè)List，而不是任何一種general-purpose的實(shí)現(xiàn)類。因?yàn)樗祷氐倪@個(gè)list并不實(shí)現(xiàn)add、remove方法－只能看，不能動(dòng)。
public class Shuffle {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.shuffle(list);
System.out.println(list);
}
}
List不光實(shí)現(xiàn)了Iterator，他還根據(jù)自己有序的特性，實(shí)現(xiàn)了一種特殊的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能自由的控制遍歷的方向，而且能隨時(shí)得到當(dāng)前所處的位置，另外，也能在遍歷期間進(jìn)行各種修改操作（add、set、remove）。
還有一點(diǎn)：Iterator只能刪除，不能修改（add、set），而ListIterator可以
為了對(duì)比，我還是把原本的Iterator貼出來：
public interface Iterator<E> {
boolean hasNext();
E next();
void remove(); //optional
}
ListIterator不僅僅是擴(kuò)展了這些方法，連構(gòu)造方法都多了一個(gè)：
除了普通的ListIterator<E> listIterator();
外，還可以用ListIterator<E> listIterator(int index);來獲得指定位置處的listIterator。這樣我們就可以從任意位置，朝任意方向開始遍歷了。
下面關(guān)于List中的subList方法，有一點(diǎn)需要注意，那就是subList返回的是一個(gè)引用，而不是新創(chuàng)建的List。這就意味這你對(duì)subList做的任何操作，都將影響到原來的list（我們稱其為backlist）。因此，subList只能用于臨時(shí)的對(duì)backlist的局部操作，而且要盡早結(jié)束，避免由于其他地方對(duì)backlist的修改導(dǎo)致subList出現(xiàn)問題。當(dāng)然，有一種這種的辦法，就是你根據(jù)返回的subList，創(chuàng)建一個(gè)新的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.
具體內(nèi)容將在介紹算法時(shí)再繼續(xù)深入
4. Queue
Queue就是數(shù)據(jù)結(jié)構(gòu)中介紹的隊(duì)列。除了Collection中提供的基本操作外，他還額外提供了一些關(guān)于插入、刪除、檢查的操作。
Queue的定義如下：
public interface Queue<E> extends Collection<E> {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
Queue有一個(gè)特點(diǎn)，就是它所提供的方法都有兩種形態(tài)：
·失敗時(shí)拋異常的
·失敗時(shí)返回特殊值的（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，就像數(shù)據(jù)結(jié)構(gòu)里介紹的那樣。但也有例外，比如priority queue，可以定義自己的排序方式。但不管順序是怎樣的，排在頭部的都是將要被remove()或者poll()方法拿出來的那個(gè)元素。而當(dāng)插入的時(shí)候，F(xiàn)IFO的queue當(dāng)然是插入隊(duì)尾，但其他形式的queue則由自身的排序規(guī)則決定插入位置
有些queue是由長度限制的，被稱為“bounded queue”，像在java.util.concurrent中實(shí)現(xiàn)的一些queue就是bounded，但java.uti8B?%8?的所有queue都是沒有長度限制的。
·add(e)方法當(dāng)超過queue的長度限制的時(shí)候，就將拋出
IllegalStateException；而offer(e)方法是被設(shè)計(jì)專門用在bounded queue上的，當(dāng)超過隊(duì)列限制時(shí)，該方法將返回false
·當(dāng)隊(duì)列為空時(shí)，調(diào)用remove()方法將拋NoSuchElementException；poll()方法將返回null
·element()和peek()方法和remove()、poll()基本是一樣的，唯一的區(qū)別是他們只是取得頭部元素的值，而并不刪除
需要注意的一點(diǎn)是：Queue 實(shí)現(xiàn)通常不允許插入
null 元素，盡管某些實(shí)現(xiàn)（如
LinkedList）并不禁止插入
null。即使在允許 null 的實(shí)現(xiàn)中，也不應(yīng)該將
null 插入到
Queue 中，因?yàn)?
null 也用作
poll 方法的一個(gè)特殊返回值，表明隊(duì)列不包含元素。
與Set和List不同的是，
Queue 實(shí)現(xiàn)通常未定義
equals 和
hashCode 方法的基于元素的版本，而是從
Object 類繼承了基于身份的版本，因?yàn)閷?duì)于具有相同元素但有不同排序?qū)傩缘年?duì)列而言，基于元素的相等性并非總是定義良好的。
另外，
Queue 接口并未定義
阻塞隊(duì)列的方法，而這在并發(fā)編程中是很常見的。
java.util.cuncurrent.BlockingQueue
接口定義了那些等待元素出現(xiàn)或等待隊(duì)列中有可用空間的方法，這些方法擴(kuò)展了此接口。
5. Map
Map存儲(chǔ)的是“鍵－值”對(duì)，他不允許key重復(fù)，每個(gè)key最多指向一個(gè)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實(shí)現(xiàn)類：HashMap、TreeMap、LinkedHashMap，他們很類似于Set中的HashSet、TreeSet、LinkedHashSet。如果你忘了這三者的區(qū)別，那就看下面一個(gè)簡單的例子：
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);
}
}
運(yùn)行：
java Freq if it is to be it is up to me to delegate
返回的結(jié)果是：
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實(shí)現(xiàn)類應(yīng)該提供兩個(gè)“標(biāo)準(zhǔn)的”構(gòu)造方法：一個(gè) void（無參數(shù)）構(gòu)造方法，用于創(chuàng)建空映射；一個(gè)是帶有單個(gè)
Map
類型參數(shù)的構(gòu)造方法，用于創(chuàng)建一個(gè)與其參數(shù)具有相同鍵-值映射關(guān)系的新映射。實(shí)際上，后一個(gè)構(gòu)造方法允許用戶復(fù)制任意映射，生成所需類的一個(gè)等價(jià)映射。盡管無法強(qiáng)制執(zhí)行此建議（因?yàn)榻涌诓荒馨瑯?gòu)造方法），但是
JDK 中所有通用的Map實(shí)現(xiàn)都遵從它。
和Set、List一樣，Map增強(qiáng)了equals和hashCode方法的約束，任意兩個(gè)Map的實(shí)現(xiàn)類的對(duì)象都可以進(jìn)行比較，只要二者所包含的鍵值對(duì)完全相同，那二者就是相等的。
Map 接口提供三種
collection
視圖，允許以鍵集、值集或鍵-值映射關(guān)系集的形式查看某個(gè)映射的內(nèi)容。映射
順序 定義為迭代器在映射的 collection
視圖上返回其元素的順序。某些映射實(shí)現(xiàn)可明確保證其順序，如
TreeMap 類；另一些映射實(shí)現(xiàn)則不保證順序，如
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的唯一途徑。