一、简介ArrayList是 Java 中一个重要的数据结构它基于数组实现可以动态扩展。在 JDK8 中ArrayList 继承自AbstractList并实现了List、RandomAccess、Cloneable和java.io.Serializable接口。这些接口分别提供了列表操作、随机访问、克隆和序列化的能力。public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.SerializableListE定义了一系列列表操作的通用方法包括增删改查遍历转换等。RandomAccess这是一个标记接口(空接口)本身没有任何方法作用是告诉java这个集合支持快速随机访问使用工具类遍历时可以选择最优的算法当你使用Collections的binarySearch或sort方法的时候内部就会判断它有没有实现RandomAccess接口如果实现了就用for循环没实现就用迭代器。public interface RandomAccess { }Cloneable这也是个标记接口(空接口)作用是告诉jvm这个类允许被克隆(调用clone()方法)。我们知道java的所用类都继承了Object。Object类中有个clone()方法但是这个clone()方法默认是不能直接使用的它需要你实现Cloneable接口才能使用否则就会直接抛出异常。Serializable同样是个标记接口(空接口)这个接口的作用是告诉jvm这个类的对象允许被序列化(存文件/发网络)如果没有实现这个接口去写文件的时候就会直接报错。二、6个核心成员//序列化版本号反序列化时jvm会用它判断序列化的对象与当前类是否兼容 private static final long serialVersionUID 8683452581122892189L; //默认容量如果是空参(未指定列表大小)创建列表第一次向其中添加元素时自动扩容的大小 private static final int DEFAULT_CAPACITY 10; //空数组有参构造传入参数为0时使用 private static final Object[] EMPTY_ELEMENTDATA {}; //空数组无参构造时使用默认创建个空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; //真正存放数据的数组 transient Object[] elementData; //实际存放元素的个数 private int size;这里需要注意一下transient Object[] elementData;它被transient关键字修饰这个关键字的作用是被它修饰的变量在对象序列化时不会被写入到流中反序列化回来会变成默认值。elementData用transient修饰是为了不序列化数组里那些没被使用到的null空位节省资源因为ArrayList是动态扩容的有可能列表中只有三个元素但是这个列表已经扩容到10如果不加transient那么序列化的时候就会把整个列表全部写进去(包括3个元素和7个无用null)会浪费大量资源。添加了transient就相当于给这个数组添加了一个默认不序列化的标识。那这样的话整个数组都不会序列化包括我们有用的元素也没有被保存这个显然是不对的;这个是通过重写writeObject /readObject来完成数组的序列化和反序列化。一句话总结就是不是不序列化元素而是不序列化整个数组。(transient只能修饰成员变量不能修饰方法或局部变量)private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ //记录当前修改次数 int expectedModCount modCount; //执行默认序列化将非transient、非static的普通字段写入流中完成默认序列化 s.defaultWriteObject(); //写入元素个数(兼容旧版本) s.writeInt(size); //写入具体元素 for (int i0; isize; i) { s.writeObject(elementData[i]); } //如果expectedModCount与modCount不一致那么说明在序列化过程中有其他线程对该对象进行了操作直接抛出异常 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } }private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { //将底层数组设置为空数组 elementData EMPTY_ELEMENTDATA; //反序列化将所有非transient、非static字段反序列化给当前对象 s.defaultReadObject(); //读取writeObject写的size-只是读出来根本不去使用。只是为了旧版本与clone行为兼容 s.readInt(); //判断数组中是否有元素 if (size 0) { //计算需要的具体容量 int capacity calculateCapacity(elementData, size); //反序列化前的安全校验-防止恶意构造超大数字导致OOM或攻击 SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); //设置底层数组elementData的大小 ensureCapacityInternal(size); Object[] a elementData; //向数组中添加元素 for (int i0; isize; i) { a[i] s.readObject(); } } }三、构造方法ArrayList共提供了三种构造方法分别是无参构造方法带初始容量参数的构造方法和带Collection参数的构造方法1、无参构造方法初始化一个为空的ArrayList当首次添加元素时数组会扩容为默认大小(10)public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }2、带初始容量参数的构造方法按用户传入的大小创建ArrayList需要注意的是允许用户传入0的数如果传入0的数的话会直接抛出异常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); } }3、带Collection参数的构造方法创建一个包含指定集合元素的ArrayList。public ArrayList(Collection? extends E c) { //将传入的集合转为数组 elementData c.toArray(); //将数组长度赋值给size并判断是否为0 if ((size elementData.length) ! 0) { //传入的集合不为空判断elementData是否为Object数组 if (elementData.getClass() ! Object[].class) //elementData不是Object数组将elementData转为Object数组 elementData Arrays.copyOf(elementData, size, Object[].class); } else { //传入的集合为空直接创建一个空集合 this.elementData EMPTY_ELEMENTDATA; } }这里有个疑问。elementData本来就是一个Object数组为啥还要去判断一下是否为Object[].class呢。这其实是jdk的一个bug导致c.toArray()返回的可能不是Object数组。例原ArrayListE c存的是String.这时c.toArray()返回的运行时类型为String[],并不是Object[]执行这行代码后赋值给Object[] elementData在编译上是没问题的但运行时其实还是String[];如果不进行判断这时向集合中添加一个Integer类型的数据就会报错。四、常用方法1、扩容(1)、ensureCapacityInternal(int minCapacity)检查是否需要扩容如果需要就完成扩容操作private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }(2)、calculateCapacity(elementData, minCapacity)判断是否为无参构造的空数组如果是那么第一次扩容给默认大小(10)否则返回实际大小private static int calculateCapacity(Object[] elementData, int minCapacity) { //判断elementData是否为空数组 if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果为空数组返回默认大小和实际大小中最大的值 return Math.max(DEFAULT_CAPACITY, minCapacity); } //不为空数组直接返回实际大小 return minCapacity; }(3)、ensureExplicitCapacity(int minCapacity)判断是否需要扩容如果需要扩容则去调用真正的扩容方法去完成扩容操作private void ensureExplicitCapacity(int minCapacity) { //修改次数1add和remove方法都会触发用于迭代器的快速失败 modCount; //所需容量是否大于当前容量 if (minCapacity - elementData.length 0) //需要扩容(真正的扩容方法) grow(minCapacity); }(4)、grow(int minCapacity)执行扩容操作每次扩容为原容量的1.5倍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); }(5)、hugeCapacity(int minCapacity)判断扩容到超大容量时是否可以继续扩容private static int hugeCapacity(int minCapacity) { //容量小于0代表int溢出(过大了) if (minCapacity 0) throw new OutOfMemoryError(); //判断容量是否超过安全上限如果超过给int最大值如果没有则设为安全上限 return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }2、新增-addArrayList提供了四种新增方法分别是添加到数组末尾、添加到指定下标的方法、追加另一个集合的所有元素到列表尾部、在指定下标添加另一个集合的全部元素四种方法(1)、add(E e)将指定的元素添加到数组末尾public boolean add(E e) { //检查数组是否需要扩容并完成扩容操作 ensureCapacityInternal(size 1); //将数据添加到数组中并且size1 elementData[size] e; return true; }(2)、add(int index, E element)将要添加的元素放到指定的位置public void add(int index, E element) { //下标合法性校验 rangeCheckForAdd(index); //确保底层数组容量足够(不够就进行扩容) ensureCapacityInternal(size 1); //元素后移1位空出要插入的位置 System.arraycopy(elementData, index, elementData, index 1, size - index); //将新元素插入指定位置 elementData[index] element; //更新有效元素个数 size; }(3)、addAll(Collection? extends E c)追加另一个集合的所有元素到列表尾部集合有变动返回true集合无变动返回falsepublic boolean addAll(Collection? extends E c) { //将目标集合转为数组 Object[] a c.toArray(); //得到有效元素的长度 int numNew a.length; //确保底层数组容量足够(不够就扩容) ensureCapacityInternal(size numNew); //在底层数组尾部插入数据 System.arraycopy(a, 0, elementData, size, numNew); //更新有效元素大小 size numNew; return numNew ! 0; }(4)、addAll(int index, Collection? extends E c)将集合c中的全部元素添加到目前集合中的指定位置集合有变动返回true集合无变动返回falsepublic boolean addAll(int index, Collection? extends E c) { //下标合法性校验 rangeCheckForAdd(index); //将目标集合转为数组 Object[] a c.toArray(); //获取目标集合中有效元素的个数 int numNew a.length; //确保底层数组容量足够(不够就扩容) ensureCapacityInternal(size numNew); //获取需要后移元素的个数 int numMoved size - index; //判断是否需要后移元素 if (numMoved 0) //需要后移后移元素 System.arraycopy(elementData, index, elementData, index numNew, numMoved); //将目标数组a中的元素插入底层数组中 System.arraycopy(a, 0, elementData, index, numNew); //更新有效元素大小 size numNew; return numNew ! 0; }3、删除-remove(1)、remove(int index)删除数组中对应下标的数据并将删除的数据返回回去public E remove(int index) { //校验下标合法性 rangeCheck(index); //修改次数1 modCount; //获取到要删除的元素 E oldValue elementData(index); //得到需要前移元素的个数 int numMoved size - index - 1; if (numMoved 0) //删除目标元素 System.arraycopy(elementData, index1, elementData, index, numMoved); //将原最后一个元素设为null elementData[--size] null; return oldValue; }(2)、remove(Object o)删除第一个匹配的元素未匹配到返回false匹配到删除后返回truepublic boolean remove(Object o) { if (o null) { //传入对象为null遍历找到第一个null元素 for (int index 0; index size; index) if (elementData[index] null) { //删除找到的元素 fastRemove(index); return true; } } else { //传入对象不为null遍历找到第一个匹配上的元素 for (int index 0; index size; index) if (o.equals(elementData[index])) { //删除找到的元素 fastRemove(index); return true; } } return false; }private void fastRemove(int index) { //修改次数1 modCount; //获取到需要前移元素的个数 int numMoved size - index - 1; //判断是否有元素需要前移(如果删除的是最后一个元素则不需要前移) if (numMoved 0) //前移元素 System.arraycopy(elementData, index1, elementData, index, numMoved); //有效元素个数-1并将原数组的最后一位元素设为null elementData[--size] null; }(3)、removeAll(Collection? c)删除当前集合中所有在入参集合中存在的元素集合被修改(删除掉元素)返回true集合未修改(未删除元素)返回falsepublic boolean removeAll(Collection? c) { //校验入参集合(不能为null) Objects.requireNonNull(c); //具体批量删除的方法 return batchRemove(c, false); }//c-参考集合complement-核心开关为true-元素不在c中就删除为false-元素在c中就删除 private boolean batchRemove(Collection? c, boolean complement) { final Object[] elementData this.elementData; //r-读指针w-写指针modified-标记集合是否发送删除操作 int r 0, w 0; boolean modified false; try { //遍历有效元素 for (; r size; r) //判断是否符合保留条件 if (c.contains(elementData[r]) complement) //不需要删除的元素 elementData[w] elementData[r]; } finally { if (r ! size) { //发生异常中断,将未遍历的数据直接添加到末尾确保数据没有丢失 System.arraycopy(elementData, r, elementData, w, size - r); //删除后剩余的元素个数 w size - r; } if (w ! size) { //有元素被删除,清理无效位置将无用引用置为null for (int i w; i size; i) elementData[i] null; //更新修改次数 modCount size - w; //更新有效元素个数 size w; //标记集合已被修改 modified true; } } return modified; }这个方法有个问题如果执行完elementData[w] elementData[r];这行代码发生了异常可能会导致数组中出现重复元素。例如有个数组为[A,B,C,D];在第一次遍历时r0,w0;执行完elementData[w] elementData[r];代码后w变为了1这时系统发生异常进入finally处理未遍历的数据时源数组起点r0目标数组起点w1拷贝长度size-r4;拷贝完成后数组变为[A,A,B,C,D];会导致出现重复数据如果正好达到了目标数组的最大值还会抛出ArrayIndexOutOfBoundsException异常。(4)、retainAll(Collection? c)只保留集合c中存在的元素其余元素全部删除。集合被修改(删除掉元素)返回true集合未修改(未删除元素)返回false。具体删除元素的流程与removeAll(Collection? c)方法相同只是核心开关传值不同public boolean retainAll(Collection? c) { Objects.requireNonNull(c); return batchRemove(c, true); }(5)、removeIf(Predicate? super E filter)根据条件批量删除元素(将满足filter条件的数据全部删掉)有元素被删除返回true否则返回false。public boolean removeIf(Predicate? super E filter) { //校验filter不能为null Objects.requireNonNull(filter); //需要删除元素的个数 int removeCount 0; //标记需要删除元素的下标(值为1对应的下标元素要删除默认值全部为0) final BitSet removeSet new BitSet(size); //记录初始修改次数 final int expectedModCount modCount; //底层集合中元素的个数 final int size this.size; //条件modCount!expectedModCount表示遍历中一旦发现外部修改集合立刻终止循环 //标记待删除元素的下标 for (int i0; modCount expectedModCount i size; i) { //抑制警告注解让编译器忽略代码中未经检查的类型转换(unchecked cast)产生的警告信息 SuppressWarnings(unchecked) final E element (E) elementData[i]; //校验该元素是否满足要删除的条件 if (filter.test(element)) { //满足条件 //将removeSet中下标为i的数据设置为1(代表该下标元素标记为待删除) removeSet.set(i); //累计待删除元素的数量 removeCount; } } //并发修改校验-判断期间是否有其他线程修改该列表 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //是否需要删除元素的标识 final boolean anyToRemove removeCount 0; if (anyToRemove) { //需要删除元素 //有效元素个数 final int newSize size - removeCount; //将不需要删除的元素移动到数组前面 for (int i0, j0; (i size) (j newSize); i, j) { //从i开始查找下一个值为0的数据并将下标赋值给i(找到下一个需要保留的元素) i removeSet.nextClearBit(i); //将元素拷贝到j位置 elementData[j] elementData[i]; } //尾部置空 for (int knewSize; k size; k) { //将数组后段无效位置置为null elementData[k] null; } //更新有效元素的个数 this.size newSize; //判断期间是否有其他线程操作该列表 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //修改次数1 modCount; } return anyToRemove; }这其中有一个BitSet类型它是java提供的一个工具类属于一个引用对象底层基于long[]长整型数组存储二进制位用每一个 bit0/1表示状态极致节省内存。(假如需要1000个布尔标记。使用boolean[],需要1000B但是使用BitSet的话只需要1000/6415.625也就是16个long16*8128B;内存相差很多)。(6)、removeRange(int fromIndex, int toIndex)删除集合中[fromIndex, toIndex)区间的元素(左闭右开);这是个protected级别的方法子类可重写但是外部不可直接调用protected void removeRange(int fromIndex, int toIndex) { //修改次数1 modCount; //需要前移的元素的个数 int numMoved size - toIndex; //元素整体前移 System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); //删除后有效元素的个数 int newSize size - (toIndex-fromIndex); //将数组尾部不再使用的位置置为null for (int i newSize; i size; i) { elementData[i] null; } //更新有效元素个数 size newSize; }(7)、clear()删除数组中全部的元素(无返回值)public void clear() { //修改次数1 modCount; //将全部元素都置为null for (int i 0; i size; i) elementData[i] null; //更新有效元素个数 size 0; }4、trimToSize()将ArrayList的底层数组容量收缩为当前实际元素个数。public void trimToSize() { //修改次数1 modCount; if (size elementData.length) { //实际元素个数小于数组容量 elementData (size 0) ? EMPTY_ELEMENTDATA //空数组 : Arrays.copyOf(elementData, size); } }5、转数组(1)、toArray()转为Object类型的数组返回转换后的数组public Object[] toArray() { return Arrays.copyOf(elementData, size); }(2)、toArray(T[] a)转为指定类型T的数组返回转换后的数组public T T[] toArray(T[] a) { if (a.length size) //传入数组a的容量小于实际元素个数 //新建数组返回 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //容量足够将有效元素拷贝到传入数组a中 System.arraycopy(elementData, 0, a, 0, size); if (a.length size) //传入数据大于实际元素个数 //标记有效元素截至位置 a[size] null; return a; }6、forEach(Consumer? super E action)遍历集合并执行自定义操作无返回值public void forEach(Consumer? super E action) { //校验action不为null Objects.requireNonNull(action); //得到修改次数 final int expectedModCount modCount; SuppressWarnings(unchecked) final E[] elementData (E[]) this.elementData; //得到有效元素个数 final int size this.size; //遍历数组并执行自定义操作 for (int i0; modCount expectedModCount i size; i) { action.accept(elementData[i]); } //判断期间是否有其他线程操作该集合 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } }7、replaceAll(UnaryOperatorE operator)遍历集合的所有元素用运算后的新值替换原有的元素;无返回值public void replaceAll(UnaryOperatorE operator) { //校验operator不为null Objects.requireNonNull(operator); //记录修改次数 final int expectedModCount modCount; //记录有效元素个数 final int size this.size; //遍历每个元素执行运算操作 for (int i0; modCount expectedModCount i size; i) { elementData[i] operator.apply((E) elementData[i]); } if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //修改次数1 modCount; }8、sort(Comparator? super E c)对集合中的全部元素按指定的比较规则排序无返回值public void sort(Comparator? super E c) { //记录修改次数 final int expectedModCount modCount; //在[0,size)范围内使用指定比较器c完成对elementData的自定义排序 Arrays.sort((E[]) elementData, 0, size, c); if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //修改次数1 modCount; }
ArrayList源码解析
一、简介ArrayList是 Java 中一个重要的数据结构它基于数组实现可以动态扩展。在 JDK8 中ArrayList 继承自AbstractList并实现了List、RandomAccess、Cloneable和java.io.Serializable接口。这些接口分别提供了列表操作、随机访问、克隆和序列化的能力。public class ArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, java.io.SerializableListE定义了一系列列表操作的通用方法包括增删改查遍历转换等。RandomAccess这是一个标记接口(空接口)本身没有任何方法作用是告诉java这个集合支持快速随机访问使用工具类遍历时可以选择最优的算法当你使用Collections的binarySearch或sort方法的时候内部就会判断它有没有实现RandomAccess接口如果实现了就用for循环没实现就用迭代器。public interface RandomAccess { }Cloneable这也是个标记接口(空接口)作用是告诉jvm这个类允许被克隆(调用clone()方法)。我们知道java的所用类都继承了Object。Object类中有个clone()方法但是这个clone()方法默认是不能直接使用的它需要你实现Cloneable接口才能使用否则就会直接抛出异常。Serializable同样是个标记接口(空接口)这个接口的作用是告诉jvm这个类的对象允许被序列化(存文件/发网络)如果没有实现这个接口去写文件的时候就会直接报错。二、6个核心成员//序列化版本号反序列化时jvm会用它判断序列化的对象与当前类是否兼容 private static final long serialVersionUID 8683452581122892189L; //默认容量如果是空参(未指定列表大小)创建列表第一次向其中添加元素时自动扩容的大小 private static final int DEFAULT_CAPACITY 10; //空数组有参构造传入参数为0时使用 private static final Object[] EMPTY_ELEMENTDATA {}; //空数组无参构造时使用默认创建个空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; //真正存放数据的数组 transient Object[] elementData; //实际存放元素的个数 private int size;这里需要注意一下transient Object[] elementData;它被transient关键字修饰这个关键字的作用是被它修饰的变量在对象序列化时不会被写入到流中反序列化回来会变成默认值。elementData用transient修饰是为了不序列化数组里那些没被使用到的null空位节省资源因为ArrayList是动态扩容的有可能列表中只有三个元素但是这个列表已经扩容到10如果不加transient那么序列化的时候就会把整个列表全部写进去(包括3个元素和7个无用null)会浪费大量资源。添加了transient就相当于给这个数组添加了一个默认不序列化的标识。那这样的话整个数组都不会序列化包括我们有用的元素也没有被保存这个显然是不对的;这个是通过重写writeObject /readObject来完成数组的序列化和反序列化。一句话总结就是不是不序列化元素而是不序列化整个数组。(transient只能修饰成员变量不能修饰方法或局部变量)private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ //记录当前修改次数 int expectedModCount modCount; //执行默认序列化将非transient、非static的普通字段写入流中完成默认序列化 s.defaultWriteObject(); //写入元素个数(兼容旧版本) s.writeInt(size); //写入具体元素 for (int i0; isize; i) { s.writeObject(elementData[i]); } //如果expectedModCount与modCount不一致那么说明在序列化过程中有其他线程对该对象进行了操作直接抛出异常 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } }private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { //将底层数组设置为空数组 elementData EMPTY_ELEMENTDATA; //反序列化将所有非transient、非static字段反序列化给当前对象 s.defaultReadObject(); //读取writeObject写的size-只是读出来根本不去使用。只是为了旧版本与clone行为兼容 s.readInt(); //判断数组中是否有元素 if (size 0) { //计算需要的具体容量 int capacity calculateCapacity(elementData, size); //反序列化前的安全校验-防止恶意构造超大数字导致OOM或攻击 SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); //设置底层数组elementData的大小 ensureCapacityInternal(size); Object[] a elementData; //向数组中添加元素 for (int i0; isize; i) { a[i] s.readObject(); } } }三、构造方法ArrayList共提供了三种构造方法分别是无参构造方法带初始容量参数的构造方法和带Collection参数的构造方法1、无参构造方法初始化一个为空的ArrayList当首次添加元素时数组会扩容为默认大小(10)public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }2、带初始容量参数的构造方法按用户传入的大小创建ArrayList需要注意的是允许用户传入0的数如果传入0的数的话会直接抛出异常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); } }3、带Collection参数的构造方法创建一个包含指定集合元素的ArrayList。public ArrayList(Collection? extends E c) { //将传入的集合转为数组 elementData c.toArray(); //将数组长度赋值给size并判断是否为0 if ((size elementData.length) ! 0) { //传入的集合不为空判断elementData是否为Object数组 if (elementData.getClass() ! Object[].class) //elementData不是Object数组将elementData转为Object数组 elementData Arrays.copyOf(elementData, size, Object[].class); } else { //传入的集合为空直接创建一个空集合 this.elementData EMPTY_ELEMENTDATA; } }这里有个疑问。elementData本来就是一个Object数组为啥还要去判断一下是否为Object[].class呢。这其实是jdk的一个bug导致c.toArray()返回的可能不是Object数组。例原ArrayListE c存的是String.这时c.toArray()返回的运行时类型为String[],并不是Object[]执行这行代码后赋值给Object[] elementData在编译上是没问题的但运行时其实还是String[];如果不进行判断这时向集合中添加一个Integer类型的数据就会报错。四、常用方法1、扩容(1)、ensureCapacityInternal(int minCapacity)检查是否需要扩容如果需要就完成扩容操作private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }(2)、calculateCapacity(elementData, minCapacity)判断是否为无参构造的空数组如果是那么第一次扩容给默认大小(10)否则返回实际大小private static int calculateCapacity(Object[] elementData, int minCapacity) { //判断elementData是否为空数组 if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果为空数组返回默认大小和实际大小中最大的值 return Math.max(DEFAULT_CAPACITY, minCapacity); } //不为空数组直接返回实际大小 return minCapacity; }(3)、ensureExplicitCapacity(int minCapacity)判断是否需要扩容如果需要扩容则去调用真正的扩容方法去完成扩容操作private void ensureExplicitCapacity(int minCapacity) { //修改次数1add和remove方法都会触发用于迭代器的快速失败 modCount; //所需容量是否大于当前容量 if (minCapacity - elementData.length 0) //需要扩容(真正的扩容方法) grow(minCapacity); }(4)、grow(int minCapacity)执行扩容操作每次扩容为原容量的1.5倍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); }(5)、hugeCapacity(int minCapacity)判断扩容到超大容量时是否可以继续扩容private static int hugeCapacity(int minCapacity) { //容量小于0代表int溢出(过大了) if (minCapacity 0) throw new OutOfMemoryError(); //判断容量是否超过安全上限如果超过给int最大值如果没有则设为安全上限 return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }2、新增-addArrayList提供了四种新增方法分别是添加到数组末尾、添加到指定下标的方法、追加另一个集合的所有元素到列表尾部、在指定下标添加另一个集合的全部元素四种方法(1)、add(E e)将指定的元素添加到数组末尾public boolean add(E e) { //检查数组是否需要扩容并完成扩容操作 ensureCapacityInternal(size 1); //将数据添加到数组中并且size1 elementData[size] e; return true; }(2)、add(int index, E element)将要添加的元素放到指定的位置public void add(int index, E element) { //下标合法性校验 rangeCheckForAdd(index); //确保底层数组容量足够(不够就进行扩容) ensureCapacityInternal(size 1); //元素后移1位空出要插入的位置 System.arraycopy(elementData, index, elementData, index 1, size - index); //将新元素插入指定位置 elementData[index] element; //更新有效元素个数 size; }(3)、addAll(Collection? extends E c)追加另一个集合的所有元素到列表尾部集合有变动返回true集合无变动返回falsepublic boolean addAll(Collection? extends E c) { //将目标集合转为数组 Object[] a c.toArray(); //得到有效元素的长度 int numNew a.length; //确保底层数组容量足够(不够就扩容) ensureCapacityInternal(size numNew); //在底层数组尾部插入数据 System.arraycopy(a, 0, elementData, size, numNew); //更新有效元素大小 size numNew; return numNew ! 0; }(4)、addAll(int index, Collection? extends E c)将集合c中的全部元素添加到目前集合中的指定位置集合有变动返回true集合无变动返回falsepublic boolean addAll(int index, Collection? extends E c) { //下标合法性校验 rangeCheckForAdd(index); //将目标集合转为数组 Object[] a c.toArray(); //获取目标集合中有效元素的个数 int numNew a.length; //确保底层数组容量足够(不够就扩容) ensureCapacityInternal(size numNew); //获取需要后移元素的个数 int numMoved size - index; //判断是否需要后移元素 if (numMoved 0) //需要后移后移元素 System.arraycopy(elementData, index, elementData, index numNew, numMoved); //将目标数组a中的元素插入底层数组中 System.arraycopy(a, 0, elementData, index, numNew); //更新有效元素大小 size numNew; return numNew ! 0; }3、删除-remove(1)、remove(int index)删除数组中对应下标的数据并将删除的数据返回回去public E remove(int index) { //校验下标合法性 rangeCheck(index); //修改次数1 modCount; //获取到要删除的元素 E oldValue elementData(index); //得到需要前移元素的个数 int numMoved size - index - 1; if (numMoved 0) //删除目标元素 System.arraycopy(elementData, index1, elementData, index, numMoved); //将原最后一个元素设为null elementData[--size] null; return oldValue; }(2)、remove(Object o)删除第一个匹配的元素未匹配到返回false匹配到删除后返回truepublic boolean remove(Object o) { if (o null) { //传入对象为null遍历找到第一个null元素 for (int index 0; index size; index) if (elementData[index] null) { //删除找到的元素 fastRemove(index); return true; } } else { //传入对象不为null遍历找到第一个匹配上的元素 for (int index 0; index size; index) if (o.equals(elementData[index])) { //删除找到的元素 fastRemove(index); return true; } } return false; }private void fastRemove(int index) { //修改次数1 modCount; //获取到需要前移元素的个数 int numMoved size - index - 1; //判断是否有元素需要前移(如果删除的是最后一个元素则不需要前移) if (numMoved 0) //前移元素 System.arraycopy(elementData, index1, elementData, index, numMoved); //有效元素个数-1并将原数组的最后一位元素设为null elementData[--size] null; }(3)、removeAll(Collection? c)删除当前集合中所有在入参集合中存在的元素集合被修改(删除掉元素)返回true集合未修改(未删除元素)返回falsepublic boolean removeAll(Collection? c) { //校验入参集合(不能为null) Objects.requireNonNull(c); //具体批量删除的方法 return batchRemove(c, false); }//c-参考集合complement-核心开关为true-元素不在c中就删除为false-元素在c中就删除 private boolean batchRemove(Collection? c, boolean complement) { final Object[] elementData this.elementData; //r-读指针w-写指针modified-标记集合是否发送删除操作 int r 0, w 0; boolean modified false; try { //遍历有效元素 for (; r size; r) //判断是否符合保留条件 if (c.contains(elementData[r]) complement) //不需要删除的元素 elementData[w] elementData[r]; } finally { if (r ! size) { //发生异常中断,将未遍历的数据直接添加到末尾确保数据没有丢失 System.arraycopy(elementData, r, elementData, w, size - r); //删除后剩余的元素个数 w size - r; } if (w ! size) { //有元素被删除,清理无效位置将无用引用置为null for (int i w; i size; i) elementData[i] null; //更新修改次数 modCount size - w; //更新有效元素个数 size w; //标记集合已被修改 modified true; } } return modified; }这个方法有个问题如果执行完elementData[w] elementData[r];这行代码发生了异常可能会导致数组中出现重复元素。例如有个数组为[A,B,C,D];在第一次遍历时r0,w0;执行完elementData[w] elementData[r];代码后w变为了1这时系统发生异常进入finally处理未遍历的数据时源数组起点r0目标数组起点w1拷贝长度size-r4;拷贝完成后数组变为[A,A,B,C,D];会导致出现重复数据如果正好达到了目标数组的最大值还会抛出ArrayIndexOutOfBoundsException异常。(4)、retainAll(Collection? c)只保留集合c中存在的元素其余元素全部删除。集合被修改(删除掉元素)返回true集合未修改(未删除元素)返回false。具体删除元素的流程与removeAll(Collection? c)方法相同只是核心开关传值不同public boolean retainAll(Collection? c) { Objects.requireNonNull(c); return batchRemove(c, true); }(5)、removeIf(Predicate? super E filter)根据条件批量删除元素(将满足filter条件的数据全部删掉)有元素被删除返回true否则返回false。public boolean removeIf(Predicate? super E filter) { //校验filter不能为null Objects.requireNonNull(filter); //需要删除元素的个数 int removeCount 0; //标记需要删除元素的下标(值为1对应的下标元素要删除默认值全部为0) final BitSet removeSet new BitSet(size); //记录初始修改次数 final int expectedModCount modCount; //底层集合中元素的个数 final int size this.size; //条件modCount!expectedModCount表示遍历中一旦发现外部修改集合立刻终止循环 //标记待删除元素的下标 for (int i0; modCount expectedModCount i size; i) { //抑制警告注解让编译器忽略代码中未经检查的类型转换(unchecked cast)产生的警告信息 SuppressWarnings(unchecked) final E element (E) elementData[i]; //校验该元素是否满足要删除的条件 if (filter.test(element)) { //满足条件 //将removeSet中下标为i的数据设置为1(代表该下标元素标记为待删除) removeSet.set(i); //累计待删除元素的数量 removeCount; } } //并发修改校验-判断期间是否有其他线程修改该列表 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //是否需要删除元素的标识 final boolean anyToRemove removeCount 0; if (anyToRemove) { //需要删除元素 //有效元素个数 final int newSize size - removeCount; //将不需要删除的元素移动到数组前面 for (int i0, j0; (i size) (j newSize); i, j) { //从i开始查找下一个值为0的数据并将下标赋值给i(找到下一个需要保留的元素) i removeSet.nextClearBit(i); //将元素拷贝到j位置 elementData[j] elementData[i]; } //尾部置空 for (int knewSize; k size; k) { //将数组后段无效位置置为null elementData[k] null; } //更新有效元素的个数 this.size newSize; //判断期间是否有其他线程操作该列表 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //修改次数1 modCount; } return anyToRemove; }这其中有一个BitSet类型它是java提供的一个工具类属于一个引用对象底层基于long[]长整型数组存储二进制位用每一个 bit0/1表示状态极致节省内存。(假如需要1000个布尔标记。使用boolean[],需要1000B但是使用BitSet的话只需要1000/6415.625也就是16个long16*8128B;内存相差很多)。(6)、removeRange(int fromIndex, int toIndex)删除集合中[fromIndex, toIndex)区间的元素(左闭右开);这是个protected级别的方法子类可重写但是外部不可直接调用protected void removeRange(int fromIndex, int toIndex) { //修改次数1 modCount; //需要前移的元素的个数 int numMoved size - toIndex; //元素整体前移 System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); //删除后有效元素的个数 int newSize size - (toIndex-fromIndex); //将数组尾部不再使用的位置置为null for (int i newSize; i size; i) { elementData[i] null; } //更新有效元素个数 size newSize; }(7)、clear()删除数组中全部的元素(无返回值)public void clear() { //修改次数1 modCount; //将全部元素都置为null for (int i 0; i size; i) elementData[i] null; //更新有效元素个数 size 0; }4、trimToSize()将ArrayList的底层数组容量收缩为当前实际元素个数。public void trimToSize() { //修改次数1 modCount; if (size elementData.length) { //实际元素个数小于数组容量 elementData (size 0) ? EMPTY_ELEMENTDATA //空数组 : Arrays.copyOf(elementData, size); } }5、转数组(1)、toArray()转为Object类型的数组返回转换后的数组public Object[] toArray() { return Arrays.copyOf(elementData, size); }(2)、toArray(T[] a)转为指定类型T的数组返回转换后的数组public T T[] toArray(T[] a) { if (a.length size) //传入数组a的容量小于实际元素个数 //新建数组返回 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //容量足够将有效元素拷贝到传入数组a中 System.arraycopy(elementData, 0, a, 0, size); if (a.length size) //传入数据大于实际元素个数 //标记有效元素截至位置 a[size] null; return a; }6、forEach(Consumer? super E action)遍历集合并执行自定义操作无返回值public void forEach(Consumer? super E action) { //校验action不为null Objects.requireNonNull(action); //得到修改次数 final int expectedModCount modCount; SuppressWarnings(unchecked) final E[] elementData (E[]) this.elementData; //得到有效元素个数 final int size this.size; //遍历数组并执行自定义操作 for (int i0; modCount expectedModCount i size; i) { action.accept(elementData[i]); } //判断期间是否有其他线程操作该集合 if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } }7、replaceAll(UnaryOperatorE operator)遍历集合的所有元素用运算后的新值替换原有的元素;无返回值public void replaceAll(UnaryOperatorE operator) { //校验operator不为null Objects.requireNonNull(operator); //记录修改次数 final int expectedModCount modCount; //记录有效元素个数 final int size this.size; //遍历每个元素执行运算操作 for (int i0; modCount expectedModCount i size; i) { elementData[i] operator.apply((E) elementData[i]); } if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //修改次数1 modCount; }8、sort(Comparator? super E c)对集合中的全部元素按指定的比较规则排序无返回值public void sort(Comparator? super E c) { //记录修改次数 final int expectedModCount modCount; //在[0,size)范围内使用指定比较器c完成对elementData的自定义排序 Arrays.sort((E[]) elementData, 0, size, c); if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } //修改次数1 modCount; }
