本篇文章为你整理了动态数组底层是如何实现的（动态数组的优点体现在哪里）的详细内容，包含有动态数组有什么用 动态数组的优点体现在哪里 动态数组是如何建立和使用的 动态数组怎么定义 动态数组底层是如何实现的，希望能帮助你了解 动态数组底层是如何实现的。
提到数组，大部分脑海里一下子想到了一堆东西
int long short byte float double boolean char String
没错，他们也可以定义成数组
但是，上面都是静态的
不过，咱们今天学习的可是动态的（ArrayList 数组）
好接下来，我们一起来下面的内容
2.1 动态数组的位置
目标：
简单认识下继承关系
ArrayList继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口
从继承关系看功能
AbstractList类
AbstractList，实现了List。List接口我们都知道，提供了相关的添加、删除、修改、遍历等功能
RandmoAccess接口
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能； 即list.get(i)
Cloneable接口
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆
Serializable接口
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输
2.2.动态数组与数据结构
目标：
图解+面试题快速认识ArrayList
1) 概念介绍
ArrayList 是一个数组队列，相当于动态（扩容）数组。
我们直接来看对象头，对其有个简单认识和猜想：（com.alist.InitialList）
package com.alist;
import org.openjdk.jol.info.ClassLayout;
import java.util.ArrayList;
public class ArrayListHeader {
ArrayList Integer list = new ArrayList(8);
//将8个int类型依次放入数组和arrayList，注意，一个int占4个字节
for (int j = 0; j j++) {
i[j] = j;
list.add(j);
System.out.println(ClassLayout.parseInstance(i).toPrintable());
System.out.println("=============");
System.out.println(ClassLayout.parseInstance(list).toPrintable());
// System.out.println(ClassLayout.parseClass(ArrayList.class));
2) 执行结果分析：
从对象头，我们大致可以看出ArrayList的数据结构：
ArrayList底层用一个数组存储数据：elementData
额外附加了几组信息：modeCount（发生修改操作的次数）、size（当前数组的长度）
等会……
为什么长度不是数组里的32，而是4个字节？ArrayList的长度到底应该是多少？？？
这个数组后面多出来俩null又是怎么回事？？？
（下面构造函数部分会得到详细答案）
3) 结论 面试题
ArrayList外围暴露出来的只是一些操作的表象，底层数据的存储和操作都是基于数组的基础上
这就意味着，它的特性和数组一样：查询快！删除插入慢。
ArrayList访问为什么那么快？
1、ArrayList底层是数组实现的
2、数组是一块连续的内存空间
3、获取数据可以直接拿地址偏移量（get（i））
因此：查询（确切的说是访问，而不是查找）的时间复杂度是O(1)
为什么删除和增加那么慢？
增删会带来元素的移动，增加数据会向后移动，删除数据会向前移动，所以影响效率
因此：插入、删除的时间复杂度是O(N)
2.3 动态数组源码深入剖析
接下来，我们从底层源码层面看ArrayList的一系列操作
先准备测试代码，下面debug用（com.alist.AList）
public class AList {
public static void main(String[] args) {
ArrayList String arrayList = new ArrayList String
//断点跟踪add
arrayList.add("100");
arrayList.add("200");
arrayList.add("300");
arrayList.add("400");
先认识下类变量和成员变量，方便讲解源码的时候能快速理解
private static final int DEFAULT_CAPACITY = 10;//默认的初始化容量
private static final Object[] EMPTY_ELEMENTDATA = {};//空，对象数组，注意static，所有空arraylist共享，那不会出问题吗？？？（秘密在add数据时的扩容操作里……）
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空，无参构造使用（1.8才有）
transient Object[] elementData; // 当前数据对象存放的地方，注意是transient，虽然数组实现了serializable接口，但是它的数据不会被默认的ObjectOutputStream序列化，想做网络传输，自己改写writeObject和readObject方法！
private int size;//当前数据的个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//数组最大长度？（扩容部分有彩蛋）
小问题：
ArrayList可以无限大吗？到底最大是多少？
elementData好理解，放数据，又为啥定义两个空数组？啰嗦不？
上面的定义看似明明白白，其实背地里藏着很多不为人知的事，我们接着往下看……
2.3.2 源码分析之构造器
目标：
源码查看ArrayList的3个构造器
1）无参构造函数
如果不传入参数，则使用默认无参构建方法创建ArrayList对象，如下：
public ArrayList() {
//默认构造函数，很简单，就是把default empty数组赋给了data
//jdk8里才有DEFAULTCAPACITY_EMPTY_ELEMENTDATA这货，并且仅仅被用在了这个构造函数里
//官方的解释是，为了区分判断第一次add的时候，数组初始化的容量
//这个秘密藏在calculateCapacity里（下文会讲）
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
2）带int类型的构造函数
如果传入参数，则代表指定ArrayList的初始数组长度，传入参数如果是大于等于0，则使用用户的参数初始化，如果用户传入的参数小于0，则抛出异常，构造方法如下：
public ArrayList(int initialCapacity) {
if (initialCapacity 0) {
//以指定容量初始化Object数组
this.elementData = new Object[initialCapacity];//初始化容量
} else if (initialCapacity == 0) {
//如果指定0的话，用empty数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//否则，如果是负数的话，扔一个异常出来（哪有长度为负数的？？）
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
3）带Collection对象的构造函数
public ArrayList(Collection ? extends E c) {
//集合转换成数组
elementData = c.toArray();
//将data长度赋值给size属性
if ((size = elementData.length) != 0) {
// 官方注释：c.toArray might (incorrectly) not return Object[] (see 6260652)
// 翻译：toArray不一定会返回Object数组，参考jdk的bug号……汗！
// 如果不是Object数组，转成Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);//数组赋值，类型转换
} else {
// 如果数据为空，将empty赋给data
this.elementData = EMPTY_ELEMENTDATA;
Collection构造器意味着，你可以使用以下一揽子集合对象：
总结：
1、构造器一 啥也没干，只是声明了一个空数组
2、构造器二 通过自定义的初始化容量创建数组
3、**构造器三 **接受Collection的参数，如果有数据，就转换成一个新的elementData，否则还是一个空数组
事情有这么简单吗？？？接着往下看！
问题来了：无参构造和0长度构造有什么区别？
用代码说话，我们把对象结构给他打出来：
package com.alist;
import org.openjdk.jol.info.ClassLayout;
import java.util.ArrayList;
public class InitialList {
public static void main(String[] args) {
//两种方式构建list，有什么区别？
ArrayList list1 = new ArrayList();
ArrayList list2 = new ArrayList(0);
//打印对象头
System.out.println(ClassLayout.parseInstance(list1).toPrintable());
System.out.println(ClassLayout.parseInstance(list2).toPrintable());
System.out.println("========");
//add一个元素之后再来打印试试
list1.add(1);
list2.add(1);
System.out.println(ClassLayout.parseInstance(list1).toPrintable());
System.out.println(ClassLayout.parseInstance(list2).toPrintable());
结果分析：
原理：
//calculateCapacity
//每次元素变动，比如add，会调用该函数判断容量情况
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//定义default empty数组的意义就在这里！用于扩容时判断当初采用的是哪种构造函数
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//如果是无参的构造函数，用的就是该default empty
//那么第一次add时候，容量取default和min中较大者
return Math.max(DEFAULT_CAPACITY, minCapacity);
//如果是另外两个构造函数，比如指定容量为5，或者初始参数collection为5
//那就直接返回5，一定程度上，节约了内存空间
return minCapacity;
结论：
刚构造时，都是空的！add时才初始化（这里容易误解，以为默认构造器data初始化就是10）
虽然list可以自动扩容，但尽量初始就预估并定义list的容量，少用无参的构造器，尤其小于10的时候
default empty存在的意义：判断那种构造函数来的，初始阶段节约了扩容的空间占用
2.3.3 源码分析之增加与扩容
目标：
源码分析ArrayList的增加、扩容方法
add增加与扩容调用流程图
增加源码（简单）
public boolean add(E e) {
//确认容量，不够则扩容
ensureCapacityInternal(size + 1);
//将元素追加到数组的末尾去，同时计数增size++
elementData[size++] = e;
return true;
扩容源码（重点）
private void grow(int minCapacity) {
//minCapacity：我需要的最小长度，也就是上面的size+1
int oldCapacity = elementData.length;//先取出旧数组大小
int newCapacity = oldCapacity + (oldCapacity 1);//扩容为旧数组的1.5倍；右移一位（除以2）
if (newCapacity - minCapacity 0)//如果扩容1.5后还不够
newCapacity = minCapacity;//取需求量为新长度，数组的扩容还是比较保守和吝啬！
if (newCapacity - MAX_ARRAY_SIZE 0)//新长度大于数组最大长度，彩蛋来了！
newCapacity = hugeCapacity(minCapacity);//看下面的huge方法 ↓
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//返回一个新的数组对象
private static int hugeCapacity(int minCapacity) {
if (minCapacity 0) // 负数说明超出了Integer的范围，溢出了，抛异常
throw new OutOfMemoryError();
//否则：返回Integer的最大值，而不是最大值-8！惊不惊奇？意不意外？
return (minCapacity MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
//让我们返回去，看这个变量的注释：
//翻译：有些VM会在array头上预留信息，企图大于这个值也行，但是不保证安全性，可能会溢出报错！
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
扩容总结：
1、按1.5倍扩容，如果1.5还不够，取你想要的容量（总之保证够你用的）
2、数组最大容量是integer的max_value，但是达到这个值的时候，arraylist不保证稳定可靠！
2.3.4 源码分析之get方法、
目标：
源码分析ArrayList的get方法
get流程图解：
因为基于数组，所以极其简单
public E get(int index) { //返回list中指定位置的元素
rangeCheck(index);//越界检查
return elementData(index);//返回list中指定位置的元素，数组访问，贼快~
总结：
和java的数组用法相近
2.3.5 源码分析之remove方法
目标：
源码分析ArrayList的remove方法
数组拷贝是重点，可以借助单步调试debug查看过程
移除回顾
remove方法执行流程
remove源码解释（重点）
public E remove(int index) {
rangeCheck(index);//数组越界检查
modCount++;//结构性修改次数+1
E oldValue = elementData(index);//将要移除的元素
int numMoved = size - index - 1;//删除指定元素后，需要左移的元素个数(graph)
if (numMoved 0)//如果有需要左移的元素，就移动（移动后，要删除的元素就已经被覆盖了）
//参数：src、src dest、dest、移动的长度
//从data的index+1到data的index，也就是元素挨个前移一格，一共移动num个
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//左移后，最后一个位置还有值，给他搞成null，下一步gc会把对象收走，size计数减少
//（借助断点查看data数组的最后一个元素的值）
elementData[--size] = null;
return oldValue;//返回刚才要删除的值
不好理解的地方
数组变化过程（左移个数，数组合并）
int numMoved = size - index - 1;//删除指定元素后，需要左移的元素个数(graph)
if (numMoved 0)//如果有需要左移的元素，就移动（移动后，该删除的元素就已经被覆盖了）
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//参数：src、src dest、dest、移动的长度
elementData[--size] = null; //左移后，最后一个位置就为空了；size减一，为了让GC起作用，设置为null
总结：
1、移除后 ，后面的节点通过数组拷贝的方式需要左移
2、需要注意的是：如果末端太长，remove是非常耗费性能的
2.3.6 源码分析之set方法
public E set(int index, E element) {
rangeCheck(index);//越界检查
E oldValue = elementData(index);//修改前的原素质
elementData[index] = element;//新元素赋值
return oldValue;//返回旧的元素
2.3.7 源码分析之clear方法
目标：
源码分析ArrayList的clear方法
public void clear() { //从列表中删除所有元素。该调用返回后，数组将为空
modCount++;//修改测试自增
// clear to let GC do its work
for (int i = 0; i size; i++)
elementData[i] = null;//清除表元素
size = 0;//大小为0
总结：
清除就是设置为null、大小设置为0；设置null，方便gc
需要注意的是：
clear过后，size=0，但是table的大小并没有回缩！
2.4 动态数组常见面试题
1、哪些集合实现了List接口和Collection接口，各自的优缺点是什么
通过上面类图可用看出，List接口下有4个实现类，分别为：LinkedList、ArrayList、Vector和Stack。
List只是个接口，接口也就是定义了一组规范或者api
具体的实现甚至底层存储可以是完全不同的，比如数组，链表
2、ArrayList提供了几种查询方式、效率如何？
Iterator迭代器遍历方式
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
随机访问 通过索引值遍历
Integer value = null;
for (int i=0; i list.size(); i++) {
value = (Integer)list.get(i);
for-each循环遍历
public void show(List Object list){
list.forEach( s - System.out.println(s));
关于性能：
1、数据量不大的时候，以上三种方式差不多
2、数据量不断上升的情况下for each表现不错
3、ArrayList可以存放null吗？
可以。
4、ArrayList是如何扩容的？
在用无参构造来创建对象的时候其实就是创建了一个空数组，长度为0。add时先分配一个默认大小10，后续扩容，每次扩容都是原容量的1.5倍。
在有参构造中，传入的参数是正整数就按照传入的参数来确定创建数组的大小。再进行扩容，每次扩容都是原容量的1.5倍
5、ArrayList是线程安全的吗？
不是
6、ArrayList插入删除一定慢么？
取决于你删除的元素离数组末端有多远
本文由传智教育博学谷 - 狂野架构师教研团队发布
如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力
转载请注明出处！
以上就是动态数组底层是如何实现的（动态数组的优点体现在哪里）的详细内容，想要了解更多 动态数组底层是如何实现的的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。