集合（上）

2019-05-04 09:39:41来源：博客园阅读 ()

传统的容器(数组)在进行增、删等破坏性操作时，需要移动元素，可能导致性能问题；同时添加、删除等算法和具体业务耦合在一起，增加了程序开发的复杂度。Java集合框架提供了一套性能优良、使用方便的接口和类，它们位于java.util包中。

1 Collection 接口

Collection是java集合框架(collection-frame)中的顶层接口。Collection接口是一个容器，容器中只能存储引用数据类型，建议存同一类型的引用类型，方便后续遍历等操作。容器中的元素可以是有序的、可重复的，称为List接口；也可能是无序的、唯一的，称为Set接口。

1.1 集合常用方法

public static void main(String[] args) {
       
       /**
        * 增:add/addAll
        * 删:clear/remove/removeAll/retainAll
        * 改:
        * 查:contains/containsAll/isEmpty/size
        */
       
       Collection c1 = new ArrayList();
       
       // 追加
       c1.add("apple"); // Object object = new String("apple");
       // c1.add(1);         // Object object = new Integer(1); 
       c1.add("banana");
       System.out.println(c1);
       
       // 追加一个集合 
       Collection c2 = new ArrayList();
       c2.add("java");
       c2.add("c++");
       c1.addAll(c2);
       System.out.println(c1);
       
       System.out.println(c1.contains("apple"));
       c2.add("js");
       System.out.println(c1.containsAll(c2));
       // c1.clear();
       System.out.println(c1.isEmpty());
       // 返回集合元素的个数
       System.out.println(c1.size());
       
       System.out.println(c1.equals(c2));        
}

1.3 集合的遍历

Iterable 是一个可遍历的接口，集合接口继承于它，集合支持快速遍历。

for (Object item : c1) {
    System.out.println(item.toString());
}

快速遍历的本质：

Collection 继承 Iterable 接口，表示集合支持快速遍历。Iterable 接口定义了一个方法iterator()用于获取集合的迭代器，是一个 Iterator 接口类型，iterator()内部返回一个实现类实现类 Iterator 接口。这个实现类一定具有 hasNext 和 next 方法用于判断是否有下一个元素和获取下一个元素。快速遍历就是基于迭代器工作的。

public static void main(String[] args) {
       
       Collection c1 = new ArrayList();
       c1.add("apple");
       c1.add("banana");
       c1.add("coco");
       
       // 快速遍历
       // for-each
       // Object 表示元素类型 
       // item表示迭代变量
       // c1表示集合
       for (Object item : c1) {
           System.out.println(item.toString());
       }
       
       // 方法1
       Iterator it = c1.iterator();
       while(it.hasNext()) {
           Object item = it.next();
           System.out.println(item.toString());
       }
       
       // 方法2（推荐）
       for(Iterator it2=c1.iterator();it2.hasNext();) {
           Object item = it2.next();
           System.out.println(item.toString());
       }    
}

查看源码可以看到 next 方法的实现

@SuppressWarnings("unchecked")
       public E next() {
           checkForComodification();
           int i = cursor;
           if (i >= size)
               throw new NoSuchElementException();
           Object[] elementData = ArrayList.this.elementData;
           if (i >= elementData.length)
               throw new ConcurrentModificationException();
           cursor = i + 1;
           return (E) elementData[lastRet = i];
       }

iterator 方法会返回一个私有类 Itr 的实例，该类中定义了一个 cursor 变量，初始值为 0，表示当前”光标“指向的元素索引；定义了一个 lastRet 变量初始值为 -1，表示上一个遍历过的元素的索引。每次使用 next 后，将 cursor 赋给 i ，光标 cursor 后移一位，同时返回当前 i 指向的元素，并将 i 赋给 lastRet。

iterator 是线程不安全的，不支持在遍历的同时修改集合元素。每次使用 next 的时候，会首先使用 checkForComodification 方法，查看源码可知，该方法会判断两个变量 modcount、expectedModCount 是否相等，如果不相等就抛出“同时修改异常”。modcount 是 ArrayList 的父类 AbstractList 中定义的一个变量，Arraylist 的 add 方法每次执行时，会先调用 ensureCapacityInternal 方法判断容量并自动扩容，该方法又调用了 ensureExplicitCapacity 方法，该方法每次调用时 modcount 会自加一次。而expectedMoCount 是在创建 Itr 实例时生成的，将ArrayList 的 modcount 赋给它，所以当在遍历过程中修改集合元素，next 方法调用时就会抛出“同时修改异常”。

 1 private void ensureCapacityInternal(int minCapacity) {
 2         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 3     }
 4 
 5     private void ensureExplicitCapacity(int minCapacity) {
 6         modCount++;
 7 
 8         // overflow-conscious code
 9         if (minCapacity - elementData.length > 0)
10             grow(minCapacity);
11     }

