java ArrayList集合分析

16-04-25 来源：[db:作者]

收藏我要投稿

一、 ArrayList概述：

本文的源代码分析基于的JDK版本是1.8.
ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。
ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。可以接受泛型。
ArrayList类的定义：

public class ArrayList extends AbstractList implements Cloneable, Serializable, RandomAccess

每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。
注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

二、 ArrayList的实现：

对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析ArrayList的源代码：

1) 私有属性：

ArrayList定义只定义类3个属性：
定义一个Object类型的数组。

/**
     * The elements in this list, followed by nulls.
     */
    transient Object[] array;

有个关键字需要解释：transient。

Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。
有点抽象，看个例子应该能明白。

public class UserInfo implements Serializable {  
     private static final long serialVersionUID = 996890129747019948L;  
     private String name;  
     private transient String psw;  

     public UserInfo(String name, String psw) {  
         this.name = name;  
         this.psw = psw;  
     }  

     public String toString() {  
         return "name=" + name + ", psw=" + psw;  
     }  
 }  

 public class TestTransient {  
     public static void main(String[] args) {  
         UserInfo userInfo = new UserInfo("张三", "123456");  
         System.out.println(userInfo);  
         try {  
             // 序列化，被设置为transient的属性没有被序列化  
             ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(  
                     "UserInfo.out"));  
             o.writeObject(userInfo);  
             o.close();  
         } catch (Exception e) {  
             // TODO: handle exception  
             e.printStackTrace();  
         }  
         try {  
             // 重新读取内容  
             ObjectInputStream in = new ObjectInputStream(new FileInputStream(  
                     "UserInfo.out"));  
             UserInfo readUserInfo = (UserInfo) in.readObject();  
             //读取后psw的内容为null  
             System.out.println(readUserInfo.toString());  
         } catch (Exception e) {  
             // TODO: handle exception  
             e.printStackTrace();  
         }  
     }  
 }

被标记为transient的属性在对象被序列化的时候不会被保存。

接着回到ArrayList的分析中……
记录数组的长度。很容易理解，array存储ArrayList内的元素，size表示它包含的元素的数量。

 /**
     * The number of elements in this list.
     */
    int size;

在创建ArrayList对象时，会默认初始化集合的大小，那么接下来这个静态常量就是来定义初始化的集合的长度。前面已经说过：。随着向ArrayList中不断添加元素，其容量也自动增长。那么默认的List集合的长度就是通过该变量定义的。

 /**
     * The minimum amount by which the capacity of an ArrayList will increase.
     * This tuning parameter controls a time-space tradeoff. This value (12)
     * gives empirically good results and is arguably consistent with the
     * RI's specified default initial capacity of 10: instead of 10, we start
     * with 0 (sans allocation) and jump to 12.
     */
    private static final int MIN_CAPACITY_INCREMENT = 12;

2) 构造方法：

ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为12的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。

/**
     * Constructs a new instance of {@code ArrayList} with the specified
     * initial capacity.
     *
     * @param capacity
     *            the initial capacity of this {@code ArrayList}.
     * ArrayList带容量大小的构造函数。    
     */
    public ArrayList(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity < 0: " + capacity);
        }
        array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
    }

    /**
     * Constructs a new {@code ArrayList} instance with zero initial capacity.
     * // ArrayList无参构造函数。默认容量是12。
     */
    public ArrayList() {
        array = EmptyArray.OBJECT;
    }

    /**
     * Constructs a new instance of {@code ArrayList} containing the elements of
     * the specified collection.
     *
     * @param collection
     *            the collection of elements to add.
     * 创建一个包含collection的ArrayList    
     */
    public ArrayList(Collection collection) {
        if (collection == null) {
            throw new NullPointerException("collection == null");
        }

        Object[] a = collection.toArray();
        if (a.getClass() != Object[].class) {
            Object[] newArray = new Object[a.length];
            System.arraycopy(a, 0, newArray, 0, a.length);
            a = newArray;
        }
        array = a;
        size = a.length;
    }

里面的一个方法需要说明以下：

src  ： 需要拷贝的数组
srcPos：从src的那个下标开始拷贝
dst：将src的内容拷贝到的数组。
dstPos：congsrcPos的那个下标开始放置被拷贝的元素
length：拷贝的元素的个数
public static native void arraycopy(Object src, int srcPos,
        Object dst, int dstPos, int length);

ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection

3) 元素存储：

1.add(E object)方法：
将指定的元素添加到此列表的尾部。先判断是否有剩余的空间存放该元素。如果没有声誉的空间则将新创建一个集合newArray，并将大小扩大为原来的1.5被。然后将array里面的数据拷贝到newArray里面。

@Override public boolean add(E object) {
        Object[] a = array;
        int s = size;
        //判断集合元素的长度是否等于数组的长度
        if (s == a.length) {
        //创建新的数组，大小扩大为原来的1.5被。
            Object[] newArray = new Object[s +
                    (s < (MIN_CAPACITY_INCREMENT / 2) ?
                     MIN_CAPACITY_INCREMENT : s >> 1)];
            //数组拷贝
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        //添加元素
        a[s] = object;
        //长度+1
        size = s + 1;
        modCount++;
        return true;
    }

2.set(int index, E object)
用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。

@Override public E set(int index, E object) {
        Object[] a = array;
        //判断是否越界
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        a[index] = object;
        return result;
    }

@SuppressWarnings(“unchecked”)的作用：取消警告表示，在编译.java文件的时候，不在出现一些警告，如变量没有用到，会有提示警告，用@SuppressWarnings(“unused”)之后，警告消失。

3.add(int index, E object)方法：
将指定的元素插入此列表中的指定位置。如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）
下面通过一张图来解释这段话：
这里写图片描述

@Override public void add(int index, E object) {
        Object[] a = array;
        int s = size;
        if (index > s || index < 0) {
            throwIndexOutOfBoundsException(index, s);
        }

        //数组元素的长度是否小于数组的长度
        if (s < a.length) {
           ///将index下标以后的数据向右移一位
            System.arraycopy(a, index, a, index + 1, s - index);
        } else {
            // assert s == a.length;
            //需要扩大数组的大小，从新创建新的数组
            Object[] newArray = new Object[newCapacity(s)];
            //数组拷贝，先拷贝0～index -1的数据。
            System.arraycopy(a, 0, newArray, 0, index);
            //在拷贝index以后的数据。注意新的数组的index的数据是空的。
            System.arraycopy(a, index, newArray, index + 1, s - index);
            //将新的数组赋值给array
            array = a = newArray;
        }
        //将index的元素赋值
        a[index] = object;
        size = s + 1;
        modCount++;
    }

4.addAll(Collection

@Override public boolean addAll(Collection collection) {
        Object[] newPart = collection.toArray();
        int newPartSize = newPart.length;
        if (newPartSize == 0) {
            return false;
        }
        Object[] a = array;
        int s = size;
        int newSize = s + newPartSize; // If add overflows, arraycopy will fail
        if (newSize > a.length) {
            int newCapacity = newCapacity(newSize - 1);  // ~33% growth room
            Object[] newArray = new Object[newCapacity];
            System.arraycopy(a, 0, newArray, 0, s);
            array = a = newArray;
        }
        System.arraycopy(newPart, 0, a, s, newPartSize);
        size = newSize;
        modCount++;
        return true;
    }

书上都说ArrayList是基于数组实现的，属性中也看到了数组，具体是怎么实现的呢？比如就这个添加元素的方法，如果数组大，则在将某个位置的值设置为指定元素即可，如果数组容量不够了呢？

4) 元素读取：

返回此列表中指定位置上的元素。

 @SuppressWarnings("unchecked") @Override public E get(int index) {
        if (index >= size) {
            throwIndexOutOfBoundsException(index, size);
        }
        return (E) array[index];
    }

5) 元素删除：

ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下：

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

@Override public E remove(int index) {
        Object[] a = array;
        int s = size;
        if (index >= s) {
            throwIndexOutOfBoundsException(index, s);
        }
        @SuppressWarnings("unchecked") E result = (E) a[index];
        //将array的index以后的数据向前移动一位
        System.arraycopy(a, index + 1, a, index, --s - index);
        //将最后一个元素设置为null
        a[s] = null;  // Prevent memory leak
        size = s;
        modCount++;
        return result;
    }

首先是检查范围，修改modCount，保留将要被移除的元素，将移除位置之后的元素向前挪动一个位置，将list末尾元素置空（null），返回被移除的元素。

remove(Object o)移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。

@Override public boolean remove(Object object) {
        Object[] a = array;
        int s = size;
        if (object != null) {
            for (int i = 0; i < s; i++) {
                if (object.equals(a[i])) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        } else {
            for (int i = 0; i < s; i++) {
                if (a[i] == null) {
                    System.arraycopy(a, i + 1, a, i, --s - i);
                    a[s] = null;  // Prevent memory leak
                    size = s;
                    modCount++;
                    return true;
                }
            }
        }
        return false;
    }

首先通过代码可以看到，当移除成功后返回true，否则返回false。remove(Object o)中通过遍历element寻找是否存在传入对象，一旦找到就将index的位置以后的元素向前移动一位。

6) 调整数组容量newCapacity：

从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法newCapacity(int currentCapacity)来实现。在实际添加大量元素前，我也可以使用newCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

private static int newCapacity(int currentCapacity) {
        int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
                MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
        return currentCapacity + increment;
    }

currentCapacity >> 1 返回的数值是currentCapacity的50%.
从上述代码中可以看出，数组进行扩容时，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用newCapacity方法来手动增加ArrayList实例的容量。

关于ArrayList和Vector区别如下：

ArrayList在内存不够时默认是扩展50% + 1个，Vector是默认扩展1倍。
Vector提供indexOf(obj, start)接口，ArrayList没有。
Vector属于线程安全级别的，但是大多数情况下不使用Vector，因为线程安全需要更大的系统开销。
ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下：

 public void trimToSize() {
        int s = size;
        if (s == array.length) {
            return;
        }
        if (s == 0) {
            array = EmptyArray.OBJECT;
        } else {
            Object[] newArray = new Object[s];
            System.arraycopy(array, 0, newArray, 0, s);
            array = newArray;
        }
        modCount++;
    }

由于arrray的长度会被拓展，size标记的是其中包含的元素的个数。所以会出现size很小但array.length很大的情况，将出现空间的浪费。trimToSize将返回一个新的数组给arrray，元素内容保持不变，length和size相同，节省空间。
转为静态数组toArray
4、注意ArrayList的两个转化为静态数组的toArray方法。
直接进行数组拷贝。返回的数组的长度等于数组的元素的个数，避免浪费存储空间。

@Override public Object[] toArray() {
        int s = size;
        Object[] result = new Object[s];
        System.arraycopy(array, 0, result, 0, s);
        return result;
    }

点击复制链接与好友分享!回本站首页