Java集合框架剖析(3)——ArrayList

绝地灬酷狼 2022-05-28 06:12 196阅读 0赞

# ArrayList #

![这里写图片描述][70]  
ArrayList继承了AbstractList，实现了List。它是一个数组队列，相当于动态数组。提供了相关的添加、删除、修改和遍历等功能。

ArrayList实现了RandomAccess接口，即提供了随机访问功能。RandomAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号来快速获取元素对象，这就是快速随机访问。下文会比较List的“快速随机访问”和使用“Iterator迭代器访问”的效率。

ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

和Vector不同，ArrayList中的操作是非线程安全的。所以建议在单线程中使用ArrayList，在多线程中选择Vector或者CopyOnWriteArrayList。

## 接口总览 ##

![这里写图片描述][70 1]  
ArrayList包含了两个重要的对象：elementData和size。  
![这里写图片描述][70 2]  
elementData是Object\[\]类型的数组，它保存了添加到ArrayList中的元素。实际上，elementData是一个动态数组，我们能通过ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity。如果通过不含参数的构造函数来创建ArrayList，则elementData是一个空数组（后面会调整其大小）。elementData数组的大小会根据ArrayList容量的增长而动态的增长。  
size则是动态数组实际的大小。

## 源码解析 ##

### 属性 ###

![这里写图片描述][70 3]  
看`transient Object[] elementData` 的注释，当一个空的ArrayList加入第一个元素的时候就会将容量扩充到10(DEFAULT\_CAPACITY)

### 构造函数 ###

![这里写图片描述][70 4]

### 容量相关 ###

![这里写图片描述][70 5]  
public的接口可以提供给外部调用  
![这里写图片描述][70 6]  
当然还有两个内部private的接口用于扩充容量  
![这里写图片描述][70 7]  
另外要提一下的是ArrayList是有最大长度的，超过这个长度就会有OutOfMemory的Exception  
![这里写图片描述][70 8]

## 搜索相关 ##

![这里写图片描述][70 9]

## clone ##

![这里写图片描述][70 10]

## toArray ##

![这里写图片描述][70 11]

## 位置操作 ##

![这里写图片描述][70 12]  
![这里写图片描述][70 13]  
![这里写图片描述][70 14]  
![这里写图片描述][70 15]  
![这里写图片描述][70 16]  
![这里写图片描述][70 17]

## 迭代器 ##

（这边需要重写）

