一、综述

     java集合框架定义了几个接口，这些接口决定了collection类的基本特性。不同的是，具体类仅仅是提供了标准接口的不同实现，如图，

colls-coreInterfacesjava集合框架接口图

    从图可知，java集合类的主要是由两个接口派生而出——Collection和Map，Collection和Map是集合框架的根接口。其介绍如下：

  • Collection — 位于集合框架的顶层，一个Collection代表一组Object，即Collection的元素（Elements）。有的Collection（子类）允许有相同的元素出现而有的就不行，有的Collection（子类）支持排序而有的则不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List、Set和Queue。

  • Set — 扩展了Collection的集合，集合中的元素不可以重复，即任意的两个元素e1和e2都有e1.equals(e2) == false。访问集合中的元素只能根据元素本身来访问。

  • List — 扩展了Collection的集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。

  • Queue — 提供了队列的实现，除了基本的Collection操作外，队列还提供其他的插入、提取和检查操作。

  • Map — 以Key-value对形式保存元素，访问时只能根据每项元素的key来访问其value。key必须唯一，value的值可以重复。

尚未列出的两个接口是Set和Map的排序版本：

  • SortedSet — 扩展Set，集合元素按升序排列

  • SortedMap — 扩展Map，以便关键字按升序排列

    另外，除了上面提到的接口，java集合使用Comparator、Iterator和ListIterator等接口，这些接口将会陆续讲解，简单来说，Comparator接口定义了两个对象的比较方法，即Iterator和ListIterator接口集合里的对象。同时，为了提供集合最大的灵活性，每个集合接口里的方法都是可修改的 —— 一个给定的implemention不一定支持所有的操作（方法）。当调用了不支持的方法时，将引发一个UnsupportedOperationException异常。

二、Collection接口

    Collection是集合框架的基础，它声明了所有集合都将拥有的核心方法。一个Collection代表一组Object，即Collection的元素（Elements）。所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后 一个构造函数允许用户复制一个Collection。如下是Collection接口的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public  interface  Collection<E>  extends  Iterable<E> {
     // 基本方法
     int  size();
     boolean  isEmpty();
     boolean  contains(Object element);
     boolean  add(E element); //可选
     boolean  remove(Object element); //可选
     Iterator<E> iterator();
     // 批量操作
     boolean  containsAll(Collection<?> c);
     boolean  addAll(Collection<?  extends  E> c);  //可选
     boolean  removeAll(Collection<?> c); //可选
     boolean  retainAll(Collection<?> c); //可选
     void  clear(); //可选
     // 数组操作
     Object[] toArray();
     <T> T[] toArray(T[] a);
}


附：“可选”代表了其子类（或子接口）可以有选择的去实现，即可以不提供此操作（方法）.

    Collection接口定义了操作一组objects的基本方法，如：集合里有多少个objects（size，isEmpty），集合是否包含某个object（contain），从集合里增加或删除一个object（add，remove），返回集合的迭代（iterator）

遍历Collection

遍历Collection，有两种方法（foreach循环，Iterator接口）。

    如下演示了使用foreach循环来输出集合里的元素：

1
2
3
for  (Object o : collection){
     System.out.println(o);
}


      Iterator接口如下：

1
2
3
4
5
public  interface  Iterator<E> {
     boolean  hasNext(); //如果仍有元素可以迭代，则返回 true。
     E next();       //返回迭代的下一个元素。
     void  remove();  //可选操作，移除当前迭代的object
}



   在需要进行如下情况时，应使用Iterator接口迭代collection，而不选foreach方法:

   1.移除当前object。foreach方法隐藏了迭代器，故而不能使用remove（）方法，同时也不能使用foreach过滤collection集合

   2.多个collection的迭代

    如下演示如何使用Iterator过滤任意collection—在遍历集合时，移除指定object：

1
2
3
4
5
static  void  filter(Collection<?> c) {
     for  (Iterator<?> it = c.iterator(); it.hasNext(); )
         if  (!cond(it.next()))
             it.remove();
}



Collection的批量操作

