Array and Collection Framework

转载自：https://blog.csdn.net/ada_dengpan/article/details/51200907

Array数组

* （1）Array数组
*
* 和C/C++以及其他语言一样，Java中的数组有差不多一样的语法
* 只是Java中除了8种基本类型，数组也是作为对象处理的，所以创建对象时也需要使用new关键字
* 和大多数编程语言一样，数组一旦创建，大小便不可改变
* Java中有一个Arrays封装类，专门用来操作基本数组
* Arrays中拥有一组static函数：
*     --equals():比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等
*     --fill():将指定的数据类型填入array数组中
*     --sort():用来对array数组进行排序
*     --binarySearch():在排好的array数组中寻找元素
*     --System.arraycopy():array数组的复制
*
* int [] intArr = new int[10];
*

Collection集合框架

概述

* （2）Array是Java中随机访问一连串对象最有效率的数据结构，但很不灵活，大小固定，且不知道里面有多少元素
* 为此JDK（）已经为我们提供了一系列的类来实现功能强大且更灵活的基本数据结构，这些类均在java.util包中。
* 其继承结构如下：
* --Collection（集合）
*
*   --List（列表）
*         --LinkedList（链表：链式存储）
*         --ArrayList（线性表：顺序存储）
*         --Vector（矢量）（已淘汰）
*              --Stack（栈）
*
*   --Set（集合）
*         --HashSet
*              --LinkedHashSet
*
*         --TreeSet（实现了SortedSet接口）
*   
*
*   --Queue（队列）
*
*   --Map（图）
*         --HashTable（哈希表：散列表）（已淘汰）
*         --HashMap（哈希图；散列表）
*              --LinkedHashMap
*         --TreeMap
*         --WeakHashMap
*

List

* （2.1）List
*   List是一个接口，不能实例化，若要实例化要通过创建ArrayList或LinkedList
*
* （2.1.1）ArrayList里面的内部类实现，是通过一定的增长规则动态复制增加数组长度来实现动态增加元素的，
*    如果在大量数据的情况下，在某一位置随机插入或删除元素，就会产生性能问题。
*
* （2.1.2）LinkedList可以解决这类问题，但LinkedList在通过下标取元素的时候，一定要遍历整个链表节点匹配，在数据量大的情况下，效率不高。
*
* （2.1.3）Vector是一种过时的动态数组，是线程同步的，效率很低，一般不赞成使用：
*          
*          Stack是Java实现了一个堆栈，先进后出（FILO）结构。
*

Set

*
* （2.2）Set
*  Set接口继承Collection接口，最大的特点是集合中的元素都是唯一的，没有重复元素。
*  它有两个类：HashSet和TreeSet
* （2.2.1）--HashSet
*        --不允许出现重复元素；
*        --不保证集合中元素的顺序都是哈希算法来的~
*        --允许包含值为null的元素，但最多只能有一个null元素。
*  
* （2.2.2）--TreeSet
*        --不允许出现重复元素；
*        --集合中元素的顺序按某种规则进行排序；
*        --不允许包含值为null的元素
*
* （2.2.3）遍历时删除问题
*    1、//使用迭代器遍历Set集合.
*      Iterator<String> it  = set.iterator();
*      while(it.hasNext()){
*      		String temp = it.next();
*      		System.out.println("元素："+ temp);
*      		it.remove();
*       }
*    2、//使用增强for循环解决 （底层实现还是迭代器）
*       for(String item : set){
*       	System.out.println("元素："+ item);
*        } 
*     使用增强for循环遍历List（所有实现子类ArrayList，Stack等）元素对其中元素进行删除，会抛出java.util.ConcurrentModificationException的异常。
*     若使用下面这种方式：
*         for(int i= 0; i < list.size(); i++){
*             list.remove(i);
*         }
*     则会删除下标为偶数的元素，因为每次删除后，后面的元素的下标全部减1,相当于元素位置全部左移一位，再次删除时，会跳过一个元素进行删除，这是非常不好的。
*     如果非要这样删除，可以倒着来：
*         for(int i = list.size()-1; i >= 0; i--){
*             list.remove(i);
*         }
*     或者新建一个要删除的List，最后一起删除list.removeAll(deleteList);
*

