ArrayList底层实现原理「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

源码分析

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

声明了一个数组。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

删除是每次进行数组复制，然后让旧的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();
}
}
}
}

运行结果：

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

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