说说ArrayList的理解？

### 一、ArrayList 介绍 ArrayList 是一种线性数据结构，底层由数组实现，相当于动态数组。与 Java 中的数组相比，ArrayList 的容量能够动态增长。ArrayList 保留了数组可以快速查找的优势，同时弥补了数组在创建后不能动态扩展的缺点。其实现的基本方法如下： 1. **快速查找**：在物理内存上采用顺序存储结构，因此可根据索引快速查找元素。 2. **容量动态增长**：当数组容量不够用时，创建一个比原数组容量大的新数组，将原数组中的元素“搬”到新数组，再将新的元素放入新数组，最后将新数组赋给原数组。 ### 二、ArrayList 继承关系 ArrayList 继承自 AbstractList，实现了 List、RandomAccess、Cloneable 和 java.io.Serializable 接口。它允许存储 null 值，除了没有进行同步，ArrayList 基本等同于 Vector。不同的是，Vector 几乎对所有的方法都进行了同步，而 ArrayList 仅对 writeObject 和 readObject 进行了同步。 ```java public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { // 省略类实现 } ``` ### 三、ArrayList 的实现 ArrayList 实现了 List 接口，底层使用数组保存所有元素。下面对 ArrayList 的具体实现进行介绍： #### 1. 私有属性 ```java // 保存 ArrayList 中数据的数组 private transient Object[] elementData; // ArrayList 中实际数据的数量 private int size; ``` elementData 存储 ArrayList 内的元素，size 表示包含的元素数量。`transient` 关键字用于标记不参与序列化的字段。 #### 2. 构造函数 ArrayList 提供了三种构造器，可以构造一个指定初始容量的空列表、构造一个默认初始容量为 10 的空列表以及构造一个包含指定 collection 元素的列表。 ```java // 带容量大小的构造函数 public ArrayList(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); this.elementData = new Object[initialCapacity]; } // 默认容量为 10 的构造函数 public ArrayList() { this(10); } // 创建包含指定 collection 元素的 ArrayList public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } ``` #### 3. 元素存储 ArrayList 基于数组实现，添加元素时，如果数组容量不够用，会进行扩容。 ```java // 添加元素 e public boolean add(E e) { ensureCapacity(size + 1); // 确保容量足够 elementData[size++] = e; return true; } // 将集合 c 追加到 ArrayList 中 public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacity(size + numNew); // 确保容量足够 System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } ``` #### 4. 元素读取 ```java // 返回指定位置上的元素 public E get(int index) { RangeCheck(index); return (E) elementData[index]; } ``` #### 5. 元素删除 ArrayList 提供了根据下标或指定对象两种方式的删除功能。 ```java // 删除指定位置的元素 public E remove(int index) { RangeCheck(index); modCount++; E oldValue = (E) elementData[index]; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; // 释放最后一个元素的引用 return oldValue; } ``` #### 6. 调整数组容量 ensureCapacity ArrayList 进行扩容时，会将老数组中的元素拷贝到新数组中，新的容量大约是原容量的 1.5 倍。确保容量的方法如下： ```java public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (oldCapacity * 3) / 2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; elementData = Arrays.copyOf(elementData, newCapacity); } } ``` #### 7. 转为静态数组 toArray 的两种方法 ```java // 返回 ArrayList 的 Object 数组 public Object[] toArray() { return Arrays.copyOf(elementData, size); } // 返回 ArrayList 的模板数组 public <T> T[] toArray(T[] a) { if (a.length < size) return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } ``` #### 8. 实现 Cloneable 接口，实现浅拷贝 ```java public Object clone() { try { ArrayList<E> v = (ArrayList<E>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { throw new InternalError(); } } ``` #### 9. 实现 Serializable 接口，启用序列化功能 ```java private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { int expectedModCount = modCount; s.defaultWriteObject(); s.writeInt(elementData.length); for (int i = 0; i < size; i++) s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } } private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); int arrayLength = s.readInt(); Object[] a = elementData = new Object[arrayLength]; for (int i = 0; i < size; i++) a[i] = s.readObject(); } ``` 以上是对 ArrayList 的详细介绍，包括其继承关系、私有属性、构造函数、元素存储、读取、删除、调整容量、数组转换、浅拷贝和序列化功能。

扩容大小规则是，扩容后的大小= 原始大小+原始大小/2 + 1。（例如：原始大小是 10 ，扩容后的大小就是 10 + 5+1 = 16）