【集合类分析】ArrayList

时间：2022-08-07 17:00:26

做题的时候，ArrayList真的是出现频率最高的一个集合类，仔细想一下，主要是因为其不用一开始就确定大小，可以无限添加元素，以及用Collections.sort()将list中的数据排序，并且可以重写比较规则来自定义排序，所以今次就好好总结下ArrayList的底层实现和主要的类方法。

====
特点：
1.ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。
2.ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用List list = Collections.synchronizedList(new ArrayList(…))
函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
3.官方文档称该类与Vector类基本相同，但ArrayList是线程不安全的，Vector是线程安全的。
4.ArrayList允许插入null值。
5.虽然ArrayList的容量是自动增长的，但建议在能大致确定ArrayList的场合可以在初始化的时候就确定大小，可以提高效率。

====
底层实现：
【集合类分析】ArrayList

=====

transient Object[] elementData;
private static final int DEFAULT_CAPACITY = 10;
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
        }
    }

注意其中三个不同的构造方法。无参构造方法构造的ArrayList的容量默认为10。带有Collection参数的构造方法，将Collection转化为数组赋给ArrayList的实现数组elementData。

public void trimToSize() {
        modCount++;
if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

trimToSize方法，可以把当前ArrayList的大小缩小为实际存储元素数的大小。

public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
        } else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
        }
return -1;
    }

indexOf方法，可以看到如果是数组的第一个元素，将返回0

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保数组大小能顺利存放新元素
        elementData[size++] = e; // 存放新元素，并将元素个数加1
return true;
    }
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }// 若当前数组为空，则将minCapacity与10比较，取最大值，设为新的minCapacity

        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0) //判断是否真的需要扩容，比如一开始确定大小的list，minCapacity可能比length小
            grow(minCapacity);
    }
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 变为1.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);
    }

注意扩充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以
容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍加1，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），
而后用Arrays.copyof()方法将元素拷贝到新的数组（详见下面的第3点）。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个
新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。

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;
    }

ArrayList的实现中大量地调用了Arrays.copyof()和System.arraycopy()方法。我们有必要对这两个方法的实现做下深入的了解。
这里可以很明显地看出，该方法实际上是在其内部又创建了一个长度为newlength的数组，调用System.arraycopy()方法，将原来数组中的元素复制到了新的数组中。
下面来看System.arraycopy()方法。该方法被标记了native，调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。该函数实际上最终
调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。
Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

public E remove(int index) {  
        rangeCheck(index); //判断传入的数字是否在合理范围内，即是否小于数组内真实的数据个数 

        modCount++; // 更改次数自增 
        E oldValue = elementData(index); // 将要remove的索引位置的元素取出 
// 将内部数组中空出来的那个位置之后的元素移动到前边去 
int numMoved = size - index - 1;   
if (numMoved > 0)  
            System.arraycopy(elementData, index+1, elementData, index,  
                             numMoved);  
        elementData[--size] = null; // 将最后一位置空，size自减 

return oldValue; // 返回移除的那个数据 
    }  
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,int length);

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。
所以，如果数组有大量的插入或删除操作，建议使用LinkedList。

public void clear() {
        modCount++;

// clear to let GC do its work
for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }  //个人觉得挺好用的方法，将ArrayList内清空，可重复使用，以免浪费内存。
public ListIterator<E> listIterator() {
return new ListItr(0);
    }

返回一个ListIterator，属性fail-fast
fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
标签：

相关文章