批量操作操纵的是整一个集合，同时批量操作的效率的较低。

  • containsAll — 如果此 collection 包含指定 collection 中的所有元素，则返回 true。

  • addAll —  将指定collection中的所有元素添加到此collection

  • removeAll — 移除此 collection 中那些也包含在指定 collection 中的所有元素

  • retainAll — 仅保留此 collection 中那些也包含在指定 collection 的元素，换句话说，移除此 collection 中未包含在指定 collection 中的所有元素。

  • clear — 移除此 collection 中的所有元素

    以上批量操作的方法，如果成功修改此collection，都会返回true。如下：从集合c里删除所有指定的元素e（一个或多个），

  c.removeAll(Collections.singleton(e));
     更具体一点的就是，你可以删除集合c里所有的null元素
     c.removeAll(Collections.singleton(null));
     附：Collections.singleton是一个静态工厂方法，返回一个只包含指定对象的不可变的set

Collection的数组操作

Collection的toArray（）方法会返回在一个数组，这个数组包含了collection集合里的元素，数组长度取决于collection集合元素的个数。如下，c为一个Collection，

    Object[] a = c.toArray();//返回的是一个object数组

   如果已知集合里元素的类型，假设所有元素都为String类型（Collection<String>），如下操作可以返回一个String数组：

   String[] a = c.toArray(new String[0]);

