核心技术：集合

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()；
}

而，队列通常有两种实现方式：

1. 一种是使用循环数组；
2. 另一种是使用链表；

Colloction 接口

在 Java 类库中，集合类的基本接口是 Collection 接口。这个接口有两个基本方法

public interface Collection<E>
{
   boolean add(E element);
   Iterator<E> iterator();
   ...
}

1. add 方法用于向集合中添加元素。如果添加元素确实改变了集合就返回 true, 如果集合没有发生变化就返回 false；
2. iterator 方法用于返回一个实现了 Iterator 接口的对象；

   可以使用这个迭代器对象依次访问集合中的元素。

迭代器

参考：关于Iterable与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.iterator()；
while (iter.hasNextO)
{
    String element = iter.next()；
    // do something with element
}

用“ foreach” 循环可以更加简练地表示同样的循环操作：

for (String element : c)
{
    // do something with element
}

• 编译器简单地将“foreach” 循环翻译为带有迭代器的循环，“foreach”循环可以与任何实现了 Iterable 接口的对象一起工作；

  Collection 接口扩展了（而非继承）Iterable 接口。因此，对于标准类库中的任何集合都可以使用“foreach” 循环。

• 在 Java SE 8 中，甚至不用写循环。可以调用forEachRemaining方法并提供 lambda 表达式（它会处理一个元素）。

  将对迭代器的每一个元素调用这个 lambda 表达式，直到再没有元素为止。

      iterator.forEachRemaining(element -> do something with element);
  

• 元素被访问的顺序取决于集合类型。

  如对 ArrayList：迭代器将从索引 0 开始，每次迭代索引值加 1；

  然而，如对 HashSet 迭代：每个元素将会按照某种随机的次序出现。（能够遍历到集合中的所有元素，但却无法预知元素被访问的次序）

【关于：迭代器的位置】

应该将 Java 迭代器认为是位于两个元素之间（而非指向一个元素）。当调用 next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

• Iterator 接口的 remove 方法将会删除上次调用 next 方法时返回的元素；

如：

1. 删除集合首个元素：

       Iterator<String> it = c.iterator();
       it.next();        // skip over the first element
       it.remove();     // now remove it
   

2. 删除两个相邻的元素：

       it.remove();
       it.next()；
       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 containsAll(Collection<?> other)	如果这个集合包含other 集合中的所有元素，返回trueo
boolean add(Object element)	将一个元素添加到集合中。 如果由于这个调用改变了集合，返回true。
boolean addAll(Col1ection<? extends E> other)	将other 集合中的所有元素添加到这个集合。 如果由于这个调用改变了集合，返回true。
boolean remove(Object obj)	从这个集合中删除等于obj 的对象。 如果有匹配的对象被删除， 返回true。
boolean removeAll(Col 1ection<?> other)	从这个集合中删除other 集合中存在的所有元素。 如果由于这个调用改变了集合，返回true。
default boolean removeIf(Predicate<? super E> filter)8	从这个集合删除filter 返回true 的所有元素。 如果由于这个调用改变了集合，则返回true。
void clear()	从这个集合中删除所有的元素。
boolean retainAll(Collection<?> other)	从这个集合中删除所有与other 集合中的元素不同的元素。 如果由于这个调用改变了集合，返回true。
Object[] toArray()	返回这个集合的对象数组。
<T> T[] toArray(T[] arrayToFill)	返回这个集合的对象数组。 如果 arrayToFill 足够大，就将集合中的元素填入这个数组中。剩余空间填补null; 否则，分配一个新数组，其成员类型与 arrayToFill 的成员类型相同，其长度等于集合的大小，并填充集合元素。
java.util.Iterator<E>
boolean hasNext()	如果存在可访问的元素，返回true。
E next()	返回将要访问的下一个对象。 如果已经到达了集合的尾部，将拋出一个 NoSuchElementException。
void remove()	删除上次访问的对象。 这个方法必须紧跟在访问一个元素之后执行。 如果上次访问之后，集合已经发生了变化， 这个方法将抛出一个 IllegalStateException。

集合框架中的接口

1. 集合有两个基本接口：Collection 和Map。

   可以用以下方法在集合中插人元素：

   boolean add(E element)
   

   不过，由于映射包含键/ 值对，所以要用put 方法来插人：

   V put(K key, V value)
   

   要从集合读取元素， 可以用迭代器访问元素。不过，从映射中读取值则要使用get 方法：

   V get (K key)
   

List

List 是一个有序集合（ordered collection），元素会增加到容器中的特定位置。可以采用两种方式访问元素：

1. 迭代器访问
2. 随机访问（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，其中包含一些用于搜索和遍历有序集和映射的方法。

具体的集合

Java 库中的具体集合

集合类型	描述
AbstractCollection
ArrayList	一种可以动态增长和缩减的索引序列
LinkedList	一种可以在任何位置进行高效地插人和删除操作的有序序列
ArrayDeque	一种用循环数组实现的双端队列
HashSet	一种没有重复元素的无序集合
TreeSet	—种有序集
EnumSet	一种包含枚举类型值的集
LinkedHashSet	一种可以记住元素插人次序的集
PriorityQueue	一种允许高效删除最小元素的集合
AbstractMap
HashMap	一种存储键/值关联的数据结构
TreeMap	—种键值有序排列的映射表
EnumMap	一种键值属于枚举类型的映射表
LinkedHashMap	一种可以记住键/值项添加次序的映射表
WeakHashMap	一种其值无用武之地后可以被垃圾回收器回收的映射表
IdentityHashMap	一种用==而不是用equals比较键值的映射表

链表（LinkedList）

• 链表不支持随机方法，但便于插入删除；
• Java中的所有链表实际上都是双向链接的（双向链表）；

添加

1. LinkedList.add：将对象添加到链表的尾部；
2. ListIterator.add：将对象添加到当前位置；

删除

• （Java中删除链表元素不需要考虑内部指向，调用方法即可）

1. 在调用 next 之后 remove，会删除迭代器左侧的元素（类似键盘的“删除”）
2. 在调用 previous 之后 remove，删除迭代器右侧的元素（类似键盘的“DEL”）

ListItetator

• ListItetator：Iterator的子类，专门用于LinkedList的迭代；
• 迭代器的位置，并不直接指向元素，而是在元素之间；
• 迭代器的 add 方法只依赖于迭代器的位置，而 remove 方法依赖于迭代器的状态（调用了next还是previous）；
• 同一个LinkedList的多个迭代器之间操作冲突的话（一个修改了集合，一个正在读），会抛出“ConcurrentModificationException”异常。

  所以：可以更具需要给容器附加多个迭代器，但只有一个可以进行修改操作；

