Java集合-ArrayList源码解析-JDK1.8

绝地灬酷狼 2024-04-18 20:14 58阅读 0赞

◆

ArrayList简介

◆

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

1.  AbstractList、List提供了添加、删除、修改、遍历等功能。
2.  RandmoAccess提供了随机访问功能
3.  Cloneable提供了可以被克隆的功能
4.  Serializable提供了序列化的功能
5.  和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或CopyOnWriteArrayList。

◆

ArrayList的属性

◆

/**	
         * 数组默认的大小	
         */	
        private static final int DEFAULT_CAPACITY = 10;	
    
    	
        /**	
         * 使用数组大小为0时的默认缓冲区	
         */	
        private static final Object[] EMPTY_ELEMENTDATA = {};	
    
    	
        /**	
         * 使用ArrayList(int initialCapacity)构造方法时且initialCapacity为0时缓冲区	
         */	
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};	
    
    	
        /**	
         * 真实存储arraylist元素的数组缓冲区	
         */	
        transient Object[] elementData; // non-private to simplify nested class access	
    
    	
        /**	
         * List的实际大小	
         */	
        private int size;	
        /**	
         * 数组可分配的最大大小	
         */	
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;	
         /**	
         *  特别注意这个是继承自AbstractList的属性，用来记录List被修改的次数	
         */	
        protected transient int modCount = 0;

◆

ArrayList的构造方法

◆

/**	
         * 无参构造方法，初始化elementData	
         */	
        public ArrayList() {	
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;	
        }	
        	
        /**	
         * 根据参数构建具有初始大小的构造方法	
         */	
        public ArrayList(int initialCapacity) {	
            if (initialCapacity > 0) {	
                this.elementData = new Object[initialCapacity];	
            } else if (initialCapacity == 0) {	
                this.elementData = EMPTY_ELEMENTDATA;	
            } else {	
                throw new IllegalArgumentException("Illegal Capacity: "+	
                        initialCapacity);	
            }	
        }	
        /**	
         * 创建一个包含collection的ArrayList	
         */	
        public ArrayList(Collection<? extends E> c) {	
            elementData = c.toArray();	
            if ((size = elementData.length) != 0) {	
                // c.toArray might (incorrectly) not return Object[] (see 6260652)	
                if (elementData.getClass() != Object[].class)	
                    elementData = Arrays.copyOf(elementData, size, Object[].class);	
            } else {	
                // replace with empty array.	
                this.elementData = EMPTY_ELEMENTDATA;	
            }	
        }

◆

ArrayList的方法

◆

接下来我们就以ArrayList的几个比较经典的方法来看一下它是如何设计的。

首先是添加方法，添加的方法一共有3个：

/**	
         * 添加元素	
         */	
        public boolean add(E e) {	
            //计算数组最新的容量，以及判断是否需要扩容	
            ensureCapacityInternal(size + 1);  // Increments modCount!!	
            elementData[size++] = e;	
            return true;	
        }	
    
    	
        /**	
         * 指定索引添加元素	
         */	
        public void add(int index, E element) {	
            //判断索引是否越界	
            rangeCheckForAdd(index);	
            //计算数组最新的容量，以及判断是否需要扩容	
            ensureCapacityInternal(size + 1);  // Increments modCount!!	
            //调用系统底层的复制方法	
            System.arraycopy(elementData, index, elementData, index + 1,	
                    size - index);	
            elementData[index] = element;	
            //List长度+1	
            size++;	
        }	
         /**	
         * 添加一个集合	
         */	
        public boolean addAll(Collection<? extends E> c) {	
            Object[] a = c.toArray();	
            int numNew = a.length;	
            ensureCapacityInternal(size + numNew);  // Increments modCount	
            System.arraycopy(a, 0, elementData, size, numNew);	
            size += numNew;	
            return numNew != 0;	
        }

仔细观察上方三个添加的方法，它们都调用了ensureCapacityInternal方法，这个方法的参数是执行当前添加操作所需要的数组容量。它会根据传递的参数来计算数组是否需要扩容，如果需要扩容则完成扩容操作。

不同之处在于，上方的两个方法添加的只有一个元素，所以传的size+1，而addAll因为是添加的一个集合所以传的参数是size+集合的长度。

接着看这个方法的实现：

