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的唯一途径。