核心技术：集合
Java 集合框架
将集合的接口与实现分离
与现代的数据结构类库的常见情况一样， Java 集合类库也将接口（ interface ) 与实现( implementation) 分离。
以队列为例：
队列接口的最简形式可能类似下面这样：
public interface Queue<E> // a simplified form of the interface in the standard library
{
void add(E element) ;
E remove();
int size()；
}
而，队列通常有两种实现方式：
- 一种是使用循环数组；
- 另一种是使用链表；
Colloction 接口
在Java 类库中，集合类的基本接口是Collection 接口。这个接口有两个基本方法
public interface Collection<b
{
boolean add(E element);
Iterator<E> iteratorQ;
...
}
- add 方法用于向集合中添加元素。如果添加元素确实改变了集合就返回true, 如果集合没有发生变化就返回false；
- iterator 方法用于返回一个实现了Iterator 接口的对象；
- 可以使用这个迭代器对象依次访问集合中的元素。
迭代器
Iterator 接口包含4 个方法：
public interface Iterator<E>
{
E next(); // 逐个访问集合中的每个元素（如果到达了集合的末尾将抛出一个NoSuchElementException）
boolean hasNext(); // 遍历时判断是否还有下一个元素
void remove(); //
default void forEachRemaining(Consumer<? super E> action) ; // 对迭代器的每一个元素调用action（Consumer是一个函数式接口，所以可用lambda表达式）
}
如果想要査看集合中的所有元素，就请求一个迭代器，并在hasNext 返回true 时反复地调用next 方法。例如：
Collection<String> c = . . .;
Iterator<String> iter = c.iteratorO；
while (iter.hasNextO)
{
String element = iter.next0；
// do something with element
}
用“ foreach” 循环可以更加简练地表示同样的循环操作：
for (String element : c)
{
// do something with element
}
- 编译器简单地将“for each” 循环翻译为带有迭代器的循环，“for each”循环可以与任何实现了Iterable 接口的对象一起工作；
- Collection 接口扩展了（而非继承）Iterable 接口。因此，对于标准类库中的任何集合都可以使用“for each” 循环。
- 在Java SE 8 中，甚至不用写循环。可以调用forEachRemaining方法并提供 lambda 表达式（它会处理一个元素）。
- 将对迭代器的每一个元素调用这个lambda 表达式，直到再没有元素为止。
i terator.forEachRemai ni ng(el ement -> do something with element);
- 元素被访问的顺序取决于集合类型。
- 如对 ArrayList：迭代器将从索引 0 开始，每次迭代索引值加 1；
- 然而，如对 HashSet 迭代：每个元素将会按照某种随机的次序出现。（能够遍历到集合中的所有元素，但却无法预知元素被访问的次序）
关于迭代器的位置
应该将Java 迭代器认为是位于两个元素之间（而非指向一个元素）。当调用next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。
- Iterator 接口的 remove 方法将会删除上次调用next 方法时返回的元素；
如：
- 删除集合首个元素：
Iterator<String> it = c.iterator(); it.nextO; // skip over the first element it.remove(); // now remove it
- 删除两个相邻的元素：
it.remove(); it.next0； it.remove(); // 而非 // it.remove(); // it.remove();
泛型使用方法
- 由于Collection 与Iterator 都是泛型接口，可以编写操作任何集合类型的实用方法。
- Java 类库提供了一个类AbstractCollection，它将基础方法size和iterator抽象化了，但是提供了例行方法。
- 所以，一个具体的集合类可以扩展AbstractCollection 类了（实际上也是这样的）
- 然而，这种“伴随类”并不是最好的方式，在原接口中将方法定义为“默认方法”会更好。
java.util.Collection<E>
- Iterator < E> iterator()
- 返回一个用于访问集合中每个元素的迭代器。
- int size()
- 返回当前存储在集合中的元素个数。
- boolean isEmpty()
- 如果集合中没有元素， 返回true。
- boolean contains(Object obj)
- 如果集合中包含了一个与obj 相等的对象， 返回true。
- boolean containsAl 1(Collection<?> other)
- 如果这个集合包含other 集合中的所有元素， 返回trueo
- boolean add(Object element)
- 将一个元素添加到集合中。如果由于这个调用改变了集合，返回true。
- boolean addAl1(Col1ection<? extends E> other)
- 将other 集合中的所有元素添加到这个集合。如果由于这个调用改变了集合，返回true。
- boolean remove(Object obj)
- 从这个集合中删除等于obj 的对象。如果有匹配的对象被删除， 返回true。
- boolean removeAl 1(Col 1ection<?> other)
- 从这个集合中删除other 集合中存在的所有元素。如果由于这个调用改变了集合，返回true。
- default boolean removelf(Predicate<? super E> filter)8
- 从这个集合删除filter 返回true 的所有元素。如果由于这个调用改变了集合，则返回true。
- void clear()
- 从这个集合中删除所有的元素。
- boolean retainAl1(Collection<?> other)
- 从这个集合中删除所有与other 集合中的元素不同的元素。如果由于这个调用改变了集合， 返回true。
- Object[]toArray()
- 返回这个集合的对象数组。
- <T> T[]toArray(T[]arrayToFi11)
- 返回这个集合的对象数组。如果arrayToFill 足够大，就将集合中的元素填入这个数组中。剩余空间填补null; 否则，分配一个新数组，其成员类型与arrayToFill的成员类型相同，其长度等于集合的大小，并填充集合元素。
java.util.Iterator<E>
- boolean hasNext()
- 如果存在可访问的元素， 返回true。
- E next()
- 返回将要访问的下一个对象。如果已经到达了集合的尾部， 将拋出一个NoSuchElementException。
- void remove( )
- 删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后，集合已经发生了变化， 这个方法将抛出一个IllegalStateException。
集合框架中的接口
- 集合有两个基本接口：Collection 和Map。
- 可以用以下方法在集合中插人元素：
boolean add(E element)
- 不过，由于映射包含键/ 值对，所以要用put 方法来插人：
V put(K key, V value)
- 要从集合读取元素， 可以用迭代器访问元素。不过，从映射中读取值则要使用get 方法：
V get (K key)
List
List 是一个有序集合（ordered collection），元素会增加到容器中的特定位置。可以采用两种方式访问元素：
- 迭代器访问
- 随机访问（random access)
- List 接口定义了多个用于随机访问的方法：
- void add(int index, E element)
- void remove(int index)
- E get(int index)
- E set(int index, E element)
Set
Set 接口等同于Collection 接口，不过其方法的行为有更严谨的定义：集（ set ) 的add 方法不允许增加重复的元素。
- 要适当地定义集的equals 方法：只要两个集包含同样的元素就认为是相等的，而不要求这些元素有同样的顺序。
- hashCode 方法的定义要保证包含相同元素的两个集会得到相同的散列码。
- SortedSet 和SortedMap接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法。
- Java SE 6 引人了接口NavigableSet和NavigableMap，其中包含一些用于搜索和遍历有序集和映射的方法。
具体的集合
| 集合类型 | 描述 |
|---|---|
| AbstractCollection | |
| ArrayList | 一种可以动态增长和缩减的索引序列 |
| LinkedList | 一种可以在任何位置进行高效地插人和删除操作的有序序列 |
| ArrayDeque | 一种用循环数组实现的双端队列 |
| HashSet | 一种没有重复元素的无序集合 |
| TreeSet | —种有序集 |
| EnumSet | 一种包含枚举类型值的集 |
| LinkedHashSet | 一种可以记住元素插人次序的集 |
| PriorityQueue | 一种允许高效删除最小元素的集合 |
| AbstractMap | |
| HashMap | 一种存储键/值关联的数据结构 |
| TreeMap | —种键值有序排列的映射表 |
| EnumMap | 一种键值属于枚举类型的映射表 |
| LinkedHashMap | 一种可以记住键/值项添加次序的映射表 |
| WeakHashMap | 一种其值无用武之地后可以被垃圾回收器回收的映射表 |
| IdentityHashMap | 一种用==而不是用equals比较键值的映射表 |
链表（LinkedList）
- 链表不支持随机方法，但便于插入删除；
- Java中的所有链表实际上都是双向链接的（双向链表）；
添加
- LinkedList.add：将对象添加到链表的尾部；
- ListIterator.add：将对象添加到当前位置；
删除
- （Java中删除链表元素不需要考虑内部指向，调用方法即可）
- 在调用 next 之后 remove，会删除迭代器左侧的元素（类似键盘的“删除”）
- 在调用 previous 之后 remove，删除迭代器右侧的元素（类似键盘的“DEL”）
ListItetator
- ListItetator：Iterator的子类，专门用于LinkedList的迭代；
- 迭代器的位置，并不直接指向元素，而是在元素之间；
- 迭代器的 add 方法只依赖于迭代器的位置，而 remove 方法依赖于迭代器的状态（调用了next还是previous）；
- 同一个LinkedList的多个迭代器之间操作冲突的话（一个修改了集合，一个正在读），会抛出“ConcurrentModificationException”异常。
- 所以：可以更具需要给容器附加多个迭代器，但只有一个可以进行修改操作；
- 尽量使用迭代器，而不使用 LinkedList.get方法来进行读取（效率太低）
常用方法
java.util.List<E>
- ListIterator<E> 1 istIterator ( )
- 返回一个列表迭代器， 以便用来访问列表中的元素。
- ListIterator <E> 1 istIterator( int index )
- 返回一个列表迭代器， 以便用来访问列表中的元素， 这个元素是第一次调用next 返回的给定索引的元素。
- void add( int i , E element )
- 在给定位置添加一个元素。
- void addAl 1 ( int i , Col 1ection<? extends E> elements )
- 将某个集合中的所有元素添加到给定位置。
- E remove( int i )
- 删除给定位置的元素并返回这个元素。
- E get ( int i )
- 获取给定位置的元素。
- E set ( int i , E element )
- 用新元素取代给定位置的元素， 并返回原来那个元素。
- int indexOf (Object element )
- 返回与指定元素相等的元素在列表中第一次出现的位置， 如果没有这样的元素将返回-1。
- int 1 astlndexOf(Object element)
- 返回与指定元素相等的元素在列表中最后一次出现的位置， 如果没有这样的元素将返回-1。
java.util.Listlterator<E>
- void add(E newElement)
在当前位置前添加一个元素。
- void set(E newElement)
- 用新元素取代next 或previous 上次访问的元素。如果在next 或previous 上次调用之后列表结构被修改了， 将拋出一个IllegalStateException 异常。
- boolean hasPrevious()
- 当反向迭代列表时， 还有可供访问的元素， 返回true。
- E previous()
- 返回前对象。如果已经到达了列表的头部， 謝te出一hNoSuchElementException 异常。
- int nextlndex()
- 返回下一次调用next 方法时将返回的元素索引。
- int previousIndex()
- 返回下一次调用previous 方法时将返回的元素索引。
java.util.LinkedList<E>
- LinkedList()
- 构造一个空链表。
- LinkedList(Col 1ection<? extends E> elements)
- 构造一个链表， 并将集合中所有的元素添加到这个链表中。
- void addFirst(E element)
- void addLast(E element)
- 将某个元素添加到列表的头部或尾部。
- E getFirst()
- E getLast()
- 返回列表头部或尾部的元素。
- E removeFirst()
- E removeLast()
- 删除并返回列表头部或尾部的元素。
数组列表（ArrayList）
List的数组实现，支持随机读取，不便于插入删除（需要移动元素）。
ArrayList 与 Vector
Vector 类的所有方法都是同步的，可以由两个线程安全地访问一个 Vector 对象，但也比 ArrayList 更耗时；
- Vector 的方法中，用到了synchronized来实现同步锁；