• 尽量使用迭代器，而不使用 LinkedList.get方法来进行读取（效率太低）

相关方法：

java.util.List<E>
ListIterator<E> listIterator ( )	返回一个列表迭代器， 以便用来访问列表中的元素。
ListIterator <E> listIterator (int index )	返回一个列表迭代器， 以便用来访问列表中的元素， 这个元素是第一次调用next 返回的给定索引的元素。
void add (int i , E element)	在给定位置添加一个元素。
void addAll (int i , Collection<? extends E> elements)	将某个集合中的所有元素添加到给定位置。
E remove (int i)	删除给定位置的元素并返回这个元素。
E get (int i)	获取给定位置的元素。
E set (int i , E element)	用新元素取代给定位置的元素， 并返回原来那个元素。
int indexOf (Object element)	返回与指定元素相等的元素在列表中第一次出现的位置， 如果没有这样的元素将返回-1。
int lastIndexOf(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 nextIndex()	返回下一次调用next 方法时将返回的元素索引。
int previousIndex()	返回下一次调用previous 方法时将返回的元素索引。
java.util.LinkedList<E>
LinkedList()	构造一个空链表。
LinkedList(Collection<? 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来实现同步锁；

散列集（HashSet）

利用对象的hashcode，来将对象存放在散列集的不同位置。

• HashSet 的迭代器将依次访问所有的桶。由于元素散列分布，所以迭代器访问元素是无序的；
• 修改元素时，如果元素的散列码变化，则其在数据结构中的位置也会变化

HashSet的实现：

• 由其构造函数可以看出，HashSet 是由 HashMap 来实现的：

  public HashSet() {
  	map = new HashMap<>();
  }
  
  public HashSet(Collection<? extends E> c) {
  	map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
  	addAll(c);
  }
  
  public HashSet(int initialCapacity, float loadFactor) {
  	map = new HashMap<>(initialCapacity, loadFactor);
  }
  
  public HashSet(int initialCapacity) {
  	map = new HashMap<>(initialCapacity);
  }
  
  HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  	map = new LinkedHashMap<>(initialCapacity, loadFactor);
  }
  

散列表

散列表，用于保存集合中对象的散列码。Java中，散列表用链表数组实现：

（每个列表被称为一个桶，bucket） 要想査找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。

例如， 如果某个对象的散列码为76268, 并且有128个桶， 对象应该保存在第108号桶中（76268除以128余108)

散列冲突

插入对象时，遇到桶被占满的情况，即为散列冲突。
这时， 需要用新对象与桶中的所有对象进行比较， 査看这个对象是否已经存在。如果散列码是合理且随机分布的， 桶的数目也足够大， 需要比较的次数就会很少。

• 在JavaSE 8 中， 桶满时会从链表变为平衡二叉树（便于查找？）。

桶数

桶数，是指用于收集具有相同散列值的桶的数目。通常，将桶数设置为预计元素个数的75% ~ 150%。

• 标准类库使用的桶数是2 的幂， 默认值为16

再散列

如果散列表太满，就需要再散列（rehashed)：创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。

装填因子（load factor) 决定何时对散列表进行再散列。
例如， 如果装填因子为0.75 (默认值)，而表中超过75%的位置已经填人元素， 这个表就会用双倍的桶数自动地进行再散列。

• 对于大多数应用程序来说， 装填因子为 0.75 是比较合理的；

相关方法：

java.util.HashSet<E>
HashSet ( )	构造一个空散列表。
HashSet (Collection<? extends E> elements )	构造一个散列集，并将集合中的所有元素添加到这个散列集中。
HashSet (int initialCapacity)	构造一个空的具有指定容量（桶数）的散列集。
HashSet (int initialCapacity , float loadFactor )	构造一个具有指定容量和装填因子（一个0.0 ~ 1.0 之间的数值， 确定散列表填充的百分比，当大于这个百分比时，散列表进行再散列）的空散列集。
java.lang.Object
int hashCode ( )	返回这个对象的散列码。散列码可以是任何整数，包括正数或负数。 equals 和hashCode的定义必须兼容，即如果“x.equals(y)”为“true”,“x.hashCode()”必须等于“y.hashCode()”。

树集（TreeSet）

树集是一个有序集合(sorted collection)。元素的排序是用树结构完成的（当前使用的是“红黑树”）；

• 使用树集，元素必须实现 Comparable 接口，或者构造集时必须提供一个 Comparator。
• Java6 之后，TreeSet类实现了 NavigableSet 接口。

  这个接口增加了几个便于定位元素以及反向遍历的方法。

每次将一个元素添加到树中时，都被放置在正确的排序位置上。因此：

1. 迭代器总是以排好序的顺序访问每个元素。
2. 添加插入较HashSet慢，但查找更快。
3. 如果树中包含 n 个元素，査找新元素的正确位置平均需要“log2 n”次比较。

TreeSet的实现：

• 由其构造函数可以看出，TreeSet 是由 TreeMap 来实现的：

  public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
  {
      /**
       * The backing map.
       */
      private transient NavigableMap<E,Object> m;
  
      // Dummy value to associate with an Object in the backing Map
      private static final Object PRESENT = new Object();
  
      TreeSet(NavigableMap<E,Object> m) {
          this.m = m;
      }
  
      public TreeSet() {
          this(new TreeMap<E,Object>());
      }
  
      public TreeSet(Comparator<? super E> comparator) {
          this(new TreeMap<>(comparator));
      }
  
      public TreeSet(Collection<? extends E> c) {
          this();
          addAll(c);
      }
  
      public TreeSet(SortedSet<E> s) {
          this(s.comparator());
          addAll(s);
      }
  	
  	public  boolean addAll(Collection<? extends E> c) {
          // Use linear-time version if applicable
          if (m.size()==0 && c.size() > 0 &&
              c instanceof SortedSet &&
              m instanceof TreeMap) {
              SortedSet<? extends E> set = (SortedSet<? extends E>) c;
              TreeMap<E,Object> map = (TreeMap<E, Object>) m;
              Comparator<?> cc = set.comparator();
              Comparator<? super E> mc = map.comparator();
              if (cc==mc || (cc != null && cc.equals(mc))) {
                  map.addAllForTreeSet(set, PRESENT);
                  return true;
              }
          }
          return super.addAll(c);
      }
  

相关方法：

java.util.TreeSet<E>
TreeSet()	构造一个空树集。
TreeSet(Comparator<? super E> comparator)
TreeSet(Collection<? extends E> elements)	构造一个树集， 并增加一个集合或有序集中的所有元素（对于后一种情况，要使用同样的顺序)。
TreeSet(SortedSet<E> s)
java.util.SortedSet<E>
Comparator<? super E> comparator()	返回用于对元素进行排序的比较器。如果元素用Comparable 接口的compareTo方法进行比较则返回null。
E first()	返回有序集中的最小元素或最大元素。
E last()
java.util.NavigableSet<E>
E higher(E value)	返回大于value 的最小元素或小于value 的最大元素，如果没有这样的元素则返回null。
E lower(E value)
E ceiling(E value)	返回大于等于vaiue 的最小元素或小于等于value 的最大元素， 如果没有这样的元素则返回null。
E floor(E value)
E pollFirst()	删除并返回这个集中的最大元素或最小元素， 这个集为空时返回null。
E pollLast()
Iterator<E> descendingIterator()	返回一个按照递减顺序遍历集中元素的迭代器。

