JAVA集合系列——ArrayList实现原理

文章目录

1. 1. ArrayList的实现原理
   1. 1.1. 特点
   2. 1.2. 数据结构
   3. 1.3. ArrayList存取实现
      1. 1.3.1. 初始化
      2. 1.3.2. 存储
      3. 1.3.3. 获取
      4. 1.3.4. 删除
      5. 1.3.5. 扩容
   4. 1.4. 线程安全
   5. 1.5. Fail-Fast机制

ArrayList的实现原理

特点

1. List接口的可变数组实现
2. 允许null值
3. 非线程安全
4. 有序
5. 查询快，插入慢，删除慢

数据结构

ArrayList的数据结构比较简单，底层使用数组保存所有的元素，所有的操作也是在这个数组上.然后使用一个size保存了当前ArrayList的元素个数

//包含元素的个数
private int size;
//底层数组
//transient:表示序列化的时候不包含此属性
private transient Object[] elementData;

ArrayList存取实现

初始化

ArrayList有3个构造函数：无参构造，容量设定构造，列表设定构造，代码如下：

//无参构造，默认容量为10
public ArrayList() {
	this(10);
}
//容量设定构造
public ArrayList(int initialCapacity) {
	super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
	this.elementData = new Object[initialCapacity];
}
//列表设定构造，将列表值置入数组
public ArrayList(Collection<? extends E> c) {
 elementData = c.toArray();
	size = elementData.length;
	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	// 如果toArray()返回不是Object[]，转为Object[]
	if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
}

存储

ArrayList用于存储的方法有：set(int index, E element)，add(E e)，add(int index, E element)，addAll(Collection<? extends E> c)，addAll(int index, Collection<? extends E> c)

//替换index位置的元素，返回旧元素
public E set(int index, E element) {
	//验证index的值，大于size就抛异常
	RangeCheck(index);
	E oldValue = (E) elementData[index];
	elementData[index] = element;
	return oldValue;
}

//添加新元素，放在size+1位置
public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}

//在index位置插入新的元素，index位置后面的元素后移
public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  // Increments modCount!!
	//将elementData的index位置与之后的元素向后移一位
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
}

//添加列表元素，将所有元素追加在elementData数组之后
public boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
    int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
	return numNew != 0;
}

//在index位置插入列表元素
public boolean addAll(int index, Collection<? extends E> c) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: " + index + ", Size: " + size);

	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacity(size + numNew);  // Increments modCount

	int numMoved = size - index;
	if (numMoved > 0)
	    System.arraycopy(elementData, index, elementData, index + numNew,
			     numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
	size += numNew;
	return numNew != 0;
}

获取

//获取指定index位置的元素
public E get(int index) {
  RangeCheck(index);
  return (E) elementData[index];
 }

删除

删除元素有2中方式：根据index位置删除，还有根据对象删除

//删除index位置的元素，并返回这个元素
public E remove(int index) {
	RangeCheck(index);

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;
}
//根据对象删除元素
public boolean remove(Object o) {
	if (o == null) {
            for (int index = 0; index < size; index++)
		if (elementData[index] == null) {
		    fastRemove(index);
		    return true;
		}
	} else {
	    for (int index = 0; index < size; index++)
		if (o.equals(elementData[index])) {
		    fastRemove(index);
		    return true;
		}
        }
	return false;
}

扩容

ArrayList的扩容是在方法ensureCapacity()中，代码如下：

public void ensureCapacity(int minCapacity) {
	modCount++;
	int oldCapacity = elementData.length;
	//需要的容量大于现在数组的容量
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    //新的容量为原来的1.5倍，如果还不够就设置为需要的容量大小
	    int newCapacity = (oldCapacity * 3)/2 + 1;
	    if (newCapacity < minCapacity)
       newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        //将原数组的元素copy到新数组，并扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
	}
}

如果需要的数组容量大于现有数组容量时，就需要新建数组并将原数组的元素copy到新数组中，并且扩充新数组容量为原数组的1.5倍；所以每次容量的扩充都涉及到元素的copy，十分的影响性能和浪费空间，所以最好的方式还是指定ArrayList的初始容量，避免不必要的扩容。

下面我们来看最近经常看到的2个方法，一个是System.arraycopy(),它是一个本地方法，用于元素从一个数组拷贝到另一个数组,

/*** 本地方法-数组拷贝* src : 源数组* srcPos：源数组起始位置* dest：目标数组* destPos：目标数组起始位置* length ： 拷贝元素的长度*/
* 本地方法-数组拷贝
* src : 源数组
* srcPos：源数组起始位置
* dest：目标数组
* destPos：目标数组起始位置
* length ： 拷贝元素的长度
*/
public static native void arraycopy(Object src,  int  srcPos,                                        Object dest, int destPos,                                        int length);
                                        Object dest, int destPos,
                                        int length)

还有一个是 Arrays.copyOf(elementData, newCapacity)，用于创建新容量的数组并拷贝数据

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)     {
    //创新新的数组，容量为newLength
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //将elementData中的元素拷贝到新的数组中
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

线程安全

ArrayList不是线程安全的，多线程环境下可以考虑用Collections.synchronizedList(List)，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

Fail-Fast机制

ArrayList有也Fail-Fast机制，并发修改时，迭代器很快就会完全失败，实现原理同HashMap机制一样,具体可查看HashMap实现原理。