java ArrayList实现原理解析

男娘i 2021-09-26 16:56 378阅读 0赞

主要参照jdk1.6,1.7 。  
为了便于理解，对源码进行了一定改造，并按层次进行解析。  
本文只讨论关键的方法。

主要实现的接口  
Iterable：返回一个可迭代的类。  
Collection：集合类，定义了一系列处理集合的方法。比如add，remove，size等。

主要的父类  
AbstractList：根据jdk版本的不同，会有一些具体的实现方法。不过最需要关注的一点是这个类定义了modCount。

ArrayList的算法结构  
本体是一个数组，java中定长的那个数组。  
所以说，ArrayList类的本体是这个。

/** * * @author nayi224 * https://blog.csdn.net/nayi_224 * 2018-5-14下午10:27:51 */
    public class NayiArrayList1 { 
    
        private Object[] element;
    
        public NayiArrayList1(){
            this(10);
        }
    
        public NayiArrayList1(int size){
            this.element = new Object[size];
        }
    
    }

ArrayList通过内部的代码使其成为一个可变长的数组。  
当添加一个元素时，若长度足够，会直接添加，否则会将数组复制为一个1.5倍长+1的数组。若在数组中间添加或删除一个元素，则会对这个对象之后的部分向后复制。  
ArrayList中还有一个size属性来记录当前储存数据的长度，用以辅助上述操作。

简易实现代码：

import java.util.Arrays;
    
    /** * * @author nayi224 * https://blog.csdn.net/nayi_224 * 2018-5-14下午10:45:12 */
    public class NayiArrayList2 { 
    
        private Object[] elementData;
    
        private int size;
    
        public NayiArrayList2(){
            this(10);
        }
    
        public NayiArrayList2(int size){
            this.elementData = new Object[size];
        }
    
        public boolean add(Object e){
            ensureCapacity(size + 1);
            elementData[size++] = e;
            return true;
        }
    
        public Object remove(int index) {
            // RangeCheck(index);
    
            // modCount++;
            Object oldValue = elementData[index];
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index + 1, elementData, index,
                        numMoved);
            elementData[--size] = null; // Let gc do its work
    
            return oldValue;
        }
    
        public Object get(int index) {
            //RangeCheck(index);
    
            return elementData[index];
        }
    
        /** * 该方法使数组有了一个自增机制 * @param minCapacity 新数组的长度 */
        public void ensureCapacity(int minCapacity) {
            // modCount++;
            int oldCapacity = elementData.length;
            if (minCapacity > oldCapacity) {
                Object oldData[] = elementData;
                int newCapacity = (oldCapacity * 3) / 2 + 1;
                if (newCapacity < minCapacity)
                    newCapacity = minCapacity;
                // minCapacity is usually close to size, so this is a win:
                elementData = Arrays.copyOf(elementData, newCapacity);
            }
        }
    
    }

我这里只实现了add，remove，get三个方法，并且省略了全部校验。  
可以很清晰的看出，get方法只是按照下标去取值，效率是非常高的。add与remove方法首先会有一个运算，这几乎不会影响效率。但是它需要复制所修改位置之后的全部元素，甚至可能需要对原数组进行全量复制，这个效率可能会非常差。

一些关键的校验

private void RangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(
                "Index: "+index+", Size: "+size);
        }

我们最熟悉的数组下标越界。

public NayiArrayList2(int size){
            if (size < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                        size);
    
            this.elementData = new Object[size];
        }

初始化时的校验，数组的长度不能是负的。

迭代机制  
我在[https://blog.csdn.net/nayi\_224/article/details/80102394][https_blog.csdn.net_nayi_224_article_details_80102394]这篇文章里做过比较完整的整理。

fast-fail机制  
主要通过modCount这个属性实现。实现原理为在对elementData进行结构上的修改时，进行modCount++。在迭代的时候检查modCount的值，若modCount值发生了变化，则说明elementData的结构发生了变化，需要跑出异常。注意，在并发情况下，这个机制会返回错误的结果。官方的建议是，这个机制应该只用来调试，而不是用它来真正的控制异常。  
具体的讨论同样在这篇文章中进行了讨论[https://blog.csdn.net/nayi\_224/article/details/80102394][https_blog.csdn.net_nayi_224_article_details_80102394]

ArrayList最核心的部分只有这些了，剩下的只是在堆代码，建议自行查看。  
如果不知道查看方法的话。写上这句话`java.util.ArrayList a;`按住ctrl再左键点击ArrayList。

[https_blog.csdn.net_nayi_224_article_details_80102394]: https://blog.csdn.net/nayi_224/article/details/80102394