队列（Queue）双端队列（Deque）

在Java SE 6 中引人了Deque 接口，ArrayDeque和LinkedList类实现了Deque接口。这两个类都提供了双端队列， 而且在必要时可以增加队列的长度。

public interface Deque<E> extends Queue<E> {

public interface Queue<E> extends Collection<E> {

• （在第14章将会看到有限队列和有限双端队列。）
• （看看消息中间件的实现？）

相关方法：

java.util.Queue<E>
boolean add (E element)	如果队列没有满，将给定的元素添加到这个双端队列的尾部并返回true。 如果队列满了，第一个方法将拋出一个 IllegalStateException, 而第二个方法返回 false。
boolean offer (E element)
E remove ( )	假如队列不空， 删除并返回这个队列头部的元素。 如果队列是空的，第一个方法抛出 NoSuchElementException, 而第二个方法返回 null。
E poll ( )
E element( )	如果队列不空，返回这个队列头部的元素，但不删除。 如果队列空，第一个方法将拋出一个 NoSuchElementException, 而第二个方法返回 null。
E peek( )
java.util.Deque<E>
void addFirst (E element)	将给定的对象添加到双端队列的头部或尾部。 如果队列满了，前面两个方法将拋出一个 IllegalStateException，而后面两个方法返回 false。
void addLast (E element)
boolean offerFirst (E element)
boolean offerLast (E element)
E removeFirst( )	如果队列不空，删除并返回队列头部的元素。 如果队列为空，前面两个方法将拋出一个 NoSuchElementException, 而后面两个方法返回 null。
E removeLast( )
E pollFirst( )
E pollLast( )
E getFirst( )	如果队列非空，返回队列头部的元素，但不删除。 如果队列空，前面两个方法将拋出一个 NoSuchElementException, 而后面两个方法返回 null。
E getLast( )
E peekFirst( )
E peekLast( )
java.util.ArrayDeque<E>
ArrayDeque( )	用初始容量16 或给定的初始容量构造一个无限双端队列。
ArrayDeque(int initialCapacity)

【关于：阻塞队列（BlockingQueue）】

BlockingQueue<E> 接口扩展了 Queue<E>接口，用于阻塞队列的实现。

• 见：【Java中的阻塞队列】

优先级队列（priority queue）

优先级队列（priority queue) 中的元素可以按照任意的顺序插人，却总是按照排序的顺序进行检索。

• 无论何时调用remove 方法， 总会获得当前优先级队列中最小的元素。
• 优先级队列使用堆（heap)，对树执行添加（add) 和删除（remore) 操作，让最小的元素移动到根，而不必花费时间对元素进行排序。

  堆是一个可以自我调整的二叉树；

• 与TreeSet—样，一个优先级队列既可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供的Comparator对象。

• 使用优先级队列的典型示例是任务调度。

相关方法：

java.util.PriorityQueue
PriorityQueue()	构造一个用于存放 Comparable 对象的优先级队列。
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity, Comparator<? super E> c)	构造一个优先级队列， 并用指定的比较器对元素进行排序。

映射

• 映射“Map”接口并不实现“Iterator”，所以并没有迭代器，但是其“entrySet()”返回值类型是“Set”接口的实现类，可以用它的迭代器对映射进行迭代操作；

基本映射操作

Java 类库为映射提供了两个通用的实现：HashMap 和TreeMap。这两个类都实现了Map 接口。

1. 散列映射对键进行散列，
2. 树映射用键的整体顺序对元素进行排序， 并将其组织成搜索树。

• 散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

相关方法：

java.util.Map<K, V>
V get(Object key)	获取与键对应的值；返回与键对应的对象，如果在映射中没有这个对象则返回null。键可以为null。
default V getOrDefault(Object key, V defaultValue)	获得与键关联的值；返回与键关联的对象，或者如果未在映射中找到这个键，则返回defaultValue。
V put(K key, V value)	将键与对应的值关系插入到映射中。 如果这个键已经存在，新的对象将取代与这个键对应的旧对象。 这个方法将返回键对应的旧值。如果这个键以前没有出现过则返回null。 键可以为null， 但值不能为null。
void putAll(Map<? extends K , ? extends V> entries)	将给定映射中的所有条目添加到这个映射中。
boolean containsKey(Object key)	如果在映射中已经有这个键， 返回true。
boolean containsValue(Object value)	如果映射中已经有这个值， 返回true。
default void forEach(BiConsumer<? super K ,? super V> action)8	对这个映射中的所有键/ 值对应用这个动作。
java.utii.HashMap<K,V>
HashMap( )	用给定的容量和装填因子构造一个空散列映射。 （装填因子是一个 0.0 ~ 1.0 之间的数值。这个数值决定散列表填充的百分比。一旦到了这个比例，就要将其再散列到更大的表中） 默认的装填因子是0.75。
HashMap(int initialCapacity)
HashMap(int initialCapacity, float 1oadFactor)
java.util.TreeMap<K,V>
TreeMap( )	为实现Comparable 接口的键构造一个空的树映射。
TreeMap(Comparator<? super K> c)	构造一个树映射， 并使用一个指定的比较器对键进行排序。
TreeMap(Map<? extends K, ? extends V> entries)	构造一个树映射， 并将某个映射中的所有条目添加到树映射中。
TreeMap(SortedMap<? extends K, ? extends V> entries)	构造一个树映射， 将某个有序映射中的所有条目添加到树映射中， 并使用与给定的有序映射相同的比较器。
java.util.SortedMap<K, V>
Comparator< ? super K> comparator()	返回对键进行排序的比较器。如果键是用Comparable 接口的compareTo 方法进行比较的，返回null。
K firstKey( )	返回映射中最小元素和最大元素。
K lastKey( )

