ArrayList原理
ArrayList集合底层数据结构
ArrayList集合介绍
List 接口的可调整大小的数组实现。
数组：一旦初始化长度就不可以发生改变
数组结构特性
增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
查询快：由于数组在内存中是一块连续空间，因此可以根据地址 索引的方式快速获取对应位置上的元素。
ArrayList继承关系
Serializable序列化接口
类的序列化由实现java.io.Serializable接口的类启用。 不实现此接口的类将不会使任何状态序列化或反序列化。 可序列化类的所有子类型都是可序列化的。 序列化接口没有方法或字段，仅用于标识可串行化的语义。
序列化是将对象状态转换为可保持或传输的格式的过程。
与序列化相对的是反序列化，它将流转换为对象。
比如将对象的数据序列化后写入到文件；
将文件中对象的数据读取出来后反序列化解析成对象。
在需要进行对象数据网络传输或持久化时，需要将对象进行序列化
源码
代码语言：javascript复制public interface Serializable {
} 从源码上看Serializable是一个空接口，Java里称为标识接口，当类实现Serializable接口，相当于给该类标记了“可被序列化”的元数据，打上了“可被序列化”的标签。
序列化/反序列化测试
代码语言：javascript复制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("testoutfileobj.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实体类
public 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。运行会出现下图报错
User实体类不实现Serializable判断是否实现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);运行速度比这个循环快：
代码语言：javascript复制// 顺序访问，迭代器进行遍历
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();源码
代码语言：javascript复制public interface RandomAccess {
}测试顺序访问和随机访问速度
代码语言：javascript复制 /**
* 测试随机访问比顺序访问快，这里仅对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克隆接口
一个类实现了Cloneable接口，以向Object.clone()方法指示该方法可以合法地对该类的实例进行逐个字段的复制。
在未实现Cloneable接口的实例上调用 Object.clone() 方法会导致抛出异常CloneNotSupportedException 。
源码
代码语言：javascript复制public interface Cloneable {
}
Cloneable也是一个标识接口，此接口不包含clone方法。因此，不可能仅凭借实现该接口的实例来克隆对象。即使以反射方式调用 clone 方法，也不能保证它会成功。
clone()使用实例
代码语言：javascript复制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();
}
}浅拷贝测试类
代码语言：javascript复制/**
* 浅拷贝
*/
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对象。
深拷贝测试类
代码语言：javascript复制/**
* 深拷贝 实现地方在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引用对象的深拷贝。
ArrayList源码
构造方法
代码语言：javascript复制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，将空数组的地址赋值给elementData
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接口
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()方法
添加单个元素
代码语言：javascript复制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!!
// 每次都会把新添加的元素放到数组末尾,ArrayList顺序存放的原因
elementData[size ] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 这里会判断下当前ArrayList是否为空，为空则先初始化数组，
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算ArrayList容量，
