动态数组底层是如何实现的 java后端数据结构算法

动态数组底层是如何实现的

引言：提到数组，大部分脑海里一下子想到了一堆东西 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 {public static void main(String[] args) { int[] i = new int[8]; ArrayList list = new ArrayList(8); //将8个int类型依次放入数组和arrayList，注意，一个int占4个字节 for (int j = 0; j < 8; 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 arrayList = new ArrayList(2); //断点跟踪add arrayList.add("100"); arrayList.add("200"); arrayList.add("300"); arrayList.add("400"); //断点跟踪get //for (int i = 0; i



 
 2.3.1 源码分析之全局变量 
 目标：

 
 先认识下类变量和成员变量，方便讲解源码的时候能快速理解

 
  private static final int DEFAULT_CAPACITY = 10;
//默认的初始化容量
 private static final Object[] EMPTY_ELEMENTDATA = https://www.it610.com/article/{};
//空，对象数组，注意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 = https://www.it610.com/article/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}


 
 2）带int类型的构造函数

 
 如果传入参数，则代表指定ArrayList的初始数组长度，传入参数如果是大于等于0，则使用用户的参数初始化，如果用户传入的参数小于0，则抛出异常，构造方法如下：

 
 public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//以指定容量初始化Object数组
this.elementData = https://www.it610.com/article/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 c) {
//集合转换成数组
elementData = https://www.it610.com/article/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 =https://www.it610.com/article/= 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 = https://www.it610.com/article/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;

}//这是为什么呢？我们一开始integer-8还有啥意义？
//让我们返回去，看这个变量的注释：
//翻译：有些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 = https://www.it610.com/article/elementData(index);
//将要移除的元素int numMoved = size - index - 1;
//删除指定元素后，需要左移的元素个数(graph)
if (numMoved> 0)//如果有需要左移的元素，就移动（移动后，要删除的元素就已经被覆盖了）
//参数：src、srcdest、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、srcdest、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 = https://www.it610.com/article/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 = https://www.it610.com/article/null;

 Iterator iter = list.iterator();

 while (iter.hasNext()) {
value = (Integer)iter.next();

}


 
  
随机访问 通过索引值遍历 
  
  Integer value = https://www.it610.com/article/null;

 for (int i=0;
 i


 
  
for-each循环遍历 
  
 publicvoid show(List