更新映射项

以“使用一个映射统计一个单词在文件中出现的频度”为例：

1. 看到一个单词（word) 时，将计数器增1， 如下所示：

   counts.put(word, counts.get(word)+ 1);
   

   这是可以的， 不过有一种情况除外： 就是第一次看到word 时。在这种情况下，get 会返回null , 因此会出现一个NullPointerException 异常。

   作为一个简单的补救， 可以使用getOrDefault 方法：

   counts.put(word, counts.getOrDefault(word, 0)+ 1);
   

2. 另一种方法是首先调用putlfAbsent 方法。只有当键原先存在时才会放入一个值。

   counts.putlfAbsent(word, 0);
   counts.put(word, counts.get(word)+ 1); // Now we know that get will succeed
   

3. 不过还可以使用 merge 方法简化这个常见的操作。如果键原先不存在，下面的调用：

   counts.merge(word, 1, Integer::sum);
   

   将把word 与1 关联，否则使用Integer::sum 函数组合原值和1 (也就是将原值与1 求和)。

相关方法：

java.util.Map<K,V> 1.2
default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) 8	如果 key 与一个非 null 值 v 关联，将函数应用到 v 和 value，将key 与结果关联，或者如果结果为 null ，则删除这个键。否则，将key 与value 关联，返回 get(key)。
default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 8	将函数应用到 key 和 get(key)。将 key 与结果关联，或者如果结果为 null ，则删除这个键。返回 get(key)。
default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 8	如果 key 与一个非 null 值 v 关联，将函数应用到 key 和 v，将 key 与结果关联，或者如果结果为 null ，则删除这个键。返回 get(key)。
default V computeIfAbsent(K key , Function<? super K, ? extends V> mappingFunction) 8	将函数应用到 key，除非 key 与一个非 null 值关联。将 key 与结果关联，或者如果结果为 null ，则删除这个键。返回 get(key)。
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 8	在所有映射项上应用函数。将键与非 null 结果关联，对于 null 结果，则将相应的键删除。

映射视图（键集、键/值对集）

集合框架不认为映射本身是一个集合。（其他数据结构框架认为映射是一个 键/值 对集合，或者是由键索引的值集合）。不过，可以得到映射的视图（ View )——这是实现了Collection 接口或某个子接口的对象。

三种视图如下：

