欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

ArrayList（jdk1.8）

程序员文章站 2022-06-04 19:30:42
...

java.lang.Object 
  –java.util.AbstractCollection =>Collection 
    –java.util.AbstractList =>List 
      –java.util.ArrayList =>List,Serializable(), Cloneable, RandomAccess 

什么是ArrayList

       ArrayList既然类名中包含array，那必然跟数组有关，ArrayList其底层是通过数组实现的，但是与数组不同的是，定义一个数组时必须要定义其长度，与定义好其容量就不会改变的数组相比，ArrayList是根据不断添加的元素，而自动扩容的动态数组（下面将详细介绍）。

源码分析：

1.类继承实现

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable,Serializable
{
    //方法....
}
  • 1
  • 2
  • 3
  • 4
  • 5

在这里扩展了AbstractList类，实现了List接口，但是查看RandomAccess，Cloneable，Serializable这三个接口时，发现是空接口…….. 
其实这里的这三个接口只是起到标记作用，是接口的一种非典型用法的标记接口。 
例如Collections.shuffle()就是通过instanceof 判断该集合是否实现了RandomAccess接口来执行不同的随机排序算法。

RandomAccess：这个接口用于表示集合是否支持快速访问，ArrayList是基于数组实现的，支持快速随机访问。而LinkedList中则没有实现这个接口，因为LinkedList是双向链表，虽然支持通过下标进行访问，但是代价却很大。

Cloneable：可以克隆。ArrayList中也重写了clone方法（浅克隆）

Serializable：可以序列化，这个用的比较多就不说了。

我个人不太理解的是为什么不使用Annotation，而去采用这种标记接口的方式，或许是这种设计方式比较早，还没有Annotation，现在难以修改，不知道理解的对不对，如果有了解的大神，还请留言指点一下，谢谢。

2.成员变量

/**
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 用于空实例的共享空数组实例。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 用于默认大小的空实例的共享空数组实例
 * 我们根据第一个元素被添加时知道多少个元素去填充把它与EMPTY_ELEMENTDATA
 * 区分开来.
 * （这个变量是jdk1.8新加的）
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 保存了添加到ArrayList中的元素的数组
 * transient修饰不会被序列化
 */
transient Object[] elementData; 

/**
 * 数组当前长度
 * 其实就是这个ArrayList的长度 ，调用size()方法的返回值
 */
private int size;

/**
 * 数组最大容量
 */
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

需要注意的变量：

elementData这个数组其实就是用来存储向ArrayList添加的元素的，在第一次初始化的时候给这个数组初始化长度为DEFAULT_CAPACITY（10），可以添加null值，当数组长度不足时会进行扩容为1.5倍，下面会详细介绍。

3.主要方法

构造方法

ArrayList一共提供了3种构造方法

1.

/**
 * 这一种是我们最常用的构造方法
 * 直接创建一个空数组
 */
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

2.

/**
 * 根据指定容量创建
 */
public ArrayList(int initialCapacity) {
        //指定容量>0时，根据指定容量创建数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        //当指定容量为0时，直接创建空数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        //其他情况 非法参数异常 带回参数
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

3.

/**
 * 创建一个和传入集合一样的ArrayList
 */
public ArrayList(Collection<? extends E> c) {
    //将传入集合转换为数组，赋给elementData（ArrayList中存储元素的数组）
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toarray可能（错误地）不返回对象[ ]
        if (elementData.getClass() != Object[].class)
            //copy数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 用空数组替换。
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

获取元素

/**
 *
 */
public E get(int index) {
    //检查参数是否正确
    rangeCheck(index);
    //因为ArrayList是通过elementData这个数组存储元素
    //所以直接根据下标获取该数组的元素即可
    return elementData(index);
}

/**
 * 检查是否越界
 */
private void rangeCheck(int index) {
    if (index >= size)//如果index大于当前长度 异常索引越界
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

添加元素

/**
 * 添加元素
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1); //扩容方法  size+1为最小容量（添加一个元素 所以为1）
    elementData[size++] = e;
    return true;
}

/**
 * 获取所需最小容量
 */
private void ensureCapacityInternal(int minCapacity) {
    //如果elementData为空数组时
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //DEFAULT_CAPACITY（默认容量10）和最小容量中取最大的为最小容量
        minCapacity = Math.max(DEFAULT_CAPACITY,minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

/**
 * 是否扩容判断
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//修改次数++
    //需要的最小容量比elementData长度大时，容量不足，则需要进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 扩容
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //新的容量为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果超过最大长度 则设置为最大长度  不管了
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //对数组进行复制
    elementData = Arrays.copyOf(elementData, newCapacity);
}
  • 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
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

当我们使用ArrayList时，如果需要加入大量的元素时，将不断会进行扩容，进行数组copy，这样的效率很低，在jdk1.8中提供了ensureCapacity()方法，我们可以预先设置容量，来提高初始化效率。

public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0: DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

移除元素

/**
 * 根据下标移除
 */
public E remove(int index) {
    //检查是否越界
    rangeCheck(index);
    //修改次数+1
    modCount++;
    //获取要移除的元素
    E oldValue = elementData(index);

    //数组elementData中index位置之后的所有元素向前移一位
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //复制数组 
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
    return oldValue;//返回删除的元素
}

/**
 * 删除某个元素
 */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);//快速移除不需要下标校验，无返回值
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);//快速移除不需要下标校验，无返
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; 
}
  • 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
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

4.Fail-Fast 机制

为什么要记录修改操作次数？

关于modcount是从AbstractList中继承来的，用来检查列表中的元素是否发生结构性变化，当一个线程正在迭代遍历，另一个线程修改了这个列表的结构。就会出现ConcurrentModificationException异常。这种情况下我们就需要Collections.synchronizedList加上线程锁控制，或者使用Concurrent并发包下的CopyOnWriteArrayList。 
同理我们也不能在迭代过程中用集合方法去操作集合，如果需要进行操作，则需要使用迭代器中提供的方法进行修改。

相关标签： ArrayList

上一篇： JavaSE面试题——基于JDK1.8中Vector的实现原理（源码剖析）

下一篇： Java初始化HashMap

推荐阅读