/******************************** Iterators ************************************/  
    
        /** * 该部分的方法重写了AbstractList抽象类中Iterator部分的方法，因为ArrayList继承 * 了AbstractList，基本大同小异，只是这里针对本类的数组，思想与AbstractList一致 * 可以参照上一章Collection架构与源码分析的AbatractList部分 */  
        public ListIterator<E> listIterator(int index) {  
            if (index < 0 || index > size)  
                throw new IndexOutOfBoundsException("Index: "+index);  
            return new ListItr(index);  
        }  
    
        public ListIterator<E> listIterator() {  
            return new ListItr(0);  
        }  
    
        public Iterator<E> iterator() {  
            return new Itr();  
        }  
    
        private class Itr implements Iterator<E> {   
            int cursor;       // index of next element to return 
            int lastRet = -1; // index of last element returned; -1 if no such 
            int expectedModCount = modCount;  
    
            public boolean hasNext() {  
                return cursor != size;  
            }  
    
            @SuppressWarnings("unchecked")  
            public E next() {  
                checkForComodification();  
                int i = cursor;  
                if (i >= size)  
                    throw new NoSuchElementException();  
                Object[] elementData = ArrayList.this.elementData;  
                if (i >= elementData.length)  
                    throw new ConcurrentModificationException();  
                cursor = i + 1;  
                return (E) elementData[lastRet = i];  
            }  
    
            public void remove() {  
                if (lastRet < 0)  
                    throw new IllegalStateException();  
                checkForComodification();  
    
                try {  
                    ArrayList.this.remove(lastRet);  
                    cursor = lastRet;  
                    lastRet = -1;  
                    expectedModCount = modCount;  
                } catch (IndexOutOfBoundsException ex) {  
                    throw new ConcurrentModificationException();  
                }  
            }  
    
            final void checkForComodification() {  
                if (modCount != expectedModCount)  
                    throw new ConcurrentModificationException();  
            }  
        }  
    
        private class ListItr extends Itr implements ListIterator<E> {   
            ListItr(int index) {  
                super();  
                cursor = index;  
            }  
    
            public boolean hasPrevious() {  
                return cursor != 0;  
            }  
    
            public int nextIndex() {  
                return cursor;  
            }  
    
            public int previousIndex() {  
                return cursor - 1;  
            }  
    
            @SuppressWarnings("unchecked")  
            public E previous() {  
                checkForComodification();  
                int i = cursor - 1;  
                if (i < 0)  
                    throw new NoSuchElementException();  
                Object[] elementData = ArrayList.this.elementData;  
                if (i >= elementData.length)  
                    throw new ConcurrentModificationException();  
                cursor = i;  
                return (E) elementData[lastRet = i];  
            }  
    
            public void set(E e) {  
                if (lastRet < 0)  
                    throw new IllegalStateException();  
                checkForComodification();  
    
                try {  
                    ArrayList.this.set(lastRet, e);  
                } catch (IndexOutOfBoundsException ex) {  
                    throw new ConcurrentModificationException();  
                }  
            }  
    
            public void add(E e) {  
                checkForComodification();  
    
                try {  
                    int i = cursor;  
                    ArrayList.this.add(i, e);  
                    cursor = i + 1;  
                    lastRet = -1;  
                    expectedModCount = modCount;  
                } catch (IndexOutOfBoundsException ex) {  
                    throw new ConcurrentModificationException();  
                }  
            }  
        }  
    
        public List<E> subList(int fromIndex, int toIndex) {  
            subListRangeCheck(fromIndex, toIndex, size);  
            return new SubList(this, 0, fromIndex, toIndex);  
        }  
    
        static void subListRangeCheck(int fromIndex, int toIndex, int size) {  
            if (fromIndex < 0)  
                throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);  
            if (toIndex > size)  
                throw new IndexOutOfBoundsException("toIndex = " + toIndex);  
            if (fromIndex > toIndex)  
                throw new IllegalArgumentException("fromIndex(" + fromIndex +  
                                                   ") > toIndex(" + toIndex + ")");  
        }  
    
        private class SubList extends AbstractList<E> implements RandomAccess {   
            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.parentOffset = fromIndex;  
                this.offset = offset + fromIndex;  
                this.size = toIndex - fromIndex;  
                this.modCount = ArrayList.this.modCount;  
            }  
    
            public E set(int index, E e) {  
                rangeCheck(index);  
                checkForComodification();  
                E oldValue = ArrayList.this.elementData(offset + index);  
                ArrayList.this.elementData[offset + index] = e;  
                return oldValue;  
            }  
    
            public E get(int index) {  
                rangeCheck(index);  
                checkForComodification();  
                return ArrayList.this.elementData(offset + index);  
            }  
    
            public int size() {  
                checkForComodification();  
                return this.size;  
            }  
    
            public void add(int index, E e) {  
                rangeCheckForAdd(index);  
                checkForComodification();  
                parent.add(parentOffset + index, e);  
                this.modCount = parent.modCount;  
                this.size++;  
            }  
    
            public E remove(int index) {  
                rangeCheck(index);  
                checkForComodification();  
                E result = parent.remove(parentOffset + index);  
                this.modCount = parent.modCount;  
                this.size--;  
                return result;  
            }  
    
            protected void removeRange(int fromIndex, int toIndex) {  
                checkForComodification();  
                parent.removeRange(parentOffset + fromIndex,  
                                   parentOffset + toIndex);  
                this.modCount = parent.modCount;  
                this.size -= toIndex - fromIndex;  
            }  
    
            public boolean addAll(Collection<? extends E> c) {  
                return addAll(this.size, c);  
            }  
    
            public boolean addAll(int index, Collection<? extends E> c) {  
                rangeCheckForAdd(index);  
                int cSize = c.size();  
                if (cSize==0)  
                    return false;  
    
                checkForComodification();  
                parent.addAll(parentOffset + index, c);  
                this.modCount = parent.modCount;  
                this.size += cSize;  
                return true;  
            }  
    
            public Iterator<E> iterator() {  
                return listIterator();  
            }  
    
            public ListIterator<E> listIterator(final int index) {  
                checkForComodification();  
                rangeCheckForAdd(index);  
                final int offset = this.offset;  
    
                return new ListIterator<E>() {  
                    int cursor = index;  
                    int lastRet = -1;  
                    int expectedModCount = ArrayList.this.modCount;  
    
                    public boolean hasNext() {  
                        return cursor != SubList.this.size;  
                    }  
    
                    @SuppressWarnings("unchecked")  
                    public E next() {  
                        checkForComodification();  
                        int i = cursor;  
                        if (i >= SubList.this.size)  
                            throw new NoSuchElementException();  
                        Object[] elementData = ArrayList.this.elementData;  
                        if (offset + i >= elementData.length)  
                            throw new ConcurrentModificationException();  
                        cursor = i + 1;  
                        return (E) elementData[offset + (lastRet = i)];  
                    }  
    
                    public boolean hasPrevious() {  
                        return cursor != 0;  
                    }  
    
                    @SuppressWarnings("unchecked")  
                    public E previous() {  
                        checkForComodification();  
                        int i = cursor - 1;  
                        if (i < 0)  
                            throw new NoSuchElementException();  
                        Object[] elementData = ArrayList.this.elementData;  
                        if (offset + i >= elementData.length)  
                            throw new ConcurrentModificationException();  
                        cursor = i;  
                        return (E) elementData[offset + (lastRet = i)];  
                    }  
    
                    public int nextIndex() {  
                        return cursor;  
                    }  
    
                    public int previousIndex() {  
                        return cursor - 1;  
                    }  
    
                    public void remove() {  
                        if (lastRet < 0)  
                            throw new IllegalStateException();  
                        checkForComodification();  
    
                        try {  
                            SubList.this.remove(lastRet);  
                            cursor = lastRet;  
                            lastRet = -1;  
                            expectedModCount = ArrayList.this.modCount;  
                        } catch (IndexOutOfBoundsException ex) {  
                            throw new ConcurrentModificationException();  
                        }  
                    }  
    
                    public void set(E e) {  
                        if (lastRet < 0)  
                            throw new IllegalStateException();  
                        checkForComodification();  
    
                        try {  
                            ArrayList.this.set(offset + lastRet, e);  
                        } catch (IndexOutOfBoundsException ex) {  
                            throw new ConcurrentModificationException();  
                        }  
                    }  
    
                    public void add(E e) {  
                        checkForComodification();  
    
                        try {  
                            int i = cursor;  
                            SubList.this.add(i, e);  
                            cursor = i + 1;  
                            lastRet = -1;  
                            expectedModCount = ArrayList.this.modCount;  
                        } catch (IndexOutOfBoundsException ex) {  
                            throw new ConcurrentModificationException();  
                        }  
                    }  
    
                    final void checkForComodification() {  
                        if (expectedModCount != ArrayList.this.modCount)  
                            throw new ConcurrentModificationException();  
                    }  
                };  
            }  
    
            public List<E> subList(int fromIndex, int toIndex) {  
                subListRangeCheck(fromIndex, toIndex, size);  
                return new SubList(this, offset, fromIndex, toIndex);  
            }  
    
            private void rangeCheck(int index) {  
                if (index < 0 || index >= this.size)  
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
            }  
    
            private void rangeCheckForAdd(int index) {  
                if (index < 0 || index > this.size)  
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
            }  
    
            private String outOfBoundsMsg(int index) {  
                return "Index: "+index+", Size: "+this.size;  
            }  
    
            private void checkForComodification() {  
                if (ArrayList.this.modCount != this.modCount)  
                    throw new ConcurrentModificationException();  
            }  
        }  
    }

