⾯试题之---ArrayList实现原理
单列集合图
1. ArrayList是⼀个动态数组，实现了List<E>, RandomAccess, Cloneable, java.io.Serializable，并允许包括null在内的所有元素。
毕业典礼主持词
1.1，实现了RandomAccess接⼝标识着其⽀持随机快速访问，实际上，我们查看RandomAccess源码可
以看到，其实⾥⾯什么都没有定义.因为ArrayList底层是数组，那么随机快速访问是理所当然的，访问速度O(1).
1.2，现了Cloneable接⼝，标识着可以它可以被复制.注意,ArrayList⾥⾯的clone()复制其实是浅复制
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
鼻子怎么描写{
private static final long rialVersionUID = 8683452581122892189L;
/**
* 默认长度是10
*/
private static final int DEFAULT_CAPACITY = 10;
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
// 默认长度是10
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 需要保持的数据⼤于现有的容量时，开始扩容
if (minCapacity - elementData.length > 0)
远光灯图标grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩展为原来的1.5倍, oldCapacity>>1表⽰往右移⼀个单位，就是除以2的1次⽅
足球学校int newCapacity = oldCapacity + (oldCapacity >> 1);
/
/ 如果扩为1.5倍还不满⾜需求，直接扩为你需要的⼤⼩
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//将原来的长度，拷贝变成扩展后的⼤⼩
elementData = pyOf(elementData, newCapacity);
}
2. 底层使⽤数组实现，默认初始容量为10.当超出后，会⾃动扩容为原来的1.5倍，即⾃动扩容机制。
数组的扩容是新建⼀个⼤容量（原始数组⼤⼩+扩充容量）的数组，然后将原始数组数据拷贝到新数组，然后将新数组作为扩容之后的数组。数组扩容的操作代价很⾼，我们应该尽量减少这种操作。
3. 该集合是可变长度数组，数组扩容时，会将⽼数组中的元素重新拷贝⼀份到新的数组中，每次数组容量增长⼤约是其容量的1.5倍，如果扩容⼀半不够，就将⽬标size作为扩容后的容量.这种操作的代价很⾼。采⽤的是 pyOf浅复制,
3.1这⾥简单说⼀下什么是浅复制
浅复制：只复制⼀个对象，但新对象和⽼对象同是⼀个地址值,
深复制：复制⼀个对象，新⽼对象的地址值也变了.
4. 采⽤了Fail-Fast机制，⾯对并发的修改时，迭代器很快就会完全失败，报异常concurrentModificationException(并发修改⼀次),⽽不是冒着在将来某个不确定时间发⽣任意不确定⾏为的风险
5. remove⽅法会让下标到数组末尾的元素向前移动⼀个单位，并把最后⼀位的值置空，⽅便GC
6. 数组扩容代价是很⾼的，因此在实际使⽤时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发⽣。或者根据实际需求，通过调⽤ensureCapacity⽅法来⼿动增加ArrayList实例的容量。
7. ArrayList不是线程安全的，只能⽤在单线程环境下，多线程环境下可以考虑⽤Collections.synchronizedList(List l)函数返回⼀个线程安全的ArrayList类，也可以使⽤concurrent并发包下的CopyOnWriteArrayList类。
eventbus的订阅⽅法subscribe()⾥⾯，就采⽤了线程较为安全的CopyOnWriteArrayList集合
private final Map<Class<?>, CopyOnWriteArrayList<Subscription>> subscriptionsByEventType;
private void subscribe(Object subscriber, SubscriberMethod subscriberMethod) {
Class<?> eventType = subscriberMethod.eventType;
Subscription newSubscription = new Subscription(subscriber, subscriberMethod);
CopyOnWriteArrayList<Subscription> subscriptions = (eventType);
if (subscriptions == null) {
subscriptions = new CopyOnWriteArrayList<>();
subscriptionsByEventType.put(eventType, subscriptions);
} el {
if (ains(newSubscription)) {
throw new EventBusException("Subscriber " + Class() + " already registered to event "
+ eventType);
}
}
8,add(E e)⽅法作⽤: 添加指定元素到末尾
如果要增加的数据量很⼤，应该使⽤ensureCapacity()⽅法，该⽅法的作⽤是预先设置Arraylist的⼤⼩，这样可以⼤⼤提⾼初始化速度.
Object obj = new Object();
ArrayList list0 = new ArrayList();
显卡风扇噪音大long startTime0 = System.currentTimeMillis();
for(int i=0;i<=N;i++){
list0.add(obj);
}
long endTime0 = System.currentTimeMillis();
Log.e("date", "111没有调⽤ensureCapacity()⽅法所⽤时间：" + (endTime0 - startTime0) + "ms");
ArrayList list1 = new ArrayList();
long startTime1 = System.currentTimeMillis();
for(int i=0;i<=N;i++){
list1.add(obj);提词卡
}
long endTime1 = System.currentTimeMillis();
Log.e("date", "222调⽤ensureCapacity()⽅法所⽤时间：" + (endTime1 - startTime1) + "ms");
9，如果是添加到数组的指定位置，那么可能会挪动⼤量的数组元素，并且可能会触发扩容机制；如果是添加到末尾的话，那么只可能触发扩容机制.
10，如果是删除数组指定位置的元素，那么可能会挪动⼤量的数组元素；如果是删除末尾元素的话，那么代价是最⼩的. ArrayList⾥⾯的删除元素，其实是将该元素置为null.
11,Collection是最顶层的集合,Array()在Collection各个⼦类的源码中使⽤频繁
pyOf(U[] original, int newLength, Class<? extends T[]> newType)，就是根据class的类型来决定是new还是反射去构造⼀个泛型数组，同时利⽤native函数，批量赋值元素⾄新数组中.
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//根据class的类型来决定是new还是反射去构造⼀个泛型数组
T[] copy = ((Object)newType == (Object)Object[].class)
以青春的名义宣誓(T[]) new Object[newLength]
: (T[]) ComponentType(), newLength);
//利⽤native函数，批量赋值元素⾄新数组中
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
13, System.arraycopy()复制数组，也是⼀个⾼频使⽤的函数.
如何转化后进生
@FastNative
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos,
int length);
借鉴:
集合各实现类的底层实现原理CopyOnWriteArrayList详解
Java中ArrayList和LinkedList区别