/**	
         * 计算数组最新的容量	
         * @param minCapacity	
         */	
        private void ensureCapacityInternal(int minCapacity) {	
            //如果创建ArrayList时指定大小为0	
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {	
                //如果本次添加的大小比初始容量10大的话则不使用默认的容量10，直接使用本次添加的大小作为初始容量	
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);	
            }	
    
    	
            ensureExplicitCapacity(minCapacity);	
        }	
    
    	
        /**	
         * 记录修改次数，调用扩容方法	
         * @param 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);	
            // 调用Arrays的复制方法更新数据缓冲池	
            elementData = Arrays.copyOf(elementData, newCapacity);	
        }	
          //判断容量是否溢出	
        private static int hugeCapacity(int minCapacity) {	
            if (minCapacity < 0) // overflow	
                throw new OutOfMemoryError();	
            return (minCapacity > MAX_ARRAY_SIZE) ?	
                    Integer.MAX_VALUE :	
                    MAX_ARRAY_SIZE;	
        }

以上就是ArrayList动态扩容的实现方式了，这里注意一下扩容是通过新建一个数组来替换原先的数组来进行的：

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;	
        }	
     /**	
         * 删除指定索引的元素	
         *	
         */	
        public E remove(int index) {	
            //判断是否越界	
            rangeCheck(index);	
            //记录修改次数	
            modCount++;	
            E oldValue = elementData(index);	
            //计算需要移动的位置	
            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	
    
    	
            return oldValue;	
        }	
        /*	
         * 删除指定元素	
         */	
        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	
        }

需要注意的是删除一个元素也是通过底层的方法实现的。

接着看get和set相对就比较简单了。

public E get(int index) {	
            //判断索引是否越界	
            rangeCheck(index);	
            return elementData(index);	
        }	
         /**	
         * 判断索引是否越界	
         */	
        private void rangeCheck(int index) {	
            if (index >= size)	
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));	
        }	
        public E set(int index, E element) {	
            //判断索引是否越界	
            rangeCheck(index);	
            //获取此索引原先的值	
            E oldValue = elementData(index);	
            elementData[index] = element;	
            return oldValue;	
        }

**看了ArrayList的增删改查方法相信你已经明白了为什么一直有人告诉你ArrayList查询修改效率高而添加和删除效率低了。**

ArrayList的序列化方式同样是比较有意思的，一开始看到ArrayList实现了Serializable我们就知道它是可以序列化的，但是实际存储的数组elementData却是transient，观看下方代码你就可以找到答案：

/**	
         * 将List写入s，注意先写容量，然后在写数据	
         * @param s	
         * @throws java.io.IOException	
         */	
        private void writeObject(java.io.ObjectOutputStream s)	
                throws java.io.IOException{	
            // Write out element count, and any hidden stuff	
            int expectedModCount = modCount;	
            s.defaultWriteObject();	
    
    	
            // 首先写数组容量	
            s.writeInt(size);	
    
    	
            // 遍历写数组中的元素	
            for (int i=0; i<size; i++) {	
                s.writeObject(elementData[i]);	
            }	
    
    	
            if (modCount != expectedModCount) {	
                throw new ConcurrentModificationException();	
            }	
        }	
    
    	
        /**	
         * 读取s中的List	
         */	
        private void readObject(java.io.ObjectInputStream s)	
                throws java.io.IOException, ClassNotFoundException {	
            elementData = EMPTY_ELEMENTDATA;	
    
    	
            // Read in size, and any hidden stuff	
            s.defaultReadObject();	
    
    	
            // 首先读数组容量	
            s.readInt(); // ignored	
    
    	
            if (size > 0) {	
                // be like clone(), allocate array based upon size not capacity	
                ensureCapacityInternal(size);	
    
    	
                Object[] a = elementData;	
                // Read in all elements in the proper order.	
                for (int i=0; i<size; i++) {	
                    a[i] = s.readObject();	
                }	
            }	
        }

鉴于篇幅有限，本篇文章仅列出上方部分代码，ArrayList完整源码解析请 点击下方“阅读原文”查看！！！

![640?wx\_fmt=gif][640_wx_fmt_gif]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

收藏转发好看再走呗!

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7b4820cd23784bf5955be5a8c252f6fe.gif
[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a7bc5114639a4ad2b8100ee5f1b80ffd.png
[640_wx_fmt_gif 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3711aab193af4e0ea0f03c608102abb0.gif