## 总结 ##

1.  ArrayList实际上是通过一个数组去保存数据的，当我们构造ArrayList时，如果使用默认构造函数，最后ArrayList的默认容量大小是10。
2.  当ArrayList容量不足以容纳全部元素时，ArrayList会自动扩张容量，新的容量 = 原始容量 + 原始容量 / 2。
3.  ArrayList的克隆函数，即是将全部元素克隆到一个数组中。
4.  ArrayList实现java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写出“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

## ArrayList遍历方式 ##

ArrayList支持三种遍历方式  
![这里写图片描述][70 18]  
猜猜哪个效率最高！！  
其实应该是随机访问效率最高， 因为ArrayList内部的存储就是个数组，直接用内存地址偏移寻址肯定要比迭代器快。  
可以做个试验：

import java.util.*;  
    
    /* * @description ArrayList三种遍历方式效率的测试 * @author eson_15 */  
    public class ArrayListRandomAccessTest {  
    
        public static void main(String[] args) {  
            List<Integer> list = new ArrayList<Integer>();  
            for (int i=0; i<500000; i++)  
                list.add(i);  
            isRandomAccessSupported(list);//判断是否支持RandomAccess 
            iteratorThroughRandomAccess(list) ;  
            iteratorThroughIterator(list) ;  
            iteratorThroughFor(list) ;  
    
        }  
    
        private static void isRandomAccessSupported(List<Integer> list) {  
            if (list instanceof RandomAccess) {  
                System.out.println("RandomAccess implemented!");  
            } else {  
                System.out.println("RandomAccess not implemented!");  
            }  
    
        }  
    
        public static void iteratorThroughRandomAccess(List<Integer> list) {  
    
            long startTime;  
            long endTime;  
            startTime = System.currentTimeMillis();  
            for (int i=0; i<list.size(); i++) {  
                list.get(i);  
            }  
            endTime = System.currentTimeMillis();  
            long interval = endTime - startTime;  
            System.out.println("RandomAccess遍历时间：" + interval+" ms");  
        }  
    
        public static void iteratorThroughIterator(List<Integer> list) {  
    
            long startTime;  
            long endTime;  
            startTime = System.currentTimeMillis();  
            for(Iterator<Integer> it = list.iterator(); it.hasNext(); ) {  
                it.next();  
            }  
            endTime = System.currentTimeMillis();  
            long interval = endTime - startTime;  
            System.out.println("Iterator遍历时间：" + interval+" ms");  
        }  
    
    
        @SuppressWarnings("unused")  
        public static void iteratorThroughFor(List<Integer> list) {  
    
            long startTime;  
            long endTime;  
            startTime = System.currentTimeMillis();  
            for(Object obj : list)  
                ;  
            endTime = System.currentTimeMillis();  
            long interval = endTime - startTime;  
            System.out.println("For循环遍历时间：" + interval+" ms");  
        }  
    }

