ArrayList源码解析

闲来无事,有空会继续写下
List
LinkedList
CopyOnWriteArrayList
Set
HashSet
LinkedHashSet
Map
HashMap
IdentityHashMap
LinkedHashMap
TreeMap
ConcurrentHashMap
Queue
ArrayBlockingQueue
LinkedBlockingQueue
ConcurrentLinkedQueue

为节省空间对于非重点代码不做展示

什么是ArrayList

ArrayList底层是由数组组成的一种数据结构，可以进行动态的增删改查

ArrayList用来干嘛

ArrayList一般用于对数据的存储

源码解析针对重要点

1. 数据的存储
2. 数据的操作
3. 什么时候扩容
4. 是否线程安全
   带上问题去找答案

   数据的存储

   从我们使用ArrayList开始
   new ArrayList<>();
   public ArrayList() {
       super();
       this.elementData = EMPTY_ELEMENTDATA;
   }
   private static final Object[] EMPTY_ELEMENTDATA = {};
   private transient Object[] elementData;
   elementData为储存数据所用容器，通过默认构造方法创建的ArrayList容器为空

数据的操作

添加

public boolean add(E e) {
	ensureCapacityInternal(size + 1);  
	elementData[size++] = e;//size表示当前使用下表，直接将元素放入到elementData的指定位置
	return true;
}
指定位置的添加，设计到元素的后移
 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++;
}
private void rangeCheckForAdd(int index) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//很常见的异常
}

删除

public E remove(int index) {
	rangeCheck(index);
	checkForComodification();
	E result = parent.remove(parentOffset + index);
	this.modCount = parent.modCount;
	this.size--;
	return result;
}
final void checkForComodification() {
	if (modCount != expectedModCount)//针对在对于list进行遍历时进行其他操作，modCount会改变，而expectedModCount值在listInterator时给定的会抛出异常
		throw new ConcurrentModificationException();
}

查询

 public E get(int index) {
    rangeCheck(index);//这就没啥好多的了
    return elementData(index);
}

什么时候扩容

 public boolean add(E e) {
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}
private void ensureCapacityInternal(int minCapacity) {
	if (elementData == EMPTY_ELEMENTDATA) { //如果容器为空，初始化容器，两个值中取最大值
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;//操作次数+1
	// overflow-conscious code
	if (minCapacity - elementData.length > 0) //扩容，当前元素数量已经等于容器了需要进行扩容
		grow(minCapacity);
}
private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;//当前容器大小
	int newCapacity = oldCapacity + (oldCapacity >> 1);// oldCapacity + oldCapacity*0.5
	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);//扩容
}
private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) // overflow //如果为负数抛出内存溢出错误
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ? //还没有为负数，那么元素最大大小改为int的最大值，注意MAX_ARRAY_SIZE为最大值-8
		Integer.MAX_VALUE :
		MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

是否线程安全

ArrayList不是线程安全的

 以添加为例
 elementData[size++] = e;
 一个 ArrayList ，在添加一个元素的时候，它可能会有两步来完成： 
1. 在 Items[Size] 的位置存放此元素； 
2. 增大 Size 的值。 
在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1； 
而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。 
那好，现在我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。

使用ArrayList的注意事项

1. arrayList不是线程安全的，不要有多个线程同时操作一个arrayList
2. 不要在循环中对arrayList做其他操作，会引发异常
3. 针对已经确定大小的List请直接传入参数，避免多次扩容

参考

• 为什么说ArrayList是线程不安全的？
• jdk源码