Map

*
* （2.3）Map
*   Map接口，没有继承Collection接口，它是一个独立的接口。使用key-value的键值对存储数据，
*   常用的两个子类是HashMap和TreeMap。
*
*  （2.3.1）--HashMap：Map基于散列表的实现。插入和查询“键值对”的位置是固定的，
*   可以通过构造器设置容量capacity和负载因子loadfactor，以调整容器的装载能力。
*
*  （2.3.2）--LinkedHashMap：类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序或者是最近最少使用（LRU）的次序，只比HashMap慢一点，而在迭代访问时反而更快，因为它使用链表维护内部次序。
*
*  （2.3.3）--TreeMap：基于红黑树数据结构的实现的，查看“键”或“键值对”时，它们会被排序（次序由Comparabel或Comparator决定）
*    TreeMap的特点在于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。
*
*  （2.3.4）--WeakHashMap：弱键（weak key）Map，Map中使用的对象也被允许释放：这是为解决特殊问题设计的。
*    如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。
*
*  （2.3.5）--IdentifyHashMap:使用==代替equals()对“键”作比较 hash map。专为解决特殊问题而设计的。
*

线程安全

* （3）线程安全
*    Vector是线程同步的，也就是线程安全的，对多线程的操作采用了synchronized处理。但因为效率低已不建议使用，
*    而ArrayList和LinkedList虽然是线程异步的、效率高，但都是线程不安全的，在多线程环境中，对数据的修改会造成错误的结果。
*
* 有两种解决方案：
*  （3.1）使用同步包装器
*     List safedList = Collections.synchronizedList(new ArrayList());
*     Set safedSet = Collections.synchronizedSet(new HashSet);
*     Map safedMap = Collections.synchronizedSet(new HashSet);
*
*   查看其源码，发现是Collections类给不安全的集合类包装了一层（即虚拟机自动给集合实现加锁接口），然后生成一个新的类。
*   新类里面采用了synchronized对集合的操作进行了同步处理：
*   public int size(){
        synchronized(mutex){return c.size();}
    }
    public boolean isEmpty(){
        synchronized(mutex){return c.isEmpty();}
    }
    public boolean contains(Object o){
        synchronized(mutex){return c.contains(o);}
    }
    public Object[] toArray(){
        synchronized(mutex){return c.toArray();}
    }
    public <T> T[] toArray(T[] a){
        synchronized(mutex){return c.toArray(a);}
    }
    public Iterator<E> iterator(){
        return c.iterator(); //Must be manually synched by uers!
    }                        //必须由用户手动同步
    public boolean add(E e){
        synchronized(mutex){return c.add(e);}
     }
    public boolean remove(Object o){
        synchronized(mutex){return c.remove(o);}
    }
    public boolean containsAll(Collection<?> coll){
        synchronized(mutex){return c.containsAll(coll);}
    }
    public boolean addAll(Collection<? extends E> coll){
        synchronized(mutex){return c.addAll(coll);}
    }
    public boolean removeAll(Collection<?> coll){
        synchronized(mutex){return c.removeAll(coll);}
    }
    public boolean retainAll(Collection<?> coll){
        synchronized(mutex){return c.retainAll(coll);}
    }
    public void clear(){
        synchronized(mutex){c.clear();}
    }
 *                    
 *  （3.2）使用安全的集合：
 *   Java5.0新加入的ConcurrentLinkedQueue、ConcurrentHashMap
 *   CopyOnWriteArrayList和CopyOnWriteArraySet,这些集合类都是线程安全的。
 *   都在java.util.concurrent包下。而至于这些新的类为什么能保证线程安全，这里不作详述。
 *                    
 * PS:
 * concurrent
 *    adj.〈正式的;同时发生的;同时完成的;同时存在的。
 *    n.[数] 共点;同时发生的事情
 */