测试结果（多次平均值）：

<table> 
 <thead> 
  <tr> 
   <th>RandomAccess(ms)</th> 
   <th align="center">Iterator(ms)</th> 
   <th align="right">For(ms)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>4.9</td> 
   <td align="center">7.1</td> 
   <td align="right">7.4</td> 
  </tr> 
 </tbody> 
</table>

[70]: /images/20220528/20c8544e7f714c73b5d81058d35f6171.png
[70 1]: /images/20220528/b608a56972ac43fe85981e2cf05ac498.png
[70 2]: /images/20220528/bc2281b202784ac78738a462bb75153c.png
[70 3]: /images/20220528/7f76b57d437d474da5a13609f43e6f7f.png
[70 4]: /images/20220528/22caf954eea54ff881cc97bd5cd7aac0.png
[70 5]: /images/20220528/c66cba7d66e54606b9ed096f1c386c71.png
[70 6]: /images/20220528/9ac05cc2599446998b4e345a16dab0b1.png
[70 7]: /images/20220528/4936b04194ef4315947e2370de73c57c.png
[70 8]: /images/20220528/e9b5d7a8474641a6b0d9fb19c403b77a.png
[70 9]: /images/20220528/bd24138e2ac949c8ad2479e2077cb503.png
[70 10]: /images/20220528/e41435606de84b72a6766ac3dbf57818.png
[70 11]: /images/20220528/c8c17c0c4cbe4063b4850691e48b4fa4.png
[70 12]: /images/20220528/1d71a55c5d3f45b0a542ddeabc0083f9.png
[70 13]: /images/20220528/2d7b0bb7ef634665848cb66e48e36159.png
[70 14]: /images/20220528/127230478f3447009442afcd5e584506.png
[70 15]: /images/20220528/f42b4cb5351e4107948c84ce3a5c9c2c.png
[70 16]: /images/20220528/f1a13ea749c04056b6fd38e41d3b1347.png
[70 17]: /images/20220528/a43331f7d1d447fcac3108c3c2fb8d20.png
[70 18]: /images/20220528/a803547a9afb4a8e990e06ddf19d717f.png