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

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

1. 引言：
2. 提到数组，大部分脑海里一下子想到了一堆东西
3. int long short byte float double　boolean　char String
4. 没错，他们也可以定义成数组
5. 但是，上面都是静态的
6. 不过，咱们今天学习的可是动态的（ArrayList 数组）
7. 好接下来，我们一起来下面的内容

复制代码

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）

1. package com.alist;
3. import org.openjdk.jol.info.ClassLayout;
5. import java.util.ArrayList;
7. public class ArrayListHeader {
10.     public static void main(String[] args) {
11.         int[] i = new int[8];
12.         ArrayList<Integer> list = new ArrayList(8);
13.         //将8个int类型依次放入数组和arrayList，注意，一个int占4个字节
14.         for (int j = 0; j < 8; j++) {
15.             i[j] = j;
16.             list.add(j);
17.         }
19.         System.out.println(ClassLayout.parseInstance(i).toPrintable());
20.         System.out.println("=============");
21.         System.out.println(ClassLayout.parseInstance(list).toPrintable());
22. //        System.out.println(ClassLayout.parseClass(ArrayList.class));
23.     }
24. }

复制代码

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）

1. public class AList {
3.     public static void main(String[] args) {
4.         ArrayList<String> arrayList = new ArrayList<String>(2);
5.         //断点跟踪add
6.         arrayList.add("100");
7.         arrayList.add("200");
8.         arrayList.add("300");
9.         arrayList.add("400");
12.         //断点跟踪get
13. //        for (int i = 0; i <arrayList.size() ; i++) {
14. //            arrayList.get(i);//Random
15. //
16. //        }
19. //        //断点跟踪remove
20. //        arrayList.remove(1);
21. //        //arrayList.remove("100");//和上面逻辑一样remove
22. //        System.out.println(arrayList);
25. //         //断点跟踪set
26. //        arrayList.set(1,"2000000");
27. //        System.out.println(arrayList);
30. //        //断点跟踪clear
31. //        arrayList.clear();
32. //        System.out.println(arrayList);
34.     }

复制代码

3）带Collection对象的构造函数
[code]    public ArrayList(Collection