视图	命令	示例
键集	Set<K> keySet()	Set<String> keys = map.keySet(); for (String key : keys) { // do something with key }
值集合	Collection<V> values() （不是一个集，因为可以重复）
键/值对集	Set<Map.Entry<K, V>> entrySet()	for (Map.Entry<String, Employee〉entry : staff.entrySet()) { String k = entry.getKey()； Employee v = entry.getValue(); // do something with k, v }

• 条目集的元素是实现 Map.Entry 接口的类的对象。
• 如果在“键集”视图上调用迭代器的remove方法，会从映射中删除这个键和与它关联的值；如果试图调用add 方法， 它会抛出一个UnsupportedOperationException。
• 原先“键/值对集”是访问所有映射条目的最高效的方法。如今，只需要使用forEach方法（使用lambda表达式）：

  counts.forEach((k， v) -> {
        // do something with k, v
     })；
  

相关方法：

java.util.Map<K, V>
Set<Map.Entry<K, V>> entrySet( )	返回 Map.Entry 对象（映射中的键/ 值对）的一个集视图。 可以从这个集中删除元素，它们将从映射中删除，但是不能增加任何元素。
Set<K> keySet( )	返回映射中所有键的一个集视图。 可以从这个集中删除元素，键和相关联的值将从映射中删除，但是不能增加任何元素。
Collection<V> values( )	返回映射中所有值的一个集合视图。 可以从这个集合中删除元素，所删除的值及相应的键将从映射中删除，不过不能增加任何元素。
java.util.Map.Entry<K, V>
K getKey( )	返回这一条目的键或值。
V getValue( )
V setValue(V newValue)	将相关映射中的值改为新值，并返回原来的值。

弱散列映射

【？？？】

链接散列集与映射（LinkedHashSet 与 LinkedHashMap）

LinkedHashSet 和 LinkedHashMap 类用来记住插人元素项的顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。当条目插入到表中时，就会并人到双向链表中。

• LinkedHashSet 由 LinkedHashMap 实现；
• LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。

特点：

• 散列表（HashMap）用于元素的存储结构；
• 双向链（List）表用于维护元素的迭代顺序，用于元素遍历（可以是插入顺序，也可以是访问顺序）；

关于“迭代顺序”：“插入顺序”“访问顺序”

如上所述，迭代（遍历） LinkedHashMap 元素的时候，会按照链接顺序（即：迭代顺序）进行。
而迭代顺序：

1. 可以是“插入顺序”：按插入顺序维护链表；
2. 也可以是“访问顺序”：按访问顺序维护链表（即链表头元素是“最近最少使用”）；

而这取决于其“accessOrder”值域：

1. 构造对象时，确定 accessOrder：

   	public LinkedHashMap(int initialCapacity, float loadFactor) {
           super(initialCapacity, loadFactor);
           accessOrder = false;
       }
   
       public LinkedHashMap(int initialCapacity) {
           super(initialCapacity);
           accessOrder = false;
       }
   
       public LinkedHashMap() {
           super();
           accessOrder = false;
       }
   
       public LinkedHashMap(Map<? extends K, ? extends V> m) {
           super();
           accessOrder = false;
           putMapEntries(m, false);
       }
   
       public LinkedHashMap(int initialCapacity,
                            float loadFactor,
                            boolean accessOrder) {
           super(initialCapacity, loadFactor);
           this.accessOrder = accessOrder;
       }
   

2. 调用相关方法时，用accessOrder值判断，是否将被访问的元素放到链表末尾；

   	public V get(Object key) {
           Node<K,V> e;
           if ((e = getNode(hash(key), key)) == null)
               return null;
           if (accessOrder)
               afterNodeAccess(e);
           return e.value;
       }
   	...
   	void afterNodeAccess(Node<K,V> e) { // move node to last
           LinkedHashMap.Entry<K,V> last;
           if (accessOrder && (last = tail) != e) {
               LinkedHashMap.Entry<K,V> p =
                   (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
               p.after = null;
               if (b == null)
                   head = a;
               else
                   b.after = a;
               if (a != null)
                   a.before = b;
               else
                   last = b;
               if (last == null)
                   head = p;
               else {
                   p.before = last;
                   last.after = p;
               }
               tail = p;
               ++modCount;
           }
       }
   

枚举集与映射（EnumSet 与 EnumMap）

EnumSet

EmimSet 是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet 内部用位序列实现。如果对应的值在集中，则相应的位被置为1。

• EnumSet 类没有公共的构造器。可以使用静态工厂方法构造这个集：

  enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
  EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
  EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
  EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
  EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);
  

• 可以使用Set 接口的常用方法来修改EnumSet。

EnumMap

EnumMap 是一个键类型为枚举类型的映射。它可以直接且高效地用一个值数组实现。

• 在使用时， 需要在构造器中指定键类型：

  EnumMap<Weekday, Employee〉personlnCharge = new EnumMap<>(Weekday.class);
  

• 所有的枚举类型都扩展于泛型Enum 类。

  例如，Weekday 扩展于 Enum<Weekday>。

标识散列映射（IdentityHashMap）

   类 IdentityHashMap 有特殊的作用。在这个类中， 键的散列值不是用 hashCode 函数计算的， 而是用 System.identityHashCode 方法计算的。这是Object.hashCode 方法根据对象的内存地址来计算散列码时所使用的方式。而且， 在对两个对象进行比较时，IdentityHashMap 类使用 ==, 而不使用 equals。
   也就是说，不同的键对象，即使内容相同，也被视为是不同的对象。在实现对象遍历算法（如对象串行化）时，这个类非常有用，可以用来跟踪每个对象的遍历状况。

特点：

1. 使用“System.identityHashCode”方法计算其 hashcode（即，使用对象内存地址计算 hashcode）；
2. 使用“==”来比较对象；

即，每个对象 hashcode （几乎）唯一，（几乎）不会出现冲突。

相关方法：

java.util.WeakHashMap<K,V> 1.2
WeakHashMap( )	用给定的容量和填充因子构造一个空的散列映射表。
WeakHashMap(int initialCapacity)
WeakHashMap(int initialCapacity, float loadFactor)
java.util.LinkedHashSet<E> 1.4
LinkedHashSet( )	用给定的容量和填充因子构造一个空链接散列集。
LinkedHashSet(int initialCapacity)
LinkedHashSet(int initialCapacity, float loadFactor)
java.util.LinkedHashMap<K,V> 1.4
LinkedHashMap( )	用给定的容量、填充因子和顺序构造一个空的链接散列映射表。 accessOrder 参数为 true 时表示访问顺序，为false 时表示插入顺序。
LinkedHashMap(int initialCapacity)
LinkedHashMap(int initialCapacity, float loadFactor)
LinkedHashMap(int initialCapacity, float loadFactor , boolean accessOrder)
protected boolean removeEldestEntry(Map.Entry<K, V> eldest)	如果想删除 eldest 元素，并同时返回true ，就应该覆盖这个方法。 eldest 参数是预期要删除的条目。这个方法将在条目添加到映射中之后调用。 其默认的实现将返回false。即在默认情况下，旧元素没有被删除。然而，可以重新定义这个方法，以便有选择地返回的 true。 例如，如果最旧的条目符合一个条件，或者映射超过了一定大小，则返回 true 。
java.util.EnumSet<E extends Enum<E>> 5.0
static <E extends Enum<E > EnumSet<E> allOf(Class<E> enumType)	返回一个包含给定枚举类型的所有值的集。
static <E extends Enum<E > EnumSet<E> noneOf(Class<E> enumType)	返回一个空集，并有足够的空间保存给定的枚举类型所有的值。
static <E extends Enum<E > EnumSet<E> range(E from, E to)	返回一个包含 from ～ to 之间的所有值（包括两个边界元素）的集。
static <E extends Enum<E > EnumSet<E> of(E value)	返回包括给定值的集。
static <E extends Enum<E > EnumSet<E> of(E value, E ... values)
java.util.EnumMap<K extends Enum<K>, V> 5.0
EnumMap(Class<K> keyType)	构造一个键为给定类型的空映射。
java.util.IdentityHashMap<K, V> 1.4
IdentityHashMap()	构造一个空的标识散列映射集，其容量是大于 1.5 * expectedMaxSize 的2 的最小次幕(expectedMaxSize 的默认值是 21）。
IdentityHashMap(int expectedMaxSize)
java.lang.System 1.0
static int identityHashCode( Object obj) 1.1	返回 Object.hashCode 计算出来的相同散列码（根据对象的内存地址产生），即使 obj 所属的类已经重新定义了 hashCode 方法也是如此。

视图与包装器

通过使用视图（views）可以获得其他的实现了Collection 接口和Map 接口的对象。

以“HashMap<K,V>”为例：

    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

    final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

“keySet()”方法返回了一个实现了“Set<K>”接口的类（“KeySet”）的对象，这个类（“KeySet”）的方法可以对原HashMap进行操作，这个集合（“KeySet”）就是视图，这个对象（“ks”）就是视图对象。
视图可以理解为一个受限制的（非原集合的）集合。（类比于数据库视图）

轻量级集合包装器

在 Arrays 类中有一个静态方法 —— asList 方法，这个方法作用是：将普通的 Java 数组包装成一个 List 集合。

例如：

String[] strings = new String[10];
strings[0] = "pby";
strings[1] = "pby1";
strings[2] = "pby2";
List<String> stringList = Arrays.asList(strings);

返回的对象不是一个 ArrayList 对象。它就是一个视图对象：

1. 这个对象带有底层数组的 get 和 set 方法。
2. 视图对象不能操作所有改变数组大小的方法：

   在调用这些方法的时候，程序会抛出一个 UnsupportedOperationException 异常；但是普通的 List 对象能够正常的调用改变数组大小的方法。

与 Arrays.asList 方法类似的另一个方法那就是在 Collections 中的 nCopies 方法。例如：

List<String> stringList = Collections.nCopies(100, "pby");

上面的代码将创建一个包含 100 个 "pby" 字符串的 List 集合对象。这样的操作优势在于存储代价很小，因为这个对象不能修改大小。

• 区分 Collections 类和 Collection 接口：Collections 类包含了很多实用的方法，这些方法的参数和返回值都是集合；

  【如“synchronizedCollection(Collection<T> c)”可用于：用普通集合实现一个同步集合】；

子范围

可以给很多的集合建立子范围视图。

例如，假设有一个集合对象list，要从中取出第10个~第19个元素，就可以使用subList方法来获得一个List集合对象的子范围视图：

List<String> list2 = list.subList(10, 19);

• Java SE 6 引人的NavigableSet接口赋予子范围操作更多的控制能力。

不可修改的视图

Collections还有几个方法，用于产生集合的不可修改视图。这些视图对现有的集合增加了一个运行时的检查。如果发现对集合进行修改的话(这里不仅仅是改变数组的大小，并且包括set之类的方法)，就会抛出一个异常，同时这个集合将保持未修改的状态。

可以使用如下8种方法来获得不可修改的视图：

1. Collections.unmodifiableCollection
2. Collections.unmodifiableList
3. Collections.unmodifiableSet
4. Collections.unmodifiableSortedSet
5. Collections.unmodifiableNavigableSet
6. Collections.unmodifiableMap
7. Collections.unmodifiableSortedMap
8. Collections.unmodifiableNavigableMap

每个方法都定义于一个接口。例如，Collections.unmodifiableList方法定义于List接口，与ArrayList、LinkedList或者任何实现了List接口的其他类一起协同工作。

• 由于视图只是包装了接口而不是实际的集合对象， 所以只能访问接口中定义的方法。

   unmodifiableCollection 方法（与本节稍后讨论的synchronizedCollection 和checkedCollection 方法一样）将返回一个集合， 它的equals 方法不调用底层集合的equals 方法。相反， 它继承了Object 类的equals 方法， 这个方法只是检测两个对象是否是同一个对象。如果将集或列表转换成集合， 就再也无法检测其内容是否相同了。视图就是以这种方式运行的， 因为内容是否相等的检测在分层结构的这一层上没有定义妥当。视图将以同样的方式处理hashCode 方法。
   然而，unmodifiableSet 类和unmodifiableList 类却使用底层集合的equals 方法和hashCode 方法。

同步视图

类库的设计者使用视图机制来确保常规集合的线程安全， 而不是实现线程安全的集合类。

例如， Collections 类的静态synchronizedMap方法可以将任何一个映射表转换成具有同步访问方法的Map：

Map<String, Employee> map = Collections.synchronizedMap(new HashMap<String, Employee>())；

受查视图

“受査”视图用来对泛型类型发生问题时提供调试支持。

例如，下面定义了一个安全列表“safeStrings”：

List<String> safeStrings = Collections.checkedList(strings，String.class);

ArrayList rawList = safeStrings;
rawList.add(new Date())；// checked list throws a ClassCastException

视图的 add 方法将检测插人的对象是否属于给定的类。如果不属于给定的类， 就立即抛出一个“ClassCastException”。这样做的好处是错误可以在正确的位置得以报告：

关于可选操作的说明

通常，视图有一些局限性，即可能只可以读、无法改变大小、只支持删除而不支持插人，这些与映射的键视图情况相同。如果试图进行不恰当的操作，受限制的视图就会抛出一个 UnsupportedOperationException。

在集合和选代器接口的API 文档中，许多方法描述为“可选操作” 。

相关方法：

java.util.Collections 1.2
static <E> Collection unmodifiableCollection(Collection<E> c)	构造一个集合视图；视图的更改器方法抛出一个 UnsupportedOperationException。
static <E> List unmodifiableList(List<E> c)
static <E> Set unmodifiableSet(Set<E> c)
static <E> SortedSet unmodifiableSortedSet(SortedSet<E> c)
static <E> SortedSet unmodifiableNavigableSet(NavigableSet<E> c) 8
static <K, V> Map unmodifiableMap（Map<K, V> c)
static <K, V> SortedMap unmodifiableSortedMap(SortedMap<K, V> c)
static <K, V> SortedMap unmodifiableNavigableMap(NavigableMap<K , V> c) 8
static <E> Collection<E> synchronizedCollection(Collection<E> c)	构造一个集合视图；视图的方法同步。
static <E> List synchronizedlist(List<E> c)
static <E> Set synchronizedSet(Set<E> c)
static <E> SortedSet synchronizedSortedSet(SortedSet<E> c)
static <E> NavigableSet synchronizedNavigableSet(NavigableSet<E> c) 8
static <K, V> Map<K, V> synchronizedMap(Map<K , V> c)
static <K, V> SortedMap<K , V> synchronizedSortedMap(SortedMap<K, V> c)
static <K, V> NavigableMap<K , V> synchronizedNavigableMap(NavigableMap<K, V> c) 8
static <E> Collection checkedCollection(Collection<E> c , Class<E> elementType)	构造一个集合视图：如果插入一个错误类型的元素， 视图的方法抛出一个 ClassCastException。
static <E> List checkedlist(List<E> c, Class<E> elementType)
static <E> Set checkedSet(Set<E> c, Class<E> e l ementType)
static <E> SortedSet checkedSortedSet(SortedSet<E> c , Class <E> elementType)
static <E> NavigableSet checkedNavigableSet(NavigableSet<E> c, Class<E> elementType) 8
static <K, V> Map checkedMap(Map<K, V> c, Class<K> keyType, Class<V> valueType)
static <K, V> SortedMap checkedSortedMap(SortedMap<K, V> c ,Class<K> keyType, Class<V> valueType)
static <K, V> NavigableMap checkedNavigableMap(NavigableMap<K , V> c, Class<K> keyType , Class<V> valueType) 8
static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> elementType) 8
static <E> List<E> nCopies(int n, E value)	构造一个对象视图，可以是一个包含 n 个相同元素的不可修改列表， 也可以是一个单元素集、列表或映射。
static <E> Set<E> singleton(E value)
static <E> List<E> singletonlist(E value)
static <K, V ＞阿ap<K, V> singletonMap(K key, V value)
static <E> List<E> emptylist()	生成一个空集合、映射或迭代器。
static <T> Set<T> emptySet()
static <E> SortedSet<E> emptySortedSet()
static NavigableSet<E> emptyNavigableSet()
static <K,V> Map<K, V> emptyMap()
static <K , V> SortedMap<K, V> emptySortedMap()
static <K,V> NavigableMap<K, V> emptyNavigableMap()
static <T> Enumeration<T> emptyEnumeration()
static <T> Iterator<T> emptyIterator()
static <T> ListIterator<T> emptyListIterator()
java.util.Arrays 1.2
static <E> List<E> aslist(E. .. array)	返回一个数组元素的列表视图。这个数组是可修改的，但其大小不可变。
java.util.List<E> 1.2
List<E> sublist(int firstIncluded, int firstExcluded)	返回给定位置范围内的所有元素的列表视图。
java.util.SortedSet<E> 1.2
SortedSet<E> subSet(E firstIncluded, E firstExcluded)	返回给定范围内的元素视图。
SortedSet<E> headSet(E firstExcluded)
SortedSet<E> tailSet(E firstIncluded)
java.util.NavigableSet<E> 6
NavigableSet<E> subSet(E from, boolean fromIncluded, E to, boolean toIncluded)	返回给定范围内的元素视图。boolean 标志决定视图是否包含边界。
NavigableSet<E> headSet(E to, boolean toIncluded)
NavigableSet<E> tailSet(E from, boolean fromIncluded)
SortedMap<K, V> subMap(K firstIncluded, K firstExcluded)	返回在给定范围内的键条目的映射视图。
SortedMap<K, V> headMap(K firstExcluded)
SortedMap<K, V> tailMap(K firstIncluded)
NavigableMap<K, V> subMap(K from, boolean fromIncluded, K to, boolean toIncluded)	返回在给定范围内的键条目的映射视图。boolean 标志决定视图是否包含边界。
NavigableMap<K, V> headMap(K from, boolean fromIncluded)
NavigableMap<K, V> tailMap(K to, boolean toIncluded)

算法

泛型集合接口有一个很大的优点， 即算法只需要实现一次。

排序与混排

Collections 类中的sort 方法可以对实现了List 接口的集合进行排序。

1. 这个方法假定列表元素实现了Comparable 接口。
2. 如果想采用其他方式对列表进行排序，可以使用List接口的sort方法并传入一个Comparator 对象。

sort方法对列表所采用的排序手段：将所有元素转人一个数组，对数组进行排序，然后，再将排序后的序列复制回列表。【？？？】

常用排序算法

Collections 类有一个算法shuffle, 其功能与排序刚好相反， 即随机地混排列表中元素的顺序。

相关方法：

java.util.Collections
static <T extends Comparable<? super T>> void sort( List<T> elements )	使用稳定的排序算法， 对列表中的元素进行排序。这个算法的时间复杂度是0(n logn), 其中n 为列表的长度。
static void shuffle( List<?> elements )	随机地打乱列表中的元素。这个算法的时间复杂度是0(n a(n)), n 是列表的长度，a(n)是访问元素的平均时间。
static void shuffle( List <?> elements , Random r )
java.util.List<E>
default void sort(Comparator<? super T> comparator )	使用给定比较器对列表排序。
java.util.Comparator<T>
static <T extends Comparable<? super T>> Comparator<T> reverseOrder( )	生成一个比较器， 将逆置 Comparable 接口提供的顺序。【？】
default Comparator<T> reversed( )	生成一个比较器， 将逆置这个比较器提供的顺序。【？】

二分查找

使用二分查找，集合必须是已排好序的。

相关方法：

java.util.Collections
static <T extends Comparable<? super T>> int binarySearch( List<T> elements , T key)	从有序列表中搜索一个键， 如果元素扩展了 AbstractSequentialList 类， 则采用线性查找，否则将采用二分查找。 这个方法的时间复杂度为0 (a(n) logn), n 是列表的长度，a(n) 是访问一个元素的平均时间。 这个方法将返回这个键在列表中的索引， 如果在列表中不存在这个键将返回负值i。 在这种情况下，应该将这个键插人到列表索引一i—l的位置上，以保持列表的有序性。
static <T> int binarySearch(List<T> elements, T key, Conparator<? super T> c)

简单算法

在 Collections 类中包含了几个简单且很有用的算法。

• 在 Java SE 8 增加了默认方法 Collection.removeIf 和 Collection.replaceAll，这两个方法需要提供 lambda 表达式来测试或转换元素。

  如：

  // 删除所有长度小于3的短词
  word.removeIf(w -> w.length() <= 3);
  
  // 把所有单词字母改为小写
  word.replaceAll(String::toLowerCase);
  

相关方法：

java.util.Collections
static <T extends Comparab1e<? super T>> T min(Collection<T> elements )	返回集合中最小的或最大的元素（为清楚起见， 参数的边界被简化了）。
static <T extends Comparable<? super T>> T max(Collection<T> elements )
static <T> min(Collection<T> elements, Comparator ? super T> c )
static <T> max (Collection<T> elements, Comparator ? super T> c )
static <T> void copy(List<? super T> to, List<T> from)	将原列表中的所有元素复制到目辱列表的相应位1上。目标列表的长度至少与原列表一样。
static <T> void fill(List<? super T> l， T value)	将列表中所有位置设置为相同的值。
static <T> boolean addAll(Collection<? super T> c, T . . . values ) 5.0	将所有的值添加到集合中。如果集合改变了， 则返回tme。
static <T> boolean replaceAll(List<T> l, T oldValue, T newValue) 1.4	用 newValue 取代所有值为oldValue 的元素。
static int indexOfSubList (List<?> l , List<?> s ) 1.4	返回 l 中第一个或最后一个等于 S 子列表的索引。 如果 l 中不存在等于S 的子列表， 则返回-1。 例如， l 为[s,t，a，r] , s 为[t, a, r], 两个方法都将返回索引1。
static int lastIndexOfSubList (List<?> l , List<?> s ) 1.4
static void swap(List<?> l , int i, int j) 1.4	交换给定偏移量的两个元素。
static void reverse(List<?> l)	逆置列表中元素的顺序。 例如， 逆置列表[t，a, r] 后将得到列表[r, a, t]。 这个方法的时间复杂度为O(n)，n 为列表的长度。
static void rotate(List<?> l, int d) 1.4	旋转列表中的元素， 将索引i 的条目移动到位置（i + d) % l.size()。 例如， 将列表[t， a, r] 旋转移2 个位置后得到[a, r，t]。 这个方法的时间复杂度为O(n) , n 为列表的长度。
static int frequency(Collection<?> c, Object o) 5.0	返回 c 中与对象o 相同的元素个数。
boolean disjoint (Collection<?> cl, Collection<?> c2 ) 5.0	如果两个集合没有共同的元素， 则返回true。
java.util.Collection<T>
default boolean removeIf (Predicate<? super E> filter ) 8	删除所有匹配的元素。
java.util.List<E>
default void replaceAll(UnaryOperator<E> op) 8	对这个列表的所有元素应用这个操作。

