关于java:ArrayList源码解析

2次阅读

共计 5138 个字符，预计需要花费 13 分钟才能阅读完成。

在平时 Java, 存储数据须要用到列表，而大多时候都能用到ArrayList，比方Mybatis 查问数据列表，返回列表都是ArrayList，很多数据的寄存也用到了ArrayList。

jdk 版本：1.8

ArrayList 是基于 大小可变的数组 实现，并容许增加 null 值, 依据下标就能数据查问快。数组一旦初始化就确定好了大小，如果须要增加数据，就须要做数据的复制，这些操作比拟耗时。

ArrayList数组的扩容、增加和删除须要用到数组的拷贝，次要用到了以下两个办法：

System.arraycopy
Arrays.copyOf

System.arraycopy() 是 Java 的原生的静态方法，该办法将源数组元素拷贝到指标数组中去。

参数详解：

src 源数组
srcPos 源数组拷贝的起始索引
dest 指标数组
destPos 拷贝到指标数组的起始索引
length 拷贝元素的个数
将src源数组，起始索引为 srcPos, 个数为length, 复制到起始索引为destPos 的dest指标数组。

比方：

int[] srcArray = new int[]{1,2,3,4,5,6};
int[] desArray = new int[5];
System.arraycopy(srcArray,1,desArray,2,3);
System.out.println("desArray:" + Arrays.toString(desArray));

输入：

[0, 0, 2, 3, 4]

Arrays.copyOf实质也是调用 System.arraycopy 办法：

 public static int[] copyOf(int[] original, int newLength) {int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

首先创立一个新的数组 copy，将original 数组全副复制给 copy 数组。

// 底层数组
transient Object[] elementData;
// 数组个数大小
private int size;
// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList是基于数组的一个实现，elementData就是底层的数组。
size 是记录数组的个数。

public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

无参构造方法，创立数据间接赋值一个 空数组。

赋一个初始化容量initialCapacity:

public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {
        throw new IllegalArgumentException("Illegal Capacity:"+
                                           initialCapacity);
    }
}

初始化容量 initialCapacity 大于零，新建长度 initialCapacity 的数组。
初始化容量 initialCapacity 等于零，新建一个空数组。

增加数据有两个办法：

add(E e) 间接增加在数组尾部。
add(int index, E element) 依据下标增加数据。

在列表尾部增加数据：

/**
 * Appends the specified element to the end of this list.
 */
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal 判断增加数据后的容量是否足够，如果不够，做扩容操作。

private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

ensureCapacityInternal 作用是判断容量以后容量是否足够寄存新的数据，如果不够就做扩容操作。

calculateCapacity计算容量，如果数组为 null，返回minCapacity 和10的最大值，否则返回minCapacity。这个办法就是返回数组的大小。

调用无参构造方法 ArrayList(), 再调用add() 办法，首先数组容量会变成 10。这也是为什么无参构造方法ArrayList() 下面有会有注解Constructs an empty list with an initial capacity of ten.

ensureExplicitCapacity 判断须要的容量 minCapacity 大于以后数组的长度 elementData.length，将会做扩容解决，也是调用grow 办法：

private void grow(int minCapacity) {
    // overflow-conscious code
    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);
}

group 次要做了两件事：

长度扩充到原来的 1.5 倍
拷贝数组到新长度的数组

做完判断是否要做扩容之后，间接在 size 地位上赋值要增加的元素，而后 size 再自增。

elementData[size++] = e;

判断数据容量是否足够，如果是空数组，返回10, 其余容量返回以后数组size + 1。
返回容量和以后数组长度比照，小于做扩容解决。
扩容长度为原来长度的 1.5 倍，将数组赋值给长度为原来数组1.5 倍的新数组。
在数组的最开端 size 赋值。

此增加数据是在指定的下标增加数据。

public void add(int index, E element) {
    // 下标是否越界
    rangeCheckForAdd(index);
    // 判断是否要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 复制 i 到 size 的数据到 i +1 到 size +1
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

add(int index, E element) 在 index 下标增加数据，

首先判断 index 是否在0 ~size 之间。
判断是否要扩容，须要扩容，进行 1.5 倍扩容。
数据迁徙, 把 index 当前的数据全副往后挪动一位。
赋值index 下标数据。

获取数据只有通过数组下标获取数据 get(int index)：

public E get(int index) {
  // 查看是否超过数组范畴 
  rangeCheck(index);
  
  return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    // 通过下标获取数据 
    return (E) elementData[index];
}

这里获取数据就比较简单：

查看下标是否超过数组范畴。
通过下标拜访数据。

删除列表中第一个匹配的元素：

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

判断要删除数据是否为null:

为空，判断 elementData[index] 是否为空。
不为空，判断元素 equals 是否匹配elementData[index]。

下面判断都为 true 时，调用 fastRemove 办法：

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; // clear to let GC do its work
}

挪动数组数据，index+1 以及之后的数据往前挪动一位，最初一位 size-1 赋值为null。

依据 index 下标删除数据。

public E remove(int index) {
    // 是否越界 
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

数组的扩容、增加和删除都须要用到 System.arraycopy 办法，System.arraycopy是将 src 源数组，起始索引为 srcPos, 个数为length, 复制到起始索引为destPos 的dest指标数组。
ArrayList次要是基于 Object[] elementData 动静数组实现。
调用构造方法，无参的就赋值一个空数组，有初始容量的就赋值一个初始容量。
add 增加数组首先判断是否须要扩容，须要扩容，长度扩充成原来的 1.5 倍。
- add(E e) 在 size 赋值增加数据
- add(int index, E element) 将数组从 index 往后挪动一位，新数据增加到 index 上。
获取数据 get(int index) 利用数组的特定，依据下标获取数据。
remove(int index) 将 index 之后的数据全副往前挪动一位，size - 1赋为null。

正文完

java

发表至： java

2022-06-28

0

关于java:JVM内存模型

关于java:微服务必须具备的-3-个基本功能

关于java:Spring-Cloud-最新版发布干掉-JSch支持-Mina这次真的追不动了

关于java:面试官Java深拷贝和浅拷贝区别

关于java:新手计算机学习路线

关于java:ArrayList源码解析

数组拷贝

System.arraycopy

Arrays.copyOf

次要字段：

构造方法

ArrayList()

ArrayList(int initialCapacity)

增加数据

add(E e)

add(E e)流程总结

add(int index, E element)

获取数据

删除数据

remove(Object o)

remove(int index)

总结

站内搜索