首页 > 代码库 > java集合-ArrayList

java集合-ArrayList

  一直要总结java集合中的知识,不知道应该如何下笔。觉得集合太多东西了,写细了太难了,写粗了又感觉写不好。不管如何觉得还是要坚持的写一写基础这一类的东西,为了提高自己的编程基础。本来觉的自己对这些已经很熟悉,最近见过一些大神后发现差距太大了,瞬间懵了,只能在加强学习了。

一、ArrayList是什么?

  ArrayList是实现List接口的动态数组,所谓动态是指它的大小是可变的。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。

  既然是数组,肯定就有容量。每个ArrayList对象都有一个容量,该容量是用来表示可以存放多少个数据在里面,即是数组的大小(默认是10)。当然,动态的肯定就会自动增加,每次我们往里面添加数据的时候,它都会进行扩容检查,检查完扩容会扩大为原来的1.5倍,扩容操作带来数据向新数组的重新拷贝,影响性能,所以如果我们知道具体业务数据量,在构造ArrayList时可以给ArrayList指定一个初始容量,这样就会减少扩容时数据的拷贝问题。当然在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

  ArrayList的底层实现是不同步,多线程操作会出现问题,这一点大家要注意。可以插入重复数据,可以插入Null。

二、ArrayList源码分析

  2.1、ArrayList定义

    public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

    ArrayList的定义,继承AbstractList,实现List<E>, RandomAccess, Cloneable, java.io.Serializable,其中AbstractList实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换。RandomAccess代表该类是否支持 随机访问,Cloneable类支持克隆,Serializable支持序列化。

  2.2、底层使用数组

    private static final long serialVersionUID = 8683452581122892189L;//serialVersionUID作用是序列化时保持版本的兼容性,即在版本升级时反序列化仍保持对象的唯一性。

    private transient Object[] elementData;//Object数组,transient关键字不知道的同学自己查资料去,带transient关键字的变量不会序列化。ArrayList容器,基本操作都是基于该数组进行操作的。

    private int size;//数组的大小。

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//要分配的数组的最大大小。

  2.3、构造函数   

    ArrayList有三个构造函数:

    ArrayList():默认构造函数,提供初始容量为10的空列表。

    ArrayList(int initialCapacity):构造一个具有指定初始容量的空列表。

    ArrayList(Collection<? extends E> c):构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。

  /**     * 构造具有指定初始容量的空列表。.     *     * @param  初始容量列表的初始容量     * @throws IllegalArgumentException 如果指定的初始容量为负会抛出非法异常。     */    public ArrayList(int initialCapacity) {        super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        this.elementData = http://www.mamicode.com/new Object[initialCapacity];    }    /**     * 构建一个初始容量为十的空列表.     */    public ArrayList() {        this(10);    }    /**     * 构造包含指定元素的列表。     * 集合,按集合返回的顺序     * 迭代器     *     * @param c的集合,其元素将放在这个列表中。     * @throws NullPointerException 如果指定的集合为null为抛出这个空指针异常。     */    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);    }

  2.4、add方法  

    ArrayList提供了add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)、set(int index, E element)这个五个方法来实现ArrayList增加。

我就拿一个来讲了,懂的一个,其他应该都懂了。  

  public boolean add(E e) {        ensureCapacityInternal(size + 1);  //增加操作次数        elementData[size++] = e;//把值放到最后一位        return true;  }  private void ensureCapacityInternal(int minCapacity) {        modCount++;        // overflow-conscious code        if (minCapacity - elementData.length > 0)//如果数组真实存储大于数组容量就增加            grow(minCapacity);  }  private void grow(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;//原来的容量        int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量为旧的1.5倍        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 =http://www.mamicode.com/ Arrays.copyOf(elementData, newCapacity);//复制数组 } private static int hugeCapacity(int minCapacity) {//注意是个静态方法        if (minCapacity < 0) // overflow   小于0,抛异常            throw new OutOfMemoryError();        return (minCapacity > MAX_ARRAY_SIZE) ?//大于MAX_ARRAY_SIZE就设置为MAX_VALUE,否则就MAX_ARRAY_SIZE            Integer.MAX_VALUE :            MAX_ARRAY_SIZE;}

  2.5、remove方法

    ArrayList提供了remove(int index)、remove(Object o)、removeRange(int fromIndex, int toIndex)、removeAll()四个方法进行元素的删除。

    remove(int index):移除此列表中指定位置上的元素。

  public E remove(int index) {//根据下标删除        rangeCheck(index);//检查是否越界        modCount++;//操作增加        E oldValue = http://www.mamicode.com/elementData(index);//获得下标的值        int numMoved = size - index - 1;//要移动的数据        if (numMoved > 0)            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);//数组往前移        elementData[--size] = null; // 让GC工作        return oldValue;//返回旧值  }  private void rangeCheck(int index) {//检查越界        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  }  private String outOfBoundsMsg(int index) {//是不是感觉经常空间这个,哈哈        return "Index: "+index+", Size: "+size;  }  @SuppressWarnings("unchecked")  E elementData(int index) {        return (E) elementData[index];  }

    remove(Object o):如果存在移除此列表中首次出现的指定元素。

  public boolean remove(Object o) {        if (o == null) {//如果为null            for (int index = 0; index < size; index++)                if (elementData[index] == null) {//==来比较                    fastRemove(index);                    return true;//存在并删除返回true                }        } else {//如果不为null            for (int index = 0; index < size; index++)                if (o.equals(elementData[index])) {//equals来比较                    fastRemove(index);//存在并删除返回true                    return true;                }        }        return false;//不存在返回false  }  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; // Let gc do its work  }

  2.6、get方法

   public E get(int index) {        rangeCheck(index);//检查是否越界        return elementData(index);//取值  }

  2.7、注意subList方法

  public static void main(String[] args) {        List<Integer> list1 = new ArrayList<Integer>();        list1.add(1);        list1.add(2);        // 通过构造函数新建一个包含list1的列表 list2        List<Integer> list2 = new ArrayList<Integer>(list1);        // 通过subList生成一个与list1一样的列表 list3        List<Integer> list3 = list1.subList(0, list1.size());        // 修改list3        list3.add(3);        System.out.println(list1.size());        System.out.println("list1 == list2:" + list1.equals(list2));        System.out.println("list1 == list3:" + list1.equals(list3));  }

    上面一段代码我感觉大部人都会认为结果是2个false,list2是新构造的肯定与list1不一样,list3是截取的肯定也不一样。所以会认为都是false,我们深入subList去看看。

public List<E> subList(int fromIndex, int toIndex) {        subListRangeCheck(fromIndex, toIndex, size);//检查下标和大小        return new SubList(this, 0, fromIndex, toIndex);//新创建一个SubList对象,注意传入的是this,代表了要截取的对象}private class SubList extends AbstractList<E> implements RandomAccess {//我擦,跟list差不多的感觉private final AbstractList<E> parent;private final int parentOffset;private final int offset;int size;//我擦,熟悉的感觉SubList(AbstractList<E> parent,int offset, int fromIndex, int toIndex) {//刚刚的构造            this.parent = parent;//this.parent = parent;而parent就是在前面传递过来的list,也就是说this.parent就是原始list的引用。            this.parentOffset = fromIndex;            this.offset = offset + fromIndex;            this.size = toIndex - fromIndex;            this.modCount = ArrayList.this.modCount;//操作数也是跟原来的一样}

  原来sublist里面操作的是原来的list,并没有生成新的list,导致2个其实是一样的。

  所以上面正确的结果是:

  list1 == list2:false
  list1 == list3:true

三、ArrayList总结

  因为它是基于数组实现的,主要有如下特点:

  1、插入、删除比较慢,因为插入、删除需要移动数据位置。

  2、可以重复插入数据、可以插入null。

  3、查找比较快,可以直接使用下标。

 

java集合-ArrayList