批操作

集合中的“removeAll()”、“retainAll()”、“addAll()”、“clear()”等方法。

集合与数组的转换

数组 -> 集合

如果需要把一个数组转换为集合，Arrays.asList 包装器可以达到这个目的。例如：

String[] values = . . .;
HashSet<String> staff = new HashSet<>(Arrays.asList(values));

集合 -> 数组

从集合得到数组会更困难一些。当然，可以使用toArray 方法：

Object[] values = staff.toArray();

• toArray 方法返回的数组是一个 Object[] 数组，不能改变它的类型。

  String[] values = (String[]) staff.toArray()；  // Error! 不能使用强制类型转换！
  

实际上， 必须使用 toArray 方法的变体形式：

1. 提供一个所需类型而且长度为 0 的数组。

   String[] values = staff.toArray(new String[0]);
   

2. 或构造一个指定大小的数组：

   String[] values = staff.toArray(new String[staff.size()]);
   

【？？？】

你可能奇怪为什么不能直接将一个 Class 对象（如String.class) 传递到 toArray 方法。 —— 原因是这个方法有“ 双重职责”，不仅要填充一个已有的数组（如果它足够长)，还要创建一个新数组。

遗留的集合

Hashtable

• 作用与 HashMap 一样，但继承自抽象类 Dictionary ，而实现了 Map 接口（HahsMap 继承自AbstractMap，实现了Map）

  public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {
  
  // （Dictionary 类已过时，新的实现类应该实现Map接口）
  public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  

• HashTable 的方法都是同步的（与Vector类似，方法使用Synchronized修饰）
• 没有同步性要求应该使用 HashMap，而并发访问应该使用 ConcurrentHashMap

  Collections 类中存在一个静态方法：synchronizedMap()，同样可以创建一个线程安全的Map对象；

  ConcurrentHashMap 的实现更加精细，同步操作精确控制到桶

枚举（Enumeration）

遗留集合使用 Enumeration 接口对元素序列进行遍历。Enumeration 接口有两个方法，即 hasMoreElements 和 nextElement。这两个方法与 Iterator 接口的 hasNext 方法和 next 方法十分类似。（可以看作遗留集合的迭代器？）

例如，Hashtable 类的 elements 方法将产生一个用于描述表中各个枚举值的对象：

Enumeration<Employee> e = staff.elements();
whi1e(e.hasMoreElements())
{
    Employee e = e.nextElement();
}

静态方法Collections.enumeration 将产生一个枚举对象，枚举集合中的元素。例如：

List<InputStream> streams = . . .;
SequenceInputStream in = new SequenceInputStream(Collections.enumeration(streams)) ;
// the SequencelnputStream constructor expects an enumeration

传递集合要比传递迭代器更为明智。集合对象的用途更大。当接受方如果需要时，总是可以从集合中获得迭代器，而且，还可以随时地使用集合的所有方法。

相关方法：

java.util.Enumeration<E>
boolean hasMoreElements( )	如果还有更多的元素可以査看， 则返回true。
E nextElement( )	返回被检测的下一个元素。 如果 hasMoreElements( ) 返回 false, 则不要调用这个方法。
java.util.HashTable<K, V>
Enumeration<K> keys( )	返回一个遍历散列表中键的枚举对象。
Enumeration<V> elements( )	返回一个遍历散列表中元素的枚举对象。
java.util.Vector<E>
Enumeration<E> elements( )	返回遍历向量中元素的枚举对象。

属性映射（Properties）

属性映射（property map) 是一个类型非常特殊的映射结构。它有下面3 个特性：

