ArrayList原理ArrayList收集底层数据结构
ArrayList集合介绍
List 实现可调接口大小的数组。
数组：一旦初始化长度不能改变
数组结构特征
添加和删除缓慢：每次删除元素时，都需要更改数组长度、副本和移动元素的位置。
快速查询：由于数组是内存中的连续空间，因此可以根据地址+索引快速获取相应位置的元素。
ArrayList继承关系Serializable序列化接口实现了类的序列化java.io.Serializable接口类启用。 未实现此接口的类别将不会使任何状态序列化或反序列化。 所有子类型的可序列化都是可序列化的。 序列接口没有方法或字段，只用于识别可串行语义。
序列化是将对象状态转换为可维持或传输格式的过程。
与序列化相对的是反序列化，它将流转换为对象。
例如，将对象的数据序列化并写入文件；
读取文件中对象的数据后，反序列化解析为对象。
当需要传输或持久对象数据网络时，需要序列化对象
源码
public interface Serializable { } 从源码上看Serializable它是一个空接口，在Java中被称为标识接口，实现了类别Serializable界面，相当于给这类标有“可序列化”的元数据，贴上“可序列化”的标签。
序列化/反序列化测试
static class Sertest01 { public static void main(String[] args) throws IOException, ClassNotFoundException { // 将测试序列化写入文件 writeObject(); // 读取测试反序列化文件 readObject(); } // 将对象数据写入文件 private static void writeObject() throws IOException { // 序列化:将对象的数据写入文件(写对象) ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("testoutfile\obj.txt")); User user = new User("李四", 78); // 将对象数据写入文件 oos.writeObject(user); // 关闭流 oos.close(); } // 将对象数据写入文件 private static void readObject() throws IOException, ClassNotFoundException { // 反序列化：读取文件中对象的数据（读取对象） ObjectInputStream ois = new ObjectInputStream(new FileInputStream("..\obj.txt")); User user = (User) ois.readObject(); // 将对象数据写入文件 System.out.println(user.toString()); // 关闭流 ois.close(); }}// user实体类publicicic class User implements Serializable { /** * 实现了类的序列化`java.io.Serializable`接口类启用。 * 未实现此接口的类别将不会使任何状态序列化或反序列化。 * 未实现此接口的类别将不会使任何状态序列化或反序列化。 * 所有子类型的可序列化都是可序列化的。 * 序列接口没有方法或字段，只用于识别可串行语义。 */ public final long serialVersionUID = 1510141000893066237L; private String name; private Integer age; public User() { } public User(String name, Integer age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Integer getAge() { return age; } public void setAge(Integer age) { this.age = age; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age).append("]"); return sb.toString(); }}实现了Serializable接口的User类可以被ObjectOutputStream将文件转换为字节流，也可以通过ObjectInputStream然后从文件中读取并分析为对象。
如果User实体类没有实现Serializable如果不能序列化或反序列化，就会抛出异常NotSerializableException。下图将报告操作中的错误
判断是否实现Serializable的源码
if (obj instanceof String) { writeString((String) obj, unshared);} else if (cl.isArray()) { writeArray(obj, desc, unshared);} else if (obj instanceof Enum) { writeEnum((Enum<?>) obj, desc, unshared);} else if (obj instanceof Serializable) { writeOrdinaryObject(obj, desc, unshared);} else { if (extendedDebugInfo) { throw new NotSerializableException( cl.getName() + "\n" + debugInfoStack.toString()); } else { throw new NotSerializableException(cl.getName()); }}从这里可以看出，Java在序列化字符串、数组、枚举类和普通类时单独判断，当普通类没有实现时Serializable界面会抛出异常NotSerializableException。
RandomAccess随机访问List使用的标记接口表明它们支持快速（通常是恒定时间）的随机访问。该接口的主要目的是允许通用算法改变其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能。
用于操作随机访问列表(如ArrayList ）顺序访问列表中应用的最佳算法(例如LinkedList ）二次行为。鼓励一般列表算法在应用算法之前检查给定列表是否为此接口的例子。如果将其应用于顺序访问列表，它将提供更差的性能，并在必要时更改它们的行为，以确保可接受的性能。
众所周知，随机访问和顺序访问之间的区别通常是模糊的。例如，如果有一些，List如果实现变得非常大，它将提供渐近线性访问时间，但在实践中，访问时间是恒定的。这种List实现通常应该实现这个接口。根据经验，如果类的典型例子出现以下循环，则List该接口应实现：
// 随机访问，list.get(i)for根据索引遍历 (int i=0, n=list.size(); i < n; i++) list.get(i);运行速度比这个循环快:
// 顺序访问，迭代器遍历for (Iterator i=list.iterator(); i.hasNext(); ) i.next();源码
public interface RandomAccess {}测试顺序访问和随机访问速度
/** * 测试随机访问速度快于顺序访问，这里只有ArrayList的经验操作 * * @param args */ public static void main(String[] args) { // 创建ArrayList集合 List<String> list = new ArrayList<>(); // 添加50W条数据 for (int i = 0; i < 500000; i++) { list.add(i + "a"); } System.out.println("----通过索引(随机访问)----"); long startTime = System.currentTimeMillis(); for (int i = 0; i < list.size(); i++) { list.get(i); } long endTime = System.currentTimeMillis(); System.out.println("随机访问： " + (endTime - startTime)); System.out.println("----通过迭代器(顺序访问)----"); startTime = System.currentTimeMillis(); Iterator<String> it = list.iterator(); while (it.hasNext()) { it.next(); } endTime = System.currentTimeMillis(); System.out.println("顺序访问时： " + (endTime - startTime)); }//----通过索引(随机访问)----//随机访问： 3//----通过迭代器(顺序访问)----//顺序访问时： 4从输出结果来看ArrayList随机访问速度比顺序访问快。接下来比较一下LinkedList
public static void main(String[] args) { // 创建ArrayList集合 List<String> list = new LinkedList<>(); // 添加10W条数据 for (int i = 0; i < 100000; i++) { list.add(i + "a"); } System.out.println("----通过索引(随机访问)----"); long startTime = System.currentTimeMillis(); for (int i = 0; i < list.size(); i++) { list.get(i); } long endTime = System.currentTimeMillis(); System.out.println("随机访问： " + (endTime - startTime)); System.out.println("----通过迭代器(顺序访问)----"); startTime = System.currentTimeMillis(); Iterator<String> it = list.iterator(); while (it.hasNext()) { it.next(); } endTime = System.currentTimeMillis(); System.out.println("顺序访问时： " + (endTime - startTime)); }//----通过索引(随机访问)----//随机访问： 11851//----通过迭代器(顺序访问)----//顺序访问时： 3从输出结果来看LinkedList顺序遍历比随机访问快。
LinkedList源码
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ // 这里不讨论具体实现的源码，省略...}可以看到LinkedList并没有实现RandomAccess接口，符合RandomAccess此外，界面介绍内容LinkedList该结构还确定了其顺序遍历速度快于随机访问。
建议在实际应用场景中使用instanceof判断集合是否实现RandomAccess接口，然后根据实际情况使用随机访问或顺序访问。
if(list instanceof RandomAccess) // 随机访问else // 顺序访问实现了一个类Cloneable接口，以向Object.clone()该方法表明该方法可以合法地逐字段复制此类实例。
在未实现Cloneable调用接口实例 Object.clone() 该方法会导致异常抛出CloneNotSupportedException 。
源码
public interface Cloneable {}Cloneable它也是一个识别接口，不包括clone方法。因此，仅仅通过实现该接口的示例来克隆对象是不可能的。即使是反射调用 clone 方法，也不能保证它会成功。
clone()使用实例
public static void main(String[] args) { // 创建用户对象集合 ArrayList<User> list = new ArrayList<User>(); list.add(new User("李四", 78)); list.add(new User("张三", 28)); Object o = list.clone(); System.out.println(o); System.out.println(list); System.out.println(o == list);}// false// [[name = 李四, age = 78], [name = 张三, age = 28]]// [[name = 李四, age = 78], [name = 张三, age = 28]]从输出看，clone()内容与原对象一致的新对象创建。
ArrayList实现了Cloneable因此，这种接口可以调用Object.clone()实现对象克隆的方法。
若类没有实现Cloneable接口，本例调用 Object.clone() 该方法会导致异常抛出CloneNotSupportedException 。
clone源码
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); }}Object.clone() 方法修改User类，使支持 Object.clone() 方法
public class User implements Serializable, Cloneable { public final long serialVersionUID = 1510141000893066237L; // 属性 getter setter toString... // 重写clone @Override public Object clone() throws CloneNotSupportedException { return super.clone(); }}User类实现Cloneable接口，并重写 Object.clone() 方法。
重写原则
- 子类返回类型小于或等于父类方法返回类型
- 子类抛出异常小于等于父类抛出异常
- 子类访问权大于或等于父类访问权（public>protected>friendly，private不能继承。
static class cloneable01 { public static void main(String[] args) throws CloneNotSupportedException { User user1 = new User("张", 12); Object user2 = user1.clone(); System.out.println(user1); System.out.println(user2); System.out.println(user1 == user2); }}// [name = 张, age = 12]// [name = 张, age = 12]// false新建Address类，如下所示
public class Address implements Serializable { public final long serialVersionUID = 1578511564815489L; private String city; public Address() { } public Address(String city) { this.city = city; } public String getCity() { return city; } public void setCity(String city) { this.city = city; } @Override public String toString() { return city; }}修改User类如下所示
public class User implements Serializable, Cloneable { public final long serialVersionUID = 1510141000893066237L; private String name; private Integer age; private Address address; // setter getter... @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("[").append("name = ").append(this.name).append(", ").append("age = ").append(this.age); if (address != null) sb.append(", address = ").append(this.address.toString()); sb.append("]"); return sb.toString(); } @Override public Object clone() throws CloneNotSupportedException { return super.clone(); }}浅拷贝测试类
/** * 浅拷贝 */static class cloneable02 { public static void main(String[] args) throws CloneNotSupportedException { Address address = new Address("北京"); User user1 = new User("张", 12, address); User user2 = (User)user1.clone(); System.out.println(user1); System.out.println(user2); System.out.println(user1 == user2); System.out.println(user2.getAddress() == user1.getAddress()); address.setCity("海口"); user1.setAddress(address); System.out.println(user1); System.out.println(user2); }}//[name = 张, age = 12, address = 北京]//[name = 张, age = 12, address = 北京]//false//true//[name = 张, age = 12, address = 海口]//[name = 张, age = 12, address = 海口]从输出结果中可以知道User可以完全复制类的基本数据类型，但不能引用数据类型。
原因在于在User对象user1当被克隆时，它的属性address作为引用类型，只复制一个引用，两者指向的地址仍然一致。因此，当address当价值发生变化时，克隆对象的价值发生变化user2的属性address值也会改变。
修改Address类，如下所示
public class Address implements Serializable, Cloneable { public final long serialVersionUID = 1578511564815489L; // getter setter toString... @Override public Object clone() throws CloneNotSupportedException { return super.clone(); }}Address类实现Cloneable并重写界面 Object.clone() 方法。
修改User类如下所示
public class User implements Serializable, Cloneable { // 属性 setter getter toString... /** * clone()调用引用对象，实现深拷贝 * * @return * @throws CloneNotSupportedException */ @Override public Object clone() throws CloneNotSupportedException { User user = (User) super.clone(); Address address = (Address) this.address.clone(); user.setAddress(address); return user; }}之前重写的super.clone()不能复制引用对象，然后调用Address类的clone() 方法，拷贝address然后赋值属性user对象。
深拷贝测试类
/** * 深拷贝 在User中实现位置、Address类 */static class cloneable03 { public static void main(String[] args) throws CloneNotSupportedException { Address address = new Address("北京"); User user1 = new User("张", 12, address); User user2 = (User) user1.clone(); System.out.println(user1); System.out.println(user2); System.out.println(user1 == user2); System.out.println(user2.getAddress() == user1.getAddress()); address.setCity("海口"); user1.setAddress(address); System.out.println(user1); System.out.println(user2); }}//[name = 张, age = 12, address = 北京]//[name = 张, age = 12, address = 北京]//false//false//[name = 张, age = 12, address = 海口]//[name = 张, age = 12, address = 北京]测试类没有代码修改，主要修改是User、Address类。
从输出结果来看，已经实现了address引用对象的深拷贝。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ // 默认长度为0的数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 存储 ArrayList 元素数组缓冲区。 ArrayList 这个数组缓冲区的长度是容量。 transient Object[] elementData; // 给elementData赋值 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }}集合对象是通过无参结构方法创建的，只会DEFAULTCAPACITY_EMPTY_ELEMENTDATA 地址赋值(默认长度为0的数组)elementData(数组缓冲区存储ArrayList元素)
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ // 共享空数组实例用于空实例。 private static final Object[] EMPTY_ELEMENTDATA = {}; // 构建具有指定初始容量的空列表。 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 长度大于0，创建指定长度的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // 长度为0，将空数组的地址赋值给elementDatata this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }}根据 ArrayList 构造方法参数创建指定长度的数组。如果指定长度等于0，则直接给出elementData赋值EMPTY_ELEMENTDATA(空数组实例)
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ // 按照集合迭代器返回的顺序构建包含指定集合元素的列表 public ArrayList(Collection<? extends E> c) { // 转成数组 Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA; } } // Collection接口实现Collection接口 public Object[] toArray() { return Arrays.copyOf(elementData, size); }}class Arrays { // 复制指定数组，切断或填充空值(必要时)，使副本具有指定长度。 public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } // 复制指定数组，切断或填充空值(必要时)，使副本具有指定长度。 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { @SuppressWarnings("unchecked") // 无论三元运算符的结果如何，都会创建一个新的数组 // 新数组的长度必须与集合的size相同 T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); // 数组的拷贝 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); // 返回新数组 return copy; } // 创建具有指定组件类型和长度的新数组。 public static Object newInstance(Class<?> componentType, int length) throws NegativeArraySizeException { return newArray(componentType, length); }}使用ArrayList<User> userList = new ArrayList<User>(list)当构建一个集合时，它将进入这种构建方法，通过三目表达式判断构建一个Object集合还是newType集合中元素类型。
add()方法添加单个元素
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ // ArrayList的大小 private int size; // 默认大小为空的例子，共享空数组实例 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 集合存元素的数组 Object[] elementData; // 默认的容量 private static final int DEFAULT_CAPACITY = 10; // 数组的最大尺寸，2^31-1-8 = 2147483647-8，一些 VM 在数组中保留一些标题字。尝试分配更大的数组可能会导致 OutOfMemoryError：要求的数组大小超过 VM 限制 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 将指定元素附加到列表的末尾 public boolean add(E e) { // 在每次添加元素之前，动态调整数组的大小，避免溢出 ensureCapacityInternal(size + 1); // Increments modCount!! // 新添加的元素每次都会放在数组的末尾，ArrrayList顺序存储的原因 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { // 这里将判断当前ArrayList是否为空，数组先初始化为空， ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } // 计算ArrayList容量， 
湘公网安备43019002002060