核心技术：集合

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<b
{
   boolean add(E element);
   Iterator<E> iteratorQ;
   ...
}

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.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 方法时返回的元素；

如：

1. 删除集合首个元素：

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

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

   it.remove();
   it.next0；
   it.remove();
   
   // 而非
   // it.remove();
   // it.remove();
   

泛型使用方法

• 由于Collection 与Iterator 都是泛型接口，可以编写操作任何集合类型的实用方法。
• Java 类库提供了一个类AbstractCollection，它将基础方法size和iterator抽象化了，但是提供了例行方法。

  所以，一个具体的集合类可以扩展AbstractCollection 类了（实际上也是这样的）

  然而，这种“伴随类”并不是最好的方式，在原接口中将方法定义为“默认方法”会更好。

java.util.Collection<E>

1. Iterator < E> iterator()

   返回一个用于访问集合中每个元素的迭代器。

2. int size()

   返回当前存储在集合中的元素个数。

3. boolean isEmpty()

   如果集合中没有元素， 返回true。

4. boolean contains(Object obj)

   如果集合中包含了一个与obj 相等的对象， 返回true。

5. boolean containsAl 1(Collection<?> other)

   如果这个集合包含other 集合中的所有元素， 返回trueo

6. boolean add(Object element)

   将一个元素添加到集合中。如果由于这个调用改变了集合，返回true。

7. boolean addAl1(Col1ection<? extends E> other)

   将other 集合中的所有元素添加到这个集合。如果由于这个调用改变了集合，返回true。

8. boolean remove(Object obj)

   从这个集合中删除等于obj 的对象。如果有匹配的对象被删除， 返回true。

9. boolean removeAl 1(Col 1ection<?> other)

   从这个集合中删除other 集合中存在的所有元素。如果由于这个调用改变了集合，返回true。

10. default boolean removelf(Predicate<? super E> filter)8

    从这个集合删除filter 返回true 的所有元素。如果由于这个调用改变了集合，则返回true。

11. void clear()

    从这个集合中删除所有的元素。

12. boolean retainAl1(Collection<?> other)

    从这个集合中删除所有与other 集合中的元素不同的元素。如果由于这个调用改变了集合， 返回true。

13. Object[]toArray()

    返回这个集合的对象数组。

14. <T> T[]toArray(T[]arrayToFi11)

    返回这个集合的对象数组。如果arrayToFill 足够大，就将集合中的元素填入这个数组中。剩余空间填补null; 否则，分配一个新数组，其成员类型与arrayToFill的成员类型相同，其长度等于集合的大小，并填充集合元素。

java.util.Iterator<E>

1. boolean hasNext()

   如果存在可访问的元素， 返回true。

2. E next()

   返回将要访问的下一个对象。如果已经到达了集合的尾部， 将拋出一个NoSuchElementException。

3. 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> 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来实现同步锁；

散列集（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 是比较合理的；

常用方法

jjava.util.HashSet<E>

• HashSet ( )

  构造一个空散列表。

• HashSet (Col 1ection<? extends E> elements )

  构造一个散列集， 并将集合中的所有元素添加到这个散列集中。

• HashSet ( int initialCapacity)

  构造一个空的具有指定容量（桶数）的散列集。

• HashSet ( int initialCapacity , float 1oadFactor )

  构造一个具有指定容量和装填因子（一个0.0 ~ 1.0 之间的数值， 确定散列表填充的百分比， 当大于这个百分比时， 散列表进行再散列）的空散列集。

java.Iang.Object

• int hashCode( )

  返回这个对象的散列码。散列码可以是任何整数，包括正数或负数。equals 和hashCode的定义必须兼容，即如果x.equals(y) 为true, x.hashCodeO 必须等于y.hashCodeO。

树集（TreeSet）

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

• 使用树集，元素必须实现 Comparable 接口。
• 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(Col 1ection<? extends E> elements)
• TreeSet(SortedSet<E> s)

  构造一个树集， 并增加一个集合或有序集中的所有元素（对于后一种情况，要使用同样的顺序)。

java.util.SortedSet<E>

• Comparator<? super E> comparator()

  返回用于对元素进行排序的比较器。如果元素用Comparable 接口的compareTo方法进行比较则返回null。

• E firstO
• E 1ast()

  返回有序集中的最小元素或最大元素。

java.util.NavigableSet<E>

• E higher(E value)
• E 1ower(E value)

  返回大于value 的最小元素或小于value 的最大元素，如果没有这样的元素则返回null。

• E cei1ing(E value)
• E floor(E value)

  返回大于等于vaiue 的最小元素或小于等于value 的最大元素， 如果没有这样的元素则返回null。

• E pollFirst()
• E pol1Last()

  删除并返回这个集中的最大元素或最小元素， 这个集为空时返回null。

• Iterator<E> descend *ngIterator()

  返回一个按照递减顺序遍历集中元素的迭代器。