1. 键与值都是字符串。
2. 表可以保存到一个文件中， 也可以从文件中加载。
3. 使用一个默认的辅助表。

实现属性映射的Java 平台类称为Properties。

• Properties 类使用 HashTable 实现：

  public class Properties extends Hashtable<Object,Object> {
  

相关方法：

java.util.Properties
Properties()	创建一个空的属性映射。
Properties(Properties defaults)	创建一个带有一组默认值的空的属性映射。
String getProperty(String key)	获得属性的对应关系；返回与键对应的字符串。如果在映射中不存在，返回默认表中与这个键对应的字符串。
String getProperty(String key, String defaultValue)	获得在键没有找到时具有的默认值属性；它将返回与键对应的字符串，如果在映射中不存在，就返回默认的字符串。
void load(InputStream in)	从 InputStream 加载属性映射。
void store(OutputStream out, String commentstring)	把属性映射存储到 OutputStream。

栈（Stack）

从 1.0 版开始，标准类库中就包含了 Stack 类，其中有大家熟悉的 push 方法和 pop 方法。但是，Stack 类扩展自 Vector 类，从理论角度看，Vector 类并不太令人满意，它可以让栈使用不属于栈操作的 insert 和 remove 方法，即可以在任何地方进行插入或删除操作，而不仅仅是在栈顶。

相关方法：

java.util.Stack<E>
E push(E item)	将 item 压人桟并返回 item。
E pop()	弹出并返回栈顶的 item。 如果栈为空，请不要调用这个方法。
E peek()	返回栈顶元素，但不弹出。 如果栈为空，请不要调用这个方法。

位集（BitSet）

Java 平台的BitSet 类用于存放一个位序列（它不是数学上的集， 称为位向量或位数组更为合适)。如果需要高效地存储位序列（例如，标志）就可以使用位集。由于位集将位包装在字节里， 所以，使用位集要比使用Boolean 对象的ArrayList 更加高效。

“Eratosthenes 筛子”

   作为位集应用的一个示例，这里给出一个采用“ Eratosthenes 筛子” 算法查找素数的实现（素数是指只能被1 和本身整除的数， 例如2、3 或5,“ Eratosthenes 筛子” 算法是最早发现的用来枚举这些基本数字的方法之一)。 这并不是一种查找素数的最好方法， 但是由于某种原因，它已经成为测试编译程序性能的一种流行的基准。（这也不是一种最好的基准测试方法，它主要用于测试位操作。）
   在此，将尊重这个传统，并给出实现。其程序将计算2 - 2 000 000 之间的所有素数（一共有148 933 个素数， 或许不打算把它们全部打印出来吧)。
   这里并不想深人程序的细节， 关键是要遍历一个拥有200 万个位的位集。首先将所有的位置为“ 开” 状态，然后，将已知素数的倍数所对应的位都置为“ 关” 状态。经过这个操作保留下来的位对应的就是素数。

相关方法：

java.util.BitSet
BitSet( int initialCapacity )	创建一个位集。
int length( )	返回位集的“ 逻辑长度”， 即1 加上位集的最高设置位的索引。
boolean get( int bit )	获得一个位。
void set( int bit )	设置一个位。
void clear ( int bit )	清除一个位。
void and( BitSet set )	这个位集与另一个位集进行逻辑“AND”。
void or( BitSet set )	这个位集与另一个位集进行逻辑“OR”。
void xor( BitSet set )	这个位集与另一个位集进行逻辑“X0R”。
void andNot( BitSet set )	清除这个位集中对应另一个位集中设置的所有位。