java集合类源码分析 ArrayList

时间:2021-08-07 16:59:03

本源代码来自JDK1.8  与1.7、1.6 略有不同

1 ArrayList中的属性

1 初始容量

初始大小为10

[java] view plain copy
  1. /** 
  2.      * Shared empty array instance used for empty instances. 
  3.      */  
  4.     private static final Object[] EMPTY_ELEMENTDATA = {};  

2 空的Object数组

当初始化容量为0时,就构造这样一个空的Objcet类型数组。

[java] view plain copy
  1. /** 
  2.      * Shared empty array instance used for empty instances. 
  3.      */  
  4.     private static final Object[] EMPTY_ELEMENTDATA = {};  

3 默认的空的Object数组

根据注释,这个大概意思就是构造一个空的对象数组,用来与EMPTY_ELEMENTDATA 这个数组进行对比,来确定当第一次向ArrayList中添加数据时,应该如果进行扩容,就是增加多大的容量暂时还不太好理解这个,往后看就懂了

[java] view plain copy
  1. /** 
  2.      * Shared empty array instance used for default sized empty instances. We 
  3.      * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when 
  4.      * first element is added. 
  5.      */  
  6.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  

4 真正用于保存数组的对象数组

ArrayList中 用来存储数组的对象数组 这个对象是transient 的,即不可被序列化的

由此可见,ArrayList底层实际是在维护一个对象数组

[java] view plain copy
  1. /** 
  2.     * The array buffer into which the elements of the ArrayList are stored. 
  3.     * The capacity of the ArrayList is the length of this array buffer. Any 
  4.     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 
  5.     * will be expanded to DEFAULT_CAPACITY when the first element is added. 
  6.     */  
  7.    transient Object[] elementData; // non-private to simplify nested class access  

5 ArrayList 大小Size

用于标识当前ArrayList的真实大小

[java] view plain copy
  1. /** 
  2.     * The size of the ArrayList (the number of elements it contains). 
  3.     * 
  4.     * @serial 
  5.     */  
  6.    private int size;  

2 构造方法

ArrayList 共有三个构造方法

1 默认的空的构造方法

根据这个方法的注释,默认的构造方法构造的是构造了一个容量为十的List,但是从源代码来看,实际上在这个地方只是构造了一个空的对象数组,那么为什么说是十呢,在后来就能看懂了。

[java] view plain copy
  1. /** 
  2.      * Constructs an empty list with an initial capacity of ten. 
  3.      */  
  4.     public ArrayList() {  
  5.         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
  6.     }  

2 带有初始化容量的构造方法

根据指定的容量构造一个空的对象数组。如果容量为负数,抛出异常。应该注意的是,当指定容量为0时,构造时使用的就是前面的全局变量,即为一个空的对象数组。

[java] view plain copy
  1. public ArrayList(int initialCapacity) {  
  2.         if (initialCapacity > 0) {  
  3.             this.elementData = new Object[initialCapacity];  
  4.         } else if (initialCapacity == 0) {  
  5.             this.elementData = EMPTY_ELEMENTDATA;  
  6.         } else {  
  7.             throw new IllegalArgumentException("Illegal Capacity: "+  
  8.                                                initialCapacity);  
  9.         }  
  10.     }  

3 利用一个已有的Collection来构造

这里首先用到了Collection.toArray()方法进行数组转换。

在这里有一个确认对象类型的检验,如果集合中的对象不是Objec类型,利用Array类的静态方法进行数组的拷贝,这里给出的注释是在调用toArray()方法时可能存在问题,这里的6260652应该BUG的Id号

当转换的数组为空时,ArryaList并没有使用转换的空结果,而是依然使用自己构造的空数组。也许Java程序员认为外来的都是不可信任的吧(个人理解)

