Java集合系列之ArrayList底层实现原理

Love The Way You Lie 2022-05-18 02:37 226阅读 0赞

# ArrayList简介 #

ArrayList是我们开发中非常常用的数据存储容器之一，其底层是数组实现的，我们可以在集合中存储任意类型的数据，ArrayList是线程不安全的，非常适合用于对元素进行查找，效率非常高。

# 源码分析 #

![70][]

创建了一个大小为0的数组，在后面会用到。

![70 1][]

声明了一个数组。

![70 2][]

ArrayList的无参构造方法，将前面声明创建的大小为0的数组赋给elementData数组。

![70 3][]

这是ArrayList的有参构造方法，传入一个int类型的变量，相当于我们在使用arrayList的时候指定list的大小。

如果传入的参数大于0，则新建一个initialCapacity大小的数组。

![70 4][]

传入值等于0的话，将这个空数组给elementData。

下面我们来看add()方法的源码：

![70 5][]

使用到了一个size的参数，先看ensureCapacityInternal方法。

![70 6][]

size参数在前面进行了声明，作用是标识该数组的大小的。

![70 7][]

先执行了calculateCapacity方法，将数组和原先数组大小+1的数值传入。

![70 8][]

对数组进行判断，判断该数组是否为空，![70 9][]，这是一个空的数组，在前面声明过，如果现存的数组等于空的，我们就返回一个数值，![70 10][]，第一个变量是常量10，第二个是我们前面传入进来的，比较它俩的大小，返回大的数值。

如果不为空的话，我么直接返回前面方法传入的数值。进入ensureExplicitCapacity()方法。

![70 11][]

modCount是前面声明的变量，初始值为0。

![70 12][]

首先进行判断，如果新长度减去数组原先的长度大于0，我们则调用grow方法，并将新长度传入进去。

![70 13][]

这里就是ArrayList底层数组扩容的核心代码。

![70 14][]

新长度是旧长度加上旧长度的0.5，所以ArrayList底层数组每次扩容的大小都是1.5倍。

第一个if，如果新创建的长度小于传入的数组长度，那么就更新newCapacity的值为minCapacity。

第二个if，如果新数组长度减去最大的数组长度大于0的话，会进入hugeCapacity再次进行判断，返回Integer的最大长度，或者Integer的最大长度-8的长度。

![70 15][]之后完成数组复制，至此，ArrayList的底层扩容已经实现。

添加的方法说完了，下面我们来看看删除的方法。

![70 16][]

删除是每次进行数组复制，然后让旧的elementData置为null进行垃圾回收，代码很简单，一看就懂，但是我们可以从源码中去发现使用技巧。

查询的方法就更简单了，直接返回查询的对应数组中的值。

下面我们来自己写一个简易的ArrayListDemo。

/**
     * 作者：LKP
     * 时间：2018/7/13
     */
    public class ArrayListDemo {
        private Object[] arry;     //数组
    
        private int size = 0;      //下标
    
        public ArrayListDemo(){
            this.arry = new Object[10];
        }
    
        public ArrayListDemo(int size) throws Exception {
            if(size > 0)
                this.arry = new Object[size];
            else
                throw new Exception("长度不允许小于零！");
        }
    
        //新增
        public void add(Object number){
            if(size >= arry.length){
                int length = arry.length;
                Object[] newArry = new Object[length];
                for(int i=0; i<arry.length; i++){
                    newArry[i] = arry[i];
                }
                length = (length*3)/2+1;        //更新数组长度
                arry = new Object[length];      //对原有数组进行扩容
                for(int j=0; j<newArry.length; j++){
                    arry[j] = newArry[j];
                }
                newArry = null;     //释放该数组
            }
            arry[size] = number;
            size++;
        }
    
        //读取
        public Object get(int index) throws Exception {
            if(index >= 0)
                return arry[index];
            throw new Exception("下标不符合要求！");
        }
    
        //获得大小
        public int getSize(){
            int count = 0;
            for(int i=0; i<arry.length; i++){
                if(arry[i] != null){
                    count++;
                }
            }
            return count;
        }
    }

客户端代码：

/**
     * 作者：LKP
     * 时间：2018/7/13
     */
    public class demo {
        public static void main(String[] args){
            ArrayList ls = new ArrayList();
            ArrayListDemo list = new ArrayListDemo();
            list.add(1);
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            for(int i=0; i<list.getSize(); i++) {
                try {
                    System.out.println("List的值："+list.get(i));
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    }

运行结果：

![70 17][]

## 总结 ##

1.在声明时尽量指定长度。

2.ArrayList底层是数组，数组是适合查询的，因为数组每个元素的内存空间是固定的，每次查询时，只需要去查询对应位置的内存空间，就可以很快找到相应的值。而数组不擅长的是添加和删除。试想，集合长度是100000，而我们在第2个位置添加了一个元素，导致的结果是从第3个开始后面每一个元素都要往后串一个元素内存空间那么大的位置。删除刚好相反，是向前串一个位置，这样的效率是很低的，元素越多，效率越低。而频繁的添加和删除，适用链表——LinkedList。

[70]: /images/20220518/f75e89c054ff4497b0f0190406aa3313.png
[70 1]: /images/20220518/741083d87b194e5d8ffe642add239805.png
[70 2]: /images/20220518/52f656f24d7f483c91f6b7b785767a2d.png
[70 3]: /images/20220518/6fe9203f046b468aa59a80454a4cfdae.png
[70 4]: /images/20220518/8a1e6efb7e054461aae43af11dcc4ffa.png
[70 5]: /images/20220518/cb10d5bb53e546c7bd142612cafd8cb5.png
[70 6]: /images/20220518/39960a6180a14497a45a126e1bef31d4.png
[70 7]: /images/20220518/a360952c986649418bba389ba8ba0863.png
[70 8]: /images/20220518/6cd986d56ac5458abdf9e84dd6819f10.png
[70 9]: https://img-blog.csdn.net/20180728193409234?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrcDE2MDM2NDU3NTY=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 10]: /images/20220518/cbe341a024e847efae8d25cddddeb276.png
[70 11]: /images/20220518/53db4e740d6a446097a3ed34fcf16542.png
[70 12]: /images/20220518/6b08b405fd9d4c119d49ecc1a7db9441.png
[70 13]: /images/20220518/8f84e0d9cf6a475abc70d9a5265bd99e.png
[70 14]: /images/20220518/1578ddab56d141ae8f4807334c9c0d03.png
[70 15]: /images/20220518/127d5a21eb574425808ba6f5b79b1a6a.png
[70 16]: /images/20220518/5b7e7d83ef6c4557b4652402b48b2842.png
[70 17]: /images/20220518/d67c664ac3324dbd8edc701300cb46de.png