三、Set接口

    一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。因此，Set构造函数里的Collection参数不能包含相同的object。当两个Set对象所包含的元素都相同，则认为这两个Set等同的。

    请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)==true将导致Set的行为不确定。

    某些 set 实现对其所包含的元素有所限制。例如，某些实现禁止包含 null 元素，而某些则对其元素的类型所有限制。试图添加不合格的元素会抛出未经检查的异常，通常是 NullPointerException 或 ClassCastException。试图查询不合格的元素是否存在可能会抛出异常，也可能简单地返回 false.

    Set接口的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public  interface  Set<E>  extends  Collection<E> {
     // 基本方法
     int  size();
     boolean isEmpty();
     boolean contains( Object  element);
     boolean add(E element);  // 可选
     boolean remove( Object  element); // 可选
     Iterator<E> iterator();
     // 批量操作
     boolean containsAll(Collection<?> c);
     boolean addAll(Collection<?  extends  E> c); // 可选
     boolean removeAll(Collection<?> c);    // 可选
     boolean retainAll(Collection<?> c); // 可选
     void  clear(); // 可选
     // 数组操作
     Object [] toArray();
     <T> T[] toArray(T[] a);
}

    java提供了三种Set的常用实现:HashSet，TreeSet和LinkedHashSet，

  • HashSet — 以哈希表的形式存储集合元素，它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。可以包含 null 元素。

  • TreeSet — 以红黑树的形式存储集合元素，使用元素的自然顺序对元素进行排序。整体性能比HashSet低

  • LinkedHashSet — 具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现，按照元素的插入顺序进行排序。可以包含null元素。

   在这里，给出一个简单而是用的Set用法：从一个可能含有重复元素里的集合c，创建一个消除重复元素的集合noDups:(在下面的FindDups有具体的演示）

    Collection<Type> noDups = new HashSet<Type>(c);

   如果在删除了重复元素的基础上，还要保留原来元素的顺序的，可以选择使用LinkedHashSet，

    Collection<Type> noDups = new LinkedHashSet<Type>(c);    这个LinkedHashSet的用法，也可以用如下的泛型方法来代替：
1
2
3
public  static  <E> Set<E> removeDups(Collection<E> c) {
     return  new  LinkedHashSet<E>(c);
} 

Set的基本操作

    size（）返回集合元素的个数，isEmpty（）判断集合是否为空；add（）方法往集合添加一个object，如果Set集合里尚未包含这个元素，则可顺利添加，否则返回false；类似的，remove方法可以删除Set集合里存在的一个元素，如果不存在则返回false。iterator（）返回集合的迭代。

    Demo：FindDups利用Set的基本方法，输出String数组里重复的元素，

1
2
3
4
5
6
7
8
9
10
public  class  FindDups {
     public  static  void  main(String[] args) {
         String[] str = { "d" , "b" , "c" , "a" , "d" };
         Set<String> s =  new  HashSet<String>();
         for  (String a : str)
             if  (!s.add(a))
                 System.out.println( "重复的元素: "  + a);
         System.out.println(s.size() +  " 个不同的元素: "  + s);
     }
}


其输出如下：image

      在FindDups里使用HashSet— 一个没有排序功能的Set，如果要实现元素排序的输出，可以选择使用TreeSet作为Set的实现。

      Set<String> s = new TreeSet<String>();

      其输出如下：image

Set批量操作

collection里的批量操作很是适用于Set，具体批量操作可参考collection的批量操作。在这里演示一下如何求两个Set集合的并集、交集和差集：

1
2
3
4
5
6
7
8
9
// 并集
Set<Type> union =  new  HashSet<Type>(s1);
union.addAll(s2);
// 交集
Set<Type> intersection =  new  HashSet<Type>(s1);
intersection.retainAll(s2);
// 差集
Set<Type> difference =  new  HashSet<Type>(s1);
difference.removeAll(s2);


    在此，可以回顾一下FindDups，假设你需要找出collection里有哪些元素只出现了一次，哪些元素出现了多次，应该如何实现呢？？？可以设计两个Set，一个包含了只出现一次的元素，另外一个包含了哪些重复出现的元素，具体的实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public  class  FindDups2 {
     public  static  void  main(String[] args) {
         String[] str = { "d" , "b" , "c" , "a" , "d" };
         Set<String> uniques =  new  HashSet<String>();
         Set<String> dups =  new  HashSet<String>();
         for  (String a : str){
             if  (!uniques.add(a))
                 dups.add(a);
         }
         // 移除所有的重复出现的元素
         uniques.removeAll(dups);
         System.out.println( "只出现一次的元素:    "  + uniques);
         System.out.println( "重复出现的元素: "  + dups);
     }
}

其输出如下：image

Set的数组操作

   Set的数组操作和collection的数组一致，并没有特别的用法，详情可看Collection的数组操作。

四、List接口

   List是一个有序的collection（有时也叫做“序列”），可以包含重复的元素。除了从Collection接口继承过来的方法，List也提供了如下操作（方法）。

  • 索引访问 — 根据元素的索引来操纵元素

  • 搜索— 搜索指定元素并返回其索引

  • Iteration — 继承了Iterator ，充分利用了List的索引优势

  • 截取 — 截取List任意范围的元素

List接口代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public  interface  List<E>  extends  Collection<E> {
     // 索引访问
     E get( int  index);
     E set( int  index, E element); //可选
     boolean  add(E element);  //可选
     void  add( int  index, E element); //可选
     E remove( int  index); //可选
     boolean  addAll( int  index, Collection<?  extends  E> c); //可选
     // 搜索
     int  indexOf(Object o);
     int  lastIndexOf(Object o);
     // 迭代器
     ListIterator<E> listIterator();
     ListIterator<E> listIterator( int  index);
     // 截取List
     List<E> subList( int  from,  int  to);
}


   javat提供了两个List的常用实现：ArrayList和LinkedList。在搜索频繁的情况下，选择使用ArrayList；插入删除频繁的情况下，选择使用ListArray。值得提一下的的是，从java2开始，Vector向量改进为可以实现List。

Collection操作

List从Collection那继承过来的方法，它的使用方式和Collection是一致的，如果不太熟悉Collection操作，可以看一下Collection接口。remove（）方法会删除List集合里的第一个元素，add（）和addAll（）方法从List的尾部依次添加元素，所以下面的代码会连接两个List：

   list1.addAll(list2);

   如果需要新建一个List3来连接List1和List2，可以这样做：

   List<Type> list3 = new ArrayList<Type>(list1); 
   list3.addAll(list2);

   和Set接口一样，如果两个List所包含的元素一致，则认为这两个List是等同的。

List的索引访问与搜索

    List的索引访问与搜索和数组的操作基本相似，如下演示了交换List里的两个元素的位置

1
2
3
4
5
public  static  <E>  void  swap(List<E> a,  int  i,  int  j) {
     E temp = a.get(i);
     a.set(i, a.get(j));
     a.set(j, temp);
}

   利用这个元素位置交换的性质,我们可以模拟扑克牌的洗牌操作,如下

1
2
3
4
public  static  void  shuffle(List<?> list, Random rnd) {
     for  ( int  i = list.size(); i >  1 ; i--)
         swap(list, i -  1 , rnd.nextInt(i));
}

   利用随机数的性质,使洗牌这一操作对每一位玩家来说都是公平的。而这个洗牌shuffle的方法，其实包含在Collections类里，如下代码演示了随机输出集合里各个元素（发牌）：

1
2
3
4
5
6
7
8
9
10
11
public  class  Shuffle {
     public  static  void  main(String[] args) {
         String[] str = { "a" , "b" , "c" , "d" , "e" , "f" }; //可以选择凑够52张牌
         List<String> list =  new  ArrayList<String>();
         for  (String a : str){
             list.add(a);
         }
         Collections.shuffle(list,  new  Random());
         System.out.println(list);
     }
}

其输出如下：image（因为是随机输出的，所以每一次运行的结果都会不一样。）

   附：事实上，还可以采取一种更为快捷简单的方法，使用Arrays提供的静态工厂方法asList：

1
2
3
4
5
6
7
8
public  class  Shuffle2 {
     public  static  void  main(String[] args) {
     String[] str = { "a" , "b" , "c" , "d" , "e" , "f" }; //可以选择凑够52张牌
         List<String> list = Arrays.asList(str);
         Collections.shuffle(list);
         System.out.println(list);
     }
}

迭代器Iterators

List提供了一个功能更为丰富的迭代器ListIterator，ListIterator，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。ListIterator 没有当前元素；它的光标位置 始终位于调用 previous() 所返回的元素和调用 next() 所返回的元素之间。长度为 n 的列表的迭代器有 n+1 个可能的指针位置（如图，长度为4的列表的迭代器有5个可能的指针位置）。

colls-fivePossibleCursor

ListIterator接口的代码如下：

1
2
3
4
5
6
7
8
9
10
11
public  interface  ListIterator<E>  extends  Iterator<E> {
     boolean  hasNext();
     E next();
     boolean  hasPrevious();
     E previous();
     int  nextIndex(); //返回对 next 的下一个元素的索引。
     int  previousIndex(); //返回对 previous 的上一个元素的索引
     void  remove();  //可选
     void  set(E e);  //可选
     void  add(E e);  //可选
}

   如下代码演示了如何反向迭代列表元素：

1
2
3
4
for  (ListIterator<Type> it = list.listIterator(list.size()); it.hasPrevious(); ) {
     Type t = it.previous();
     ...
}

hasNext, next, 和remove方法的用法和原来的Iterator的用法一致，nextIndex和previousIndex通常用于记录某个搜索到的元素的位置或者用于创建一个元素位置一致的新ListIterator。如果指针位置在第一个元素之前调用previousIndex（）方法，会返回-1；类似的，如果指针位置在最后一个元素之后调用nextIndex（）方法，会返回List.size。更为详细的讲解， 可以参考一下List.indexOf方法的实现：

1
2
3
4
5
6
7
public  int  indexOf(E e) {
     for  (ListIterator<E> it = listIterator(); it.hasNext(); )
         if  (e ==  null  ? it.next() ==  null  : e.equals(it.next()))
             return  it.previousIndex();
     // 元素不存在
     return  - 1 ;
}


 ListIterator接口提供了两种更新列表的方法—set和add。set(E e)用指定元素替换 next 或 previous 返回的最后一个元素。如下代码演示了如何用另一个值替换列表里得指定值：

1
2
3
4
5
public  static  <E>  void  replace(List<E> list, E val, E newVal) {
     for  (ListIterator<E> it = list.listIterator(); it.hasNext(); )
         if  (val ==  null  ? it.next() ==  null  : val.equals(it.next()))
             it.set(newVal);
}


   这个Demo里只需要比较val和it.next是否相同就行了，同时需要判断null，防止出现NullPointerException。add(E e)会在指针位置的前面插入一个元素。如下Demo演示了用一组数据替换List里的指定的值：

1
2
3
4
5
6
7
8
9
public  static  <E>  void  replace(List<E> list, E val, List<?  extends  E> newVals) {
         for  (ListIterator<E> it = list.listIterator(); it.hasNext();) {
             if  (val ==  null  ? it.next() ==  null  : val.equals(it.next())) {
                 it.remove();
                 for  (E e : newVals)
                     it.add(e);
             }
         }
     }

List的截取操作

     List的截取操作，subList(int fromIndex, int toIndex)，截取原List第fromIndex位到第toIndex位的元素（新List包含第fromIndex位，不包含toIndex位，用集合表示为[fromIndex,toIndex]。注意的是，返回的新List还是原List的一部风，在新List所做的改变，同时也会改变原List。

   任和需要List对象的操作都可以看成是对其子List的一系列操作。举个例子，如下代码可删除List指定范围里的元素：

   list.subList(fromIndex, toIndex).clear();

   类似地，可以这样搜索List表里的指定元素：

    
1
2
int  i = list.subList(fromIndex, toIndex).indexOf(object);
int  j = list.subList(fromIndex, toIndex).lastIndexOf(object); 
    注：如上搜索指定元素的方法，返回的字表的索引值，而不是原List的索引值。

任意一个操作List的多肽算法，如replace和shuffle方法，都是与字表打交道的。这里给出一个使用subList的多肽方法，使用这个方法来处理经典发扑克牌的问题。首先，先假设只给一个人发牌（hand），扑克牌堆用deck表示，那么发n张牌就可以看做从deck表的尾部截取n个元素的子List。代码如下：

1
2
3
4
5
6
7
public  static  <E> List<E> dealHand(List<E> deck,  int  n) {
         int  deckSize = deck.size(); //扑克牌的（剩余）张数
         List<E> handView = deck.subList(deckSize - n, deckSize);
         List<E> hand =  new  ArrayList<E>(handView); //发给这个人n张牌
         handView.clear(); //已发的牌，需要从deck里删除
         return  hand;
     }


   注意到了，我们是从deck（List）的尾端截取的。对多数List的实现来说，如ArrayList，从尾端移除元素比从头部移除元素的效率好。接着，我们来看一下如何给n个人发牌（这里假设有52张牌）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public  class  Deal {
     public  static  void  main(String[] args) {
         // 52张扑克牌
         String[] suit =  new  String[] {  "黑桃" ,  "红心" ,  "梅花" ,  "方块"  };
         String[] rank =  new  String[] {  "A" ,  "2" ,  "3" ,  "4" ,  "5" ,  "6" ,  "7" ,  "8" ,  "9" ,  "10" ,  "J" ,  "Q" ,  "K"  };
         // 初始化deck列表
         List<String> deck =  new  ArrayList<String>();
         for  ( int  i =  0 ; i < suit.length; i++) {
             for  ( int  j =  0 ; j < rank.length; j++) {
                 deck.add(suit[i] + rank[j]);
             }
         }
         dealing(deck,  4 ,  13 );  // 4个玩家，每个玩家13张牌
     }
     //发牌，共有numHands玩家，每个玩家有cardsPerPerson张牌
     public  static  <E>  void  dealing(List<E> deck,  int  numHands,  int  cardsPerPerson) {
         // 洗牌
         Collections.shuffle(deck);
         if  (numHands * cardsPerPerson > deck.size()) {
             System.out.println( "玩家太多，扑克牌不足" );
             return ;
         }
         for  ( int  i =  0 ; i < numHands; i++) {
             System.out.println(dealHand(deck, cardsPerPerson));
         }
     }
     public  static  <E> List<E> dealHand(List<E> deck,  int  n) {
         int  deckSize = deck.size();
         List<E> handView = deck.subList(deckSize - n, deckSize);
         List<E> hand =  new  ArrayList<E>(handView);
         handView.clear();
         return  hand;
     }
}


其输出如下：image（因为是随机发牌的，所以每次运行的结果都会不一样）

List 算法

    类Collections提供的多数多肽方法都适用于List，在这里给出这些算法概览（以后会详谈）：

  • sort — 使用合并排序算法排序List，默认为升序排列。

  • shuffle — 使用随机源对指定列表进行置换。（洗牌）.

  • reverse — 反转指定列表中元素的顺序。

  • rotate — 根据指定的距离轮换指定列表中的元素。

  • swap — 交换指定位置上的元素

  • replaceAll — 使用一个值替换列表中出现的所有某一指定值。

  • fill — 使用指定元素替换列表中的所有元素。

  • copy — 将所有元素从一个列表复制到另一个列表。

  • binarySearch — 使用二分搜索法搜索指定列表，以获得指定对象。

  • indexOfSubList — 返回指定列表中第一次出现指定目标列表的起始位置；如果没有出现这样的目标，则返回 -1。

  • lastIndexOfSubList — 返回指定源列表中最后一次出现指定目标列表的起始位置；如果没有出现这样的目标，则返回 -1。

   最后附上两张经典的collection图，希望可以给你带来一定的 帮助，感谢你的浏览。

201203102245165206

201203102245182566