2 List 接口

List 继承 Collection。List 接口中的元素时有序的、可重复的。List接口中的元素通过索引(index)来确定元素的顺序。可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

2.1 List 常用方法

public static void main(String[] args) {
       
       /**
        * 增:add/addAll/add(index,el)/addAll(index,collection)
        * 删:clear/remove/removeAll/remove(index)
        * 改:set(index,el)
        * 查:get(index)/indexOf/lastIndexOf()
        * 其他:contains/containsAll/isEmpty/size
        */
       List list1 = new ArrayList();
       // 添加元素
       list1.add("apple");
       list1.add("banana");
       // 在指定位置添加元素
       list1.add(0, "coco");
       
       System.out.println(list1);
       
       List list2 = new ArrayList();
       list2.add("java");
       list2.add("c++");
       
       list1.addAll(1, list2);
       System.out.println(list1);
       
       // 删除
       list1.remove(0);
       System.out.println(list1);
       
       // 修改
       list1.set(0, "javax");
       System.out.println(list1);
       
       // 查
       System.out.println(list1.get(0));
       list1.add("apple");
       list1.add("apple");
       System.out.println(list1);
       System.out.println(list1.indexOf("apple"));
       System.out.println(list1.lastIndexOf("apple"));
}

2.2 List 接口的遍历

ListIterator 继承于Iterator，在Iterator的基础上提供了以正向遍历集合，也可以以逆序遍历集合。hasNext/next 以正向遍历；hasPrevious/previous 以逆序遍历。

public static void main(String[] args) {
   
       List list1 = new ArrayList();
       list1.add("apple");
       list1.add("banana");
       list1.add("coco");
       
       // 【1】快速遍历
       System.out.println("--for each--");
       for (Object item : list1) {
           System.out.println(item.toString());
       }
       
       // 【2】普通for
       System.out.println("--for--");
       for(int i=0;i<list1.size();i++) {
           System.out.println(list1.get(i));
       }
       
       // 【3】集合迭代器
       System.out.println("--iterator--");
       Iterator it = list1.iterator();
       while(it.hasNext()) {
           System.out.println(it.next());
       }
       
       System.out.println("--list iterator--");
       // 正向遍历
       ListIterator it2 = list1.listIterator();
       while(it2.hasNext()) {
           System.out.println(it2.next());
       }
       
       // 逆序遍历
       while(it2.hasPrevious()) {
           System.out.println(it2.previous());
       }
       
       System.out.println("--list iterator with index--");
       ListIterator it3 = list1.listIterator(1);
       while(it3.hasNext()) {
           System.out.println(it3.next());
       }
}

3 ArrayList/Vector

ArrayList 是List接口的实现类，底层数据结构是数组，实现大小可变的数组。ArrayList 线程不安全，从 jdk1.2 开始使用。ArrayList 底层数据结构是数组，默认数组大小是10,如果添加的元素个数超过默认容量，ArrayList会自动拓容，拓容原则:newCapacity = oldCapacity + oldCapacity / 2；如果未来确定序列的元素不在增加，通过调用trimToSize()调制容量至合适的空间。ArrayList作为List接口的实现类，常用方法和遍历方法参考List接口。

Vector 是List接口的实现类，底层数据结构也是数组，也是大小可变的数组。Vector是线程安全的，从 jdk1.0 开始使用。Vector底层数据结构是数组，默认数组大小是10,如果添加的元素个数超过默认容量，Vector会自动拓容，拓容原则:newCapacity = oldCapacity +capacityIncrement(增长因子);如果未来确定序列的元素不在增加，通过调用trimToSize()调制容量至合适的空间。

注意:Vector 在实现List接口的同时，同添加了自身特有的方法xxxElement,未来使用时为了程序的可拓展性，一定要按照接口来操作Vector。

4 LinkedList

LinkedList是List接口的实现类，底层数据结构是链表。LinekList常用方法和遍历方法参照List接口。LinkedList 线程不安全。

除了实现List接口，还实现了栈接口（后进先出 LIFO），通过 push 和 pop 方法实现栈的操作。

public static void main(String[] args) {
       LinkedList list = new LinkedList();
       list.push("apple");
       list.push("banana");
       list.push("coco");
       
       
       System.out.println(list.pop()); //coco
       System.out.println(list.pop()); //banana
       System.out.println(list.pop());
       
       // java.util.NoSuchElementException
       System.out.println(list.pop());
}

