java ArrayList学习

ArrayList&LinkedList 区别

ArrayList是用数组实现。linkedList是链表实现。
ArrayList数组实现查找快，新增删除慢。LinkedList链表新增删除快查找慢。
为什么？
数组是申请的一块连续的内存，新增就是不断的申请拷贝数据。删除的话先查到这个数据，删除它，然后后面的所有数据都要移动。这样的数据结构查询很快。
链表的话是不连续的内存每次查找涉及到指针移动寻址。

ArrayList详解

查找

ArrayList两种查找 get(index) get(Object)（内部还是get(index)去遍历的） 因为是连续的存储单元。所以遍历很快。

基本属性

	
  /**
* 存储数据数组
   * The array buffer into which the elements of the ArrayList are stored.
   * The capacity of the ArrayList is the length of this array buffer.
   */
  private transient Object[] elementData;

  /**
* 数组大小
   * The size of the ArrayList (the number of elements it contains).
   *
   * @serial
   */
  private int size;

默认构造方法

/**
 * 初始化大小固定的数组
    * Constructs an empty list with the specified initial capacity.
    */
   public ArrayList(int initialCapacity) {
   	super();
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
  		this.elementData = new Object[initialCapacity];
   }

   /**
 * 默认大小为10
    * Constructs an empty list with an initial capacity of ten.
    */
   public ArrayList() {
  		this(10);
   }

   /**
    * 初始化一个存在的集合转换成数组
    * Constructs a list containing the elements of the specified
    * collection, in the order they are returned by the collection's
    * iterator.
    */
   public ArrayList(Collection<? extends E> c) {
   	elementData = c.toArray();
   	size = elementData.length;
   	// c.toArray might (incorrectly) not return Object[] (see 6260652)
   	if (elementData.getClass() != Object[].class)
       	elementData = Arrays.copyOf(elementData, size, Object[].class);
   }

新增方法

		
 	public boolean add(E e) {
		//size就是里面元素的的大小
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e; 
        return true;
    }
	
    //先进行数组容量调整最后将数据放在数组最后，所以这步操作才不会出错elementData[size++] = e;
	private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

		//现在变成最大值
        ensureExplicitCapacity(minCapacity);
    }
	
    //确定内部数组容量如果当前数组容量小于默认容量选择默认容量，
	//相当于提前扩展数组（可能是防止频繁的数组拷贝）
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
	
    private void grow(int minCapacity) {
        //当前数组实际容量
        int oldCapacity = elementData.length;
		//新容量是原来容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

`

删除

   public boolean remove(Object o) {
       if (o == null) {
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   fastRemove(index);
                   return true;
               }
       }
       return false;
   } 

/*
    * Private remove method that skips bounds checking and does not
    * return the value removed.
    */
   private void fastRemove(int index) {
       modCount++;
       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work
   }

   public static native void arraycopy(Object src,  int  srcPos,
                                       Object dest, int destPos,
                                       int length);

> 因为数组是连续存储所有的新增和删除操作都会涉及到后面的值和位置的修改。得出结论ArrayList的新增和删除每次都会涉及到数组的copy所以效率比较低

查找

public E get(int index) {
       rangeCheck(index);
       return elementData(index);
   }

private void rangeCheck(int index) {
       if (index >= size)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
   }

E elementData(int index) {
       return (E) elementData[index];
   }

直接通过数组下标找到到查找的元素

快速失败原理

final void checkForComodification() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }

在进行集合迭代的时候会开启新线程进行循环，
如果同时进行新增删除中都会对modCount进行++操作。在使用迭代器进行遍历arrayList的时候
modCount会发生变化实现快速失败。

解决快速失败:采用对应的线程安全的对应结构CopyOnWriterArrayList