[java] view plain copy
  1. <span style="font-size:18px;">public ArrayList(Collection<? extends E> c) {</span>  
  2.         elementData = c.toArray();  
  3.         if ((size = elementData.length) != 0) {  
  4.             // c.toArray might (incorrectly) not return Object[] (see 6260652)  
  5.             if (elementData.getClass() != Object[].class)  
  6.                 elementData = Arrays.copyOf(elementData, size, Object[].class);  
  7.         } else {  
  8.             // replace with empty array.  
  9.             this.elementData = EMPTY_ELEMENTDATA;  
  10.         }  
  11.     }  


3 Add方法

这里把Add方法单独拿出来,这是因为这个Add不仅仅是一个方法,它是一个流程。如果把这个流程理解了,那么整个ArrayList也就懂了。前面遗留的几个不懂得地方在这都有解答

Add方法有两个

(1)Add(E e)

可以看到这个方法永远返回true,所以不应该通过add的返回值来判断是否添加成功。换句话说,Java的大神们在告诉你,我的方法永远都不会出错,你要相信我

[java] view plain copy
  1. public boolean add(E e) {  
  2.         ensureCapacityInternal(size + 1);  // Increments modCount!!  
  3.         elementData[size++] = e;  
  4.         return true;  
  5.     }  
这个方法一共只有三行,其中第一行的才是关键。这里面是在确定ArrayList的容量能否再多加一个。我们看到ArrayList是个无底洞对吧?想放多少放多,实际上都是源于这句话。而这句话的方法在做什么呢?下面给出源代码 [java] view plain copy
  1. private void ensureCapacityInternal(int minCapacity) {  
  2.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
  3.             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  
  4.         }  
  5.   
  6.         ensureExplicitCapacity(minCapacity);  
  7.     }  

ensureCapacityInternal 这个方法首先判断了当前的对象数组是不是默认的空数组,如果是的话,那么就在默认容量(10)和需要的容量中取一个最大值,然后把得到的这个值传递给下一个函数ensureExplicitCapacity。

从这个地方就可以解答了前面的疑问了,如果使用默认的构造方法,那么elementData 就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,当首次插入对象时,取最大值的时候一定是10,再经过后面的扩容,实际上就相当于构造了一个长度为10的对象数组。

[java] view plain copy
  1. private void ensureExplicitCapacity(int minCapacity) {  
  2.         modCount++;  
  3.   
  4.         // overflow-conscious code  
  5.         if (minCapacity - elementData.length > 0)  
  6.             grow(minCapacity);  
  7.     }  
ensureExplicitCapacity 这个方法第一行先不管是干嘛的,看后面的代码,很简单吧! 就是判断需要的容量和现在的用来存储的对象的数组(elementData)那个更大,如果现在已有的不够大了,那就扩容呗! grow(minCapacity)

[java] view plain copy
  1. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;  

[java] view plain copy
  1. private void grow(int minCapacity) {  
  2.         // overflow-conscious code  
  3.         int oldCapacity = elementData.length;  
  4.         int newCapacity = oldCapacity + (oldCapacity >> 1);  
  5.         if (newCapacity - minCapacity < 0)  
  6.             newCapacity = minCapacity;  
  7.         if (newCapacity - MAX_ARRAY_SIZE > 0)  
  8.             newCapacity = hugeCapacity(minCapacity);  
  9.         // minCapacity is usually close to size, so this is a win:  
  10.         elementData = Arrays.copyOf(elementData, newCapacity);  
  11.     }  


