集合框架概览

• 前言
• • 数组和集合区别
  • 误解
• 集合
• • Collection
  • • List
    • • AbstractList
      • ArrayList
      • • 属性
        • 构造器

集合数学中的概念：是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。同样的java集合就是汇集特定性质对象的容器。

• 数组是java语言内置的数据类型，他是一个线性的序列，所以可以快速访问其他的元素，当创建了一个数组后，它的容量是不变的。

而集合是可以动态扩展容量，可以根据需要动态改变大小，集合提供更多的成员方法，能满足更多的需求。

集合存放的类型可以不是一种(不加泛型时添加的类型是Object)。数组存放只能是一种类型的数据

Object [] ob = new Object[3];
ob[0]=1;
ob[1]="hal";
ob[2]=new TestList();

类似于不声明类型的集合

List li = new ArrayList();
li.add(1);
li.add("hal");
li.add(new TestList());

集合框架分为Collection和Map派生。

Collection分为List、Queue、Set。Collection接口提供了基础功能：新增、大小、是否为空、包含、分割、流。

继承自Collection只是一个接口定义了基本行为属性。

AbstractList提供了列表接口的框架实现，以最小化实现由“随机访问”数据存储（如数组）支持的接口所需的工作量。对于顺序访问数据（如链表），应优先使用AbstractSequentialList而不是此类。

1. 要实现一个不可修改的列表，程序员只需扩展这个类，并提供get(int)和size()方法的实现。
2. 实现一个可修改的列表，程序员必须另外重写set(int，E)方法(否则会抛出一个UnsupportedOperationException)。如果列表大小可变，程序员还必须重写add(int，E)和remove(int)方法。
3. 与其他抽象集合实现不同，程序员不必提供迭代器实现；迭代器和列表迭代器由此类在“随机访问”方法之上实现：get(int)、set(int，E)、add(int，E)和remove(int)。由内部类Itr和ListItr源码看出。
4. fail-fast机制：如果在创建迭代器后的任何时候，以迭代器自己的remove或add方法以外的任何方式对列表进行结构修改，迭代器将抛出ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速、干净地失败，而不是在将来的不确定时间冒着任意、不确定行为的风险

private class Itr implements Iterator {
        
        int cursor = 0;

        
        int lastRet = -1;

        
        int expectedModCount = modCount;
		//光标等于列表容量大小时，表示没有下一个元素了
        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
        //并发修改检查
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
            
                checkForComodification();
                throw new NoSuchElementException(e);
            }
        }

        public void remove() {
        
            if (lastRet < 0)
                throw new IllegalStateException();
            //检查并发修改
            checkForComodification();

            try {
            	//调用AbstractList的remove从数组中移除元素
                AbstractList.this.remove(lastRet);
                
                if (lastRet < cursor)
                 
                    cursor--;
                //最后返回元素索引标志复位为-1
                lastRet = -1;
                //同步modCount到迭代器
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
            //数组越界时由于remove并发引起的，抛出并发修改异常
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    //对Itr的扩展
    private class ListItr extends Itr implements ListIterator {
        ListItr(int index) {
            cursor = index;
        }
		//是否有前向元素
        public boolean hasPrevious() {
        //光标不为0就代表有前向元素
            return cursor != 0;
        }
		//查找前向元素
        public E previous() {
            checkForComodification();
            try {
            	
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException(e);
            }
        }
		
        public int nextIndex() {
            return cursor;
        }
		//前向元素索引当前光标-1
        public int previousIndex() {
            return cursor-1;
        }
		//为最后一次调用next返回元素设置值
        public void set(E e) {
        //没有调用next或者元素被移除，抛出状态异常。
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
		//增加元素
        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                AbstractList.this.add(i, e);
                成功增加完元素，最后一次返回标志复位为-1
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

List的可调整大小的数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现列表接口外，此类还提供了一些方法来操作内部用于存储列表的数组Array的大小。(该类大致相当于Vector，只是不同步。）

1. size、isEmpty、get、set、iterator和listIterator运行时间是固定的。add操作在摊销的固定时间内运行，即添加n个元素需要O(n)个时间。所有其他操作都在线性时间内运行（粗略地说）。与linkedList实现相比，常数因子较低。
2. ArrayList的实现非同步的。如果多个线程并发获取一个ArrayList实例，一个线程结构性的改动了ArrayList(新增、移除、调整数组大小都是结构性改变，修改元素值不是结构性改变)。通常在封装列表的某个对象时完成同步。没有这样的对象，就在创建list时List list = Collections.synchronizedList(new ArrayList(...))

private static final int DEFAULT_CAPACITY = 10;
//空的数组实列，初始化ArraList时初始化容量为0时
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认空数组实列，第一次添加元素时可以和初始化容量为0时区分，此时是通过无参构造来的
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData;
//数组容量
private int size;


    public static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }