ArrayList核心知识总结
本文主要从源码的角度出发，对ArrayList体系进行总结。
一、有?过ArrayList吗？它是做什么用的？
ArrayList就是数组列表，底层是数组 Object[] elementData，ArrayList在装载基本数据类型时，实际装载的是对应的包装类。
与ArrayList类似的还有LinkedList，他们俩相?：
- ArrayList：查找和访问元素的速度快，新增、删除的速度慢。线程不安全，使?频率?。
- LinkedList：查找和访问元素的速度慢，新增、删除的速度快。
二、ArrayList线程不安全，为什么还要去用？
实际开发中有以下?种场景：
- 频繁增删：使?LinkedList，但是涉及到频繁增删的场景不多
- 追求线程安全：使?Vector。
- 普通的?来查询：使?ArrayList，使?的场景最多。
根据数据结构的特性，三者难以全包含，只能在相互之间做取舍。
三、ArrayList底层是数组，那是怎么实现不断扩容的？
- 使??参构造创建ArrayList
/**
* Default initial capacity.
* 默认的初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
这个是创建的默认??的空数组。EMPTY_ELEMENTDATA?于表示当第?个数据被添加时该空数组初始化的??。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
* 构造?个空的List，该List具有10个容量
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
使?ArrayList空参的构造器创建集合时，数组并没有创建。当集合中添加第?个元素时，数组被创建，初始化容量为10.
- 使?有参构造创建ArrayList
有参构造创建时，如果指定了容量则会创建出指定容量??的数组。如果指定容量为0，则与?参构造?样。
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
四、ArrayList(int initialCapacity)会不会初始化数组大小？
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial
capacity
* is negative
*/
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);
}
}
会初始化??，但如果通过ArrayList的size()?法进?判断时结果依然为0，因为只有在添加元素时才会对ArrayList的size属性+1
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
五、ArrayList底层是?数组实现，但数组长度是有限的，如何实现扩容？
当新增元素，ArrayList放不下该元素时，触发扩容。
扩容的容量将会是原容量的1/2，也就是新容量是旧容量的1.5倍。
确定新容量确定的源码：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量=旧容量+1/2旧容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
执?扩容时使?系统类System的数组复制?法arraycopy()进?扩容。
扩容的源码：
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
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;
}
六、ArrayList1.7之前和1.7及以后的区别？
1.7之前ArrayList在初始化的时候直接调?this(10)，初始化容量为10的数组。在1.7及以后，只有第?次执?add?法向集合添加元素时才会创建容量为10的数组。
七、为什么ArrayList增删?较慢，增删是如何做的？
- 没有指定index添加元素
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
- 如果指定了index添加元素
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their
indices).
*
* @param index index at which the specified element is to be
inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
从源码?看到，是将要添加的元素位置index之后的已有元素全部拷?到添加到原数组index+1处，然后再把新的数据加?。
八、ArrayList插?和删除数据?定慢吗？
不?定，取决于删除的数据离数组末端有多远，如果离末端较近，则性能不?定差。
九、ArrayList如何删除数据？
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
}
ArrayList删除数据时同样使?拷?数组的?式，将要删除的位置之后的所有元素拷到当前位置，最后再对最后?个位置的数据设置为null，交给gc来回收。这种删除，其实就是覆盖，如
果数据量?，那么效率很低。
十、ArrayList适合做队列吗？
队列需要遵循先进先出的原则，如果从ArrayList的数组头部?队列，数组尾部出队列，那么对于?队列时的操作，会涉及?数据量的数组拷?，?分耗性能。队头队尾反?反也是?样，因此ArrayList不适合做队列。
十一、数组适合做队列吗？
ArrayBlockingQueue环形队列就是?数组来实现的。ArrayBlockingQueue的存和取操作的索引是在当索引值等于容量值时，将索引值设置为0实现环形队列的效果，因此在这种情况下，数组适合做队列。
/**
* Inserts element at current put position, advances, and signals.
* Call only when holding lock.
*/
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x;
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal();
}
/**
* Extracts element at current take position, advances, and
signals.
* Call only when holding lock.
*/
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
return x;
}
十二、ArrayList和LinkedList两者的遍历性能孰优孰劣？
ArrayList的遍历性能明显要?LinkedList好，因为ArrayList存储的数据在内存中时连续的，CPU内部缓存结构会缓存连续的内存?段，可以?幅降低读取内存的性能开销。
十三、ArrayList和LinkedList的区别？
ArrayList： 基于动态数组，连续内存存储，适合下标访问（随机访问），扩容机制：因为数组长度固定，超出长度存储数据时需要新建数组，然后将老数组的数据拷贝到新数组，如果不是尾部插入数据还会涉及到元素的移动（往后复制一份，插入新元素），使用尾插法并指定初始容量可以极大提升性能，甚至超过LinkedList（需要创建大量的node对象）。
LinkedList： 基于链表，可以存储在分散的内存中，适合做数据插入及删除操作，不适合查询：需要逐一遍历。遍历LinkedList必须使用iterator不能使用for循环，因为每次for循环体内通过get(i)取得某一元素时需要对list重新进行遍历，性能消耗极大。
另外不要试图使用indexOf等返回元素索引，并利用其进行遍历，使用indexOf对list进行了遍历，当结果为空时会遍历整个列表。