[java] view plain copy
  1. private static int hugeCapacity(int minCapacity) {  
  2.         if (minCapacity < 0// overflow  
  3.             throw new OutOfMemoryError();  
  4.         return (minCapacity > MAX_ARRAY_SIZE) ?  
  5.             Integer.MAX_VALUE :  
  6.             MAX_ARRAY_SIZE;  
  7.     }  



这段代码进行了扩容,可以看到扩容通过newCapacity = oldCapacity + (oldCapacity >> 1);这段代码实现,实际上就是将新的容量变为原来容量的1.5倍

但是需要对扩容后的容量进行检验。共有两种可能,

1得到的容量比需要的容量小,为什么会有这种情况呢,溢出了呗。

2得到的容量超过了规定的最大容量,进入hugeCapacity中,如果需要的容量小于0,抛出内存溢出异常,如果需要的容量比规定的最大容量大,那么最大容量只能是 Integer.MAX_VALUE

最后将elementData 通过Array的复制拷贝方法进行了扩容。


由此就完成了整个添加新的元素的过程。从这个过程可以看出,ArrayList也并不是无限大的,它指定了一个最大容量 是Integer.MAX_VALUE - 8,实际最大只能是Integer.MAX_VALUE这个值了。

(2)add(int index, E element)

这个方法是在指定的位置插入元素 element

[java] view plain copy
  1. public void add(int index, E element) {  
  2.         rangeCheckForAdd(index);  
  3.   
  4.         ensureCapacityInternal(size + 1);  // Increments modCount!!  
  5.         System.arraycopy(elementData, index, elementData, index + 1,  
  6.                          size - index);  
  7.         elementData[index] = element;  
  8.         size++;  
  9.     }  
第一行没什么好说的,肯定是检验index是否合法
[java] view plain copy
  1. private void rangeCheckForAdd(int index) {  
  2.         if (index > size || index < 0)  
  3.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
  4.     }  
第二行与前面add方法一致,检验容量并扩容

第三行是arraycopy的方法,在这里面实现的就是将原来的数组从index位置开始,每个元素向后移一位。这是一个本地方法,看不到源代码啦

第四行比较简单啦,就是把要插入的元素放在他应该出现的位置上。

4Remove 方法

(1) remove(int index)

从指定的位置删除元素。实现原理就是把index后面的数据都向前移位。O(n)

[java] view plain copy
  1. public E remove(int index) {  
  2.         rangeCheck(index);  
  3.   
  4.         modCount++;  
  5.         E oldValue = elementData(index);  
  6.   
  7.         int numMoved = size - index - 1;  
  8.         if (numMoved > 0)  
  9.             System.arraycopy(elementData, index+1, elementData, index,  
  10.                              numMoved);  
  11.         elementData[--size] = null// clear to let GC do its work  
  12.   
  13.         return oldValue;  
  14.     }  

[java] view plain copy
  1. private void rangeCheck(int index) {  
  2.         if (index >= size)  
  3.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
  4.     }  
(1)第一行就是检验index的返回,有人会问为什么不检验负数的情况。本人亲自试验了一下,如果index是负数的话,第一行是可以正确执行的,但是在elementData(index)这样地方就会抛出java.lang.ArrayIndexOutOfBoundsException: -1即 数组越界异常其实个人觉得,如果没有第一句 检验,仍然会抛出数组越界异常。只不过多了第一行的话,抛出的异常就是java.lang.IndexOutOfBoundsException: Index: 2, Size: 2,而且会打印出错误信息。又有哪个Java程序员不喜欢看到更详细的异常信息呢?

(2) 计算移动量,如果要删除的元素不是最后一位,就要进行移动。

(3)将移动后的数组末尾赋值null。这里有一句注释,让GC去回收。这是一种释放内存的方式。但是我们不能依赖这种方法, 因为我们永远不知道GC如何能去回收它。

(2)remove(Object o)

删除指定的元素,仅删除符合条件的第一个元素,如果不存在,返回false 即删除失败

[java] view plain copy
  1. public boolean remove(Object o) {  
  2.         if (o == null) {  
  3.             for (int index = 0; index < size; index++)  
  4.                 if (elementData[index] == null) {  
  5.                     fastRemove(index);  
  6.                     return true;  
  7.                 }  
  8.         } else {  
  9.             for (int index = 0; index < size; index++)  
  10.                 if (o.equals(elementData[index])) {  
  11.                     fastRemove(index);  
  12.                     return true;  
  13.                 }  
  14.         }  
  15.         return false;  
  16.     }  

分析这段代码,首先对o进行了非空处理。如果不进行这样的处理,将会引发o.equals的空指针异常。这个是非常常见的处理方式

在这if else语句块中,都用了fastRemove(index) 听上去挺高大上的,快速删除的,其实看了源码就知道,很简单。

[java] view plain copy
  1. private void fastRemove(int index) {  
  2.         modCount++;  
  3.         int numMoved = size - index - 1;  
  4.         if (numMoved > 0)  
  5.             System.arraycopy(elementData, index+1, elementData, index,  
  6.                              numMoved);  
  7.         elementData[--size] = null// clear to let GC do its work  
  8.     }  

这不就是remove(index)方法的后半部门吗?为何不直接调用这个方法呢? 肯定是为了提交一点点效率吗,这毕竟是Java API嘛,要是不能高效一点,是吧、、、


(3)removeAll(Collection<?> c)

在集合中,删除与Collection中元素相等的元素。

[java] view plain copy
  1. public boolean removeAll(Collection<?> c) {  
  2.         Objects.requireNonNull(c);  
  3.         return batchRemove(c, false);  
  4.     }  

第一行是java1.7新出的工具类,用于检验c非空的,如果为空,抛出空指针异常

接下来就是batchRemove(c, false) 这个方法了。源码里虽然没有给出注释,但从第一个if就可以看出,这个方法是用于返回与给定c相同或不同的元素,而且是全部。

[java] view plain copy
  1. private boolean batchRemove(Collection<?> c, boolean complement) {  
  2.        final Object[] elementData = this.elementData;  
  3.        int r = 0, w = 0;  
  4.        boolean modified = false;  
  5.        try {  
  6.            for (; r < size; r++)  
  7.                if (c.contains(elementData[r]) == complement)  
  8.                    elementData[w++] = elementData[r];  
  9.        } finally {  
  10.            // Preserve behavioral compatibility with AbstractCollection,  
  11.            // even if c.contains() throws.  
  12.            if (r != size) {  
  13.                System.arraycopy(elementData, r,  
  14.                                 elementData, w,  
  15.                                 size - r);  
  16.                w += size - r;  
  17.            }  
  18.            if (w != size) {  
  19.                // clear to let GC do its work  
  20.                for (int i = w; i < size; i++)  
  21.                    elementData[i] = null;  
  22.                modCount += size - w;  
  23.                size = w;  
  24.                modified = true;  
  25.            }  
  26.        }  
  27.        return modified;  
  28.    }  
下面来分析一下这段代码。首先对集合中的对象数组进行了一次复制,然后将数组中的元素依次与collection进行对比。try{}块的结果就是得到了一个数组, 数组前w位元素或与collection相同(complement=true的时候)或不同(complement=false)

下面来看finally,先来看第二个if{}代码块,它的作用就是把数组中w以后的元素全部变为null值,让gc来回收。

现在回到finally的第一个if中,看条件(r != size),似乎永远不会满足这个条件吧。上面的for循环一直r++啊,可是别忘了,c.contains(elementData[r])这句话是有可能抛出异常的,如果一旦类型不匹配,就会抛出异常 进入finally中。

这个方法,如果没有删除任何数据,那么将会返回false。


现在我们再来看return batchRemove(c, false);这行的含义吧。它指定了第二个参数为false,所以在batchRemove()保留下来的都是与collection中不同的元素。相同的元素都被删除了。这样就达到了removeAll(Collection<?> c)的目的。

5 迭代器

迭代器可谓是操作ArrayList的神器,在ArrayList内部通过内部类的形式实现了Iterator接口,完成对ArrayList的操作。先让我们来内部一 Itr的源码

[java] view plain copy
  1. private class Itr implements Iterator<E> {  
  2.         int cursor;       // index of next element to return  
  3.         int lastRet = -1// index of last element returned; -1 if no such  
  4.         int expectedModCount = modCount;  
  5.   
  6.         public boolean hasNext() {  
  7.             return cursor != size;  
  8.         }  
  9.   
  10.         @SuppressWarnings("unchecked")  
  11.         public E next() {  
  12.             checkForComodification();  
  13.             int i = cursor;  
  14.             if (i >= size)  
  15.                 throw new NoSuchElementException();  
  16.             Object[] elementData = ArrayList.this.elementData;  
  17.             if (i >= elementData.length)  
  18.                 throw new ConcurrentModificationException();  
  19.             cursor = i + 1;  
  20.             return (E) elementData[lastRet = i];  
  21.         }  
  22.   
  23.         public void remove() {  
  24.             if (lastRet < 0)  
  25.                 throw new IllegalStateException();  
  26.             checkForComodification();  
  27.   
  28.             try {  
  29.                 ArrayList.this.remove(lastRet);  
  30.                 cursor = lastRet;  
  31.                 lastRet = -1;  
  32.                 expectedModCount = modCount;  
  33.             } catch (IndexOutOfBoundsException ex) {  
  34.                 throw new ConcurrentModificationException();  
  35.             }  
  36.         }  
  37.   
  38.         @Override  
  39.         @SuppressWarnings("unchecked")  
  40.         public void forEachRemaining(Consumer<? super E> consumer) {  
  41.             Objects.requireNonNull(consumer);  
  42.             final int size = ArrayList.this.size;  
  43.             int i = cursor;  
  44.             if (i >= size) {  
  45.                 return;  
  46.             }  
  47.             final Object[] elementData = ArrayList.this.elementData;  
  48.             if (i >= elementData.length) {  
  49.                 throw new ConcurrentModificationException();  
  50.             }  
  51.             while (i != size && modCount == expectedModCount) {  
  52.                 consumer.accept((E) elementData[i++]);  
  53.             }  
  54.             // update once at end of iteration to reduce heap write traffic  
  55.             cursor = i;  
  56.             lastRet = i - 1;  
  57.             checkForComodification();  
  58.         }  
  59.   
  60.         final void checkForComodification() {  
  61.             if (modCount != expectedModCount)  
  62.                 throw new ConcurrentModificationException();  
  63.         }  
  64.     }  


这个类并不长,让我们来分析一下

(1) 属性

a  游标

int cursor; 我们知道iterator是始终向前走的,就是这个游标始终在++的原因

b 末尾标识

 int lastRe 标识了最后一个返回的元素的索引位置,-1代表这个元素不存在

C 操作数标识

 int expectedModCount = modCount;  这个非常重要,它用来校验在使用iterator期间,是否存在非Iterator的操作对ArrayList进行了修改。

(2)checkForComodification 方法

这个方法很简单,但是可以看到在这个内部类中,几乎所有方法都在调用它。它所做的工作就是校验在使用iterator期间,是否存在非Iterator的操作对ArrayList进行了修改。

在ArrayList中,有很多操作都修改了一个变量,modCount。每次进行操作,modCount都在++。前面一直不理解这个有什么用,在这看到了它的用意。Iterator的游标特性决定了它对ArrayList中元素在这一时刻的位置很敏感,如果当前游标在index位置,而有其他操作在index-1的位置上插入了一个元素,那么调用iterator的next()方法,返回的还是当前这个元素,这样就乱了。为了避免这个情况发生,需要在这个期间把ArrayList“锁住“。它并没有实现真正的锁,所以采用了这个校验的方式。

(3)next()

返回当前游标位置的元素,这里面第一个if判断的条件很有意思。因此游标前移,当移动到一个不存在数据的地方,它抛出了异常。而并没有返回null。这就是我们为什么在使用iterator的时候不能用(null==iterator.next())来判断的原因。而是在要每次循环开始的时候判断iterator.hasNext()。

(4) remove()

删除lastRe 所标识位置的元素。我们可以把它理解为当前元素。在try前面有一个校验,保证元素没有被改动过,要不就删错了。

在try{}语句块中,首先删除了lastRe标识的元素,然后让游标指向了这个位置。我们知道在删除元素以后,这个位置有了新的元素,这样再次调用next()的时候不会出现空指针异常,更不会跳过一个元素。

最后expectedModCount = modCount;这句相当于释放了锁。也是在表示,在我Iterator的地盘,只有我能够去修改mod,别人动了就不行!

6 set 与get


set将指定位置的元素替换

[java] view plain copy
  1. public E set(int index, E element) {  
  2.         rangeCheck(index);  
  3.   
  4.         E oldValue = elementData(index);  
  5.         elementData[index] = element;  
  6.         return oldValue;  
  7.     }  
get  获取指定位置的的元素

[java] view plain copy
  1. public E get(int index) {  
  2.        rangeCheck(index);  
  3.   
  4.        return elementData(index);  
  5.    }  

[java] view plain copy
  1. private void rangeCheck(int index) {  
  2.         if (index >= size)  
  3.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
  4.     }  

这两个方法里面  都有一步rangeCheck,即检验输入索引位置是否越界,它将会引发越界异常。

7 contains 、indexOf、lastIndexOf

这三个方法功能很相近

第一个是查看ArrayList中是否含有指定元素

第二个是返回指定元素的第一个出现的索引位置

第三个返回指定元素的最后一个出现的索引位置

这是一组依赖的方法,实际上执行的是同一段代码。

[java] view plain copy
  1. public boolean contains(Object o) {  
  2.         return indexOf(o) >= 0;  
  3.     }  

[java] view plain copy
  1. public int indexOf(Object o) {  
  2.         if (o == null) {  
  3.             for (int i = 0; i < size; i++)  
  4.                 if (elementData[i]==null)  
  5.                     return i;  
  6.         } else {  
  7.             for (int i = 0; i < size; i++)  
  8.                 if (o.equals(elementData[i]))  
  9.                     return i;  
  10.         }  
  11.         return -1;  
  12.     }  
[java] view plain copy
  1. public int lastIndexOf(Object o) {  
  2.        if (o == null) {  
  3.            for (int i = size-1; i >= 0; i--)  
  4.                if (elementData[i]==null)  
  5.                    return i;  
  6.        } else {  
  7.            for (int i = size-1; i >= 0; i--)  
  8.                if (o.equals(elementData[i]))  
  9.                    return i;  
  10.        }  
  11.        return -1;  
  12.    }  


这段代码很简单,就是一个简单的遍历,只是变量的起点不同而已,就实现了不同的功能。indexof的代码有没有觉得似曾相识呢?就是跟remove的方法差不多呢,这也再一次提醒我们,如果要使用一个对象的方法时,一定要注意解决空指针异常

8 clone

拷贝,重写了Objec类的拷贝方法,ArrayList的拷贝是浅拷贝

[java] view plain copy
  1. public Object clone() {  
  2.         try {  
  3.             ArrayList<?> v = (ArrayList<?>) super.clone();  
  4.             v.elementData = Arrays.copyOf(elementData, size);  
  5.             v.modCount = 0;  
  6.             return v;  
  7.         } catch (CloneNotSupportedException e) {  
  8.             // this shouldn't happen, since we are Cloneable  
  9.             throw new InternalError(e);  
  10.         }  
  11.     }  

这里面用到了前面看到很多次的方法,Arrays.copyOf()

9 sort

排序方法,这个方法用到的是Array类的静态排序方法

[java] view plain copy
  1. public void sort(Comparator<? super E> c) {  
  2.         final int expectedModCount = modCount;  
  3.         Arrays.sort((E[]) elementData, 0, size, c);  
  4.         if (modCount != expectedModCount) {  
  5.             throw new ConcurrentModificationException();  
  6.         }  
  7.         modCount++;  
  8.     }  

10 总结

上面介绍了ArrayList中常用的方法,第一次较为认真地读源代码,确实发现了不少秘密。

(1) ArrayList是用Object数组来实现了,所谓的动态扩容,实际上就是在不断地产生新的数组,然后进行复制。

(2)在使用ArrayList插入大量元素时,应该有选择的申请一个容量,而不是使用默认的容量。扩容也是会消耗时间的

(3) ArrayList不是线程安全的,它的操作中没有使用同步方法。如果想使用线程安全的,可以用Vector,也可以使用Collections.synchronizedList来创建线程安全的list。