也实现了队列接口（先进先出 FIFO），提供两套方法实现。

add/remove/element() 可能会出现NoSuchElementException异常

public static void main(String[] args) {
       
       LinkedList queue = new LinkedList();
       // 入队
       /**
        * 队列头                          队列尾
        *<-----          <-----
        * [apple, banana, coco]
        */
       queue.add("apple");
       queue.add("banana");
       queue.add("coco");
       System.out.println(queue);
       
       // 出队
       System.out.println(queue.remove()); //返回队列头元素，并从队列中移除
       System.out.println(queue.remove());
       System.out.println(queue.remove());        
       System.out.println(queue);
       
       // java.util.NoSuchElementException
       System.out.println(queue.remove());
       
       
       // 获取表头元素
       System.out.println(queue.element());
}

offer/poll/peek 可能会返回特殊值(null)

public static void main(String[] args) {
       
       LinkedList queue = new LinkedList();
       // 入队
       /**
        * 队列头                          队列尾
        *<-----          <-----
        * [apple, banana, coco]
        */
       queue.offer("apple");
       queue.offer("banana");
       queue.offer("coco");
       
       // 出队列
       //System.out.println(queue.poll());
       //System.out.println(queue.poll());
       //System.out.println(queue.poll());
       System.out.println(queue);

       //System.out.println(queue.poll());//输出 null
       
       // 获取表头元素
       System.out.println(queue.peek());
   
}

同时也继承了双向队列接口，两头可进可出，一样提供两套方法，一个会抛异常，一个会返回 null。

用法如上面代码类似。

5 ListIterator

正如上文讲遍历时所说的，Iterator 不支持遍历的过程中修改集合元素，而 ListIterator 正好弥补了这个缺陷，ArrayList 对象可以使用 listIterator 方法获得一个 ListIterator 的实例。ListIterator允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。

public static void main(String[] args) {
       ArrayList list = new ArrayList();
       list.add("apple");
       list.add("banana");
       list.add("coco");
       
       ListIterator it = list.listIterator();
       while(it.hasNext()) {
           String item = (String) it.next();
           if(item.equals("banana")) {
               it.add("test");  
                       //在当前光标（cursor）位置插入一个元素，这个 add 方法是属于ListIterator 的
                       // next 方法调用后，光标 cursor 会后移
           }
       }
       
       System.out.println(list); //[apple, banana, test, coco]
}

6 泛型（generic）

6.1 概念

泛型允许开发者在强类型程序设计语言（java）编写代码时定义一些可变部分，这些部分在使用前必须作出指明。泛型就是将类型参数化。

ArrayList<E> list表示声明了一个列表list，列表的元素是E类型
ArrayList<String> list = new ArrayList<String>()；声明了一个列表list，列表的元素只能是String类型。

6.2 泛型的擦除

泛型在编译器起作用，运行时jvm察觉不到泛型的存在。泛型在运行时已经被擦除了。

public static void main(String[] args) {
       ArrayList<String> list = new ArrayList<String>();
       list.add("apple");
       System.out.println(list instanceof ArrayList); //true
       System.out.println(list instanceof ArrayList<String>);
              //Cannot perform instanceof check against parameterized type ArrayList<String>.
              // Use the form ArrayList<?> instead since further generic type information will 
              //be erased at runtime
}

6.3 泛型的应用

泛型类

当一个类中属性的数据类型不确定时，具体是什么类型由使用者来确定时，使用泛型。泛型类的形式：

public class 类名<T> {
   
}

定义一个泛型类：

class FanClass<T> {
   private T t;

   public T getT() {
       return t;
   }

   public void setT(T t) {
       this.t = t;
   }

   public FanClass(T t) {
       super();
       this.t = t;
   }

   public FanClass() {
       super();
   }
}
public class Test01 {
   public static void main(String[] args) {
       FanClass<String> fan = new FanClass<String>();
       fan.setT("apple");
       
       FanClass<Integer> fan2 = new FanClass<Integer>();
       fan2.setT(1);
   }
}

泛型方法

当一个方法的参数类型不确定时，具体是什么类型由使用者来确定，可以考虑使用泛型方法，泛型方法在调用时确定(指明)类型。形式：

public <T> void xxx(T a) {
   System.out.println(a);
}

举例：

class Student {
   public <T> void showInfo(T a) {
       System.out.println(a);
   }
}
public class test {
       public static void main(String[] args) {
       Student stu = new Student();
       stu.showInfo(1);
       stu.showInfo("apple");
       stu.showInfo(1.0f);  //传入的参数是什么类型，T 就是什么类型
   }
}