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

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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33

2.3.1 源码分析之全局变量

目标：

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

 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;//数组最大长度？（扩容部分有彩蛋）
1
2
3
4
5

小问题：

• 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;
    }
1
2
3
4
5
6

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);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

3）带Collection对象的构造函数

    public ArrayList(Collection 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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Collection构造器意味着，你可以使用以下一揽子集合对象：

总结：

1、构造器一 啥也没干，只是声明了一个空数组

2、构造器二 通过自定义的初始化容量创建数组

3、*构造器三 *接受Collection的参数，如果有数据，就转换成一个新的elementData，否则还是一个空数组

事情有这么简单吗？？？接着往下看！

问题来了：无参构造和0长度构造有什么区别？

用代码说话，我们把对象结构给他打出来：

PHP7数组的底层实现示例

pdf 0星 超过10%的资源 81KB

下载

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());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

结果分析：

原理：

        //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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

结论：

• 刚构造时，都是空的！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;
}
1
2
3
4
5
6

扩容源码（重点）

    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;
    }



    //这是为什么呢？我们一开始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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

扩容总结：

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中指定位置的元素，数组访问，贼快~
}
1
2
3
4

总结：

和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;//返回刚才要删除的值
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

不好理解的地方

数组变化过程（左移个数，数组合并）

   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
3
4

js实现动态层,鼠标点击该层时，弹出该层隐藏内容。如163的新闻栏一样

application/x-rar 3星 超过45%的资源 6KB

下载

总结：

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;//返回旧的元素
    }
1
2
3
4
5

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
}
1
2
3
4
5
6

总结：

清除就是设置为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();
     }
1
2
3
4

• 随机访问 通过索引值遍历

 Integer value = null;
 for (int i=0; i