本文共 11294 字，大约阅读时间需要 37 分钟。

ArrayList:基于动态数组实现,访问较快,增删较慢,线程不安全

实现原理: ArrayList底层实现原理: https://www.cnblogs.com/maoyali/p/8805975.html https://www.cnblogs.com/AmyZheng/p/9427140.html 构造函数: 无参构造: public ArrayList() { //对象数组就指向到一个空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

指定初始容量构造:

public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //初始容量大于0 new 一个新数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { //小于零直接报错 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }

指定集合作为初始参数的:

注意这里 // c.toArray might (incorrectly) not return Object[] (see 6260652) https://blog.csdn.net/GuLu_GuLu_jp/article/details/51457492 主要原因是 c.toArray()调用的具体实现类中的toArray()方法,向下转型时不安全 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添加元素扩容机制:

先看几个基础属性:

//elementData中已存放的元素的个数，注意：不是elementData的容量private int size;//elementData的默认容量为10private static final int DEFAULT_CAPACITY = 10;//对象数组：ArrayList的底层数据结构，transient表示该字段不进行序列化操作transient Object[] elementData;//实例化一个空数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
   };//实例化一个空数组private static final Object[] EMPTY_ELEMENTDATA = {
   };//修改次数protected transient int modCount = 0;@Native public static final int   MAX_VALUE = 0x7fffffff;private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

1: 向末尾添加

public boolean add(E e) {
           ensureCapacityInternal(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;    }// minCapacity = seize+1，即表示执行完添加操作后，数组中的元素个数    private void ensureCapacityInternal(int minCapacity) {
           ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));    }	//获取数组的最小容量(或者说元素个数) 要么是10 要么是 添加元素后 元素个数,(直接当作元素个数更好理解)	private static int calculateCapacity(Object[] elementData, int minCapacity) {
           if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   		 //用最小容量和10进行比较，取最大值赋值给最小容量            return Math.max(DEFAULT_CAPACITY, minCapacity);        }        return minCapacity;    }		//这个方法是用来确保容量的  private void ensureExplicitCapacity(int minCapacity) {
           modCount++;        // overflow-conscious code		//元素个数   >  数据长度   扩容        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }	//扩容 	private void grow(int minCapacity) {
   			// overflow-conscious code			int oldCapacity = elementData.length;			// 新容量大小等于  旧容量 + 旧容量的1/2取整((oldCapacity >> 1) 右移一位相当于除以2,取整)			int newCapacity = oldCapacity + (oldCapacity >> 1);			 //如果新的容量小于数组个数，将数组个数赋值给新容量			if (newCapacity - minCapacity < 0)				newCapacity = minCapacity;			// 如果新的容量大于最大容量，就根据数组个数来决定新的容量大小			if (newCapacity - MAX_ARRAY_SIZE > 0)				newCapacity = hugeCapacity(minCapacity);			 // 根据新的容量，将数组拷贝到新的数组并赋值给数组			elementData = Arrays.copyOf(elementData, newCapacity);		}

**2:**向指定位置添加

public void add(int index, E element) { rangeCheckForAdd(index);

ensureCapacityInternal(size + 1);  // Increments modCount!!	 //通过拷贝使数组内位置为 index 到 （size-1）的元素往后移动一位    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);	 // 找到位置添加元素    elementData[index] = element;    size++;}

**3:**删除指定位置的元素

public E remove(int index) {
   		//指定位置检查        rangeCheck(index);        modCount++;		//获取要删除的值        E oldValue = elementData(index);		//要移动元素个数        int numMoved = size - index - 1;        if (numMoved > 0)		   //通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);		//清除末尾元素让GC回收					         elementData[--size] = null; // clear to let GC do its work        return oldValue;    }

4: 删除指定元素

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;    }//遍历找到序号  然后删除   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    }

5: 缩容

正如你所看到的那样,增加元素的时候会扩容,减少元素的时候却不会缩容,但是ArrayList中有一个方法是可以缩容的,需要自己主动去调用

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

---

线程安全的 CopyOnWriteArrayList

参考:https://blog.csdn.net/hua631150873/article/details/51306021 CopyOnWriteArrayList这是一个ArrayList的线程安全的变体， Copy-On-Write简称COW(CopyOnWriteArrayList和CopyOnWriteArraySet)，是一种用于程序设计中的优化策略。 其基本思路是，从一开始大家都在共享同一个内容，当某个人想要修改这个内容的时候，才会真正把内容Copy出去形成一个新的内容然后再改,，最后把新的容器的引用地址赋值给了之前那个旧的的容器地址， 但是在添加这个数据的期间，其他线程如果要去读取数据，仍然是读取到旧的容器里的数据。这是一种延时懒惰策略。

上源码:

构造函数 3个(有参2个,无参一个)

public CopyOnWriteArrayList() {
   	setArray(new Object[0]);}public CopyOnWriteArrayList(Collection
    c) {
       Object[] elements;    if (c.getClass() == CopyOnWriteArrayList.class)        elements = ((CopyOnWriteArrayList)c).getArray();    else {        elements = c.toArray();        // c.toArray might (incorrectly) not return Object[] (see 6260652)        if (elements.getClass() != Object[].class)            elements = Arrays.copyOf(elements, elements.length, Object[].class);    }    setArray(elements);}public CopyOnWriteArrayList(E[] toCopyIn) {    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));}  final void setArray(Object[] a) {
       array = a;}

无论使用哪一种构造 创建一个Object类型的数组，然后赋值给array

**1,**在末尾添加元素:

public boolean add(E e) {
           final ReentrantLock lock = this.lock;        lock.lock();        try {
               Object[] elements = getArray();            int len = elements.length;            Object[] newElements = Arrays.copyOf(elements, len + 1);  //复制            newElements[len] = e;   //赋值            setArray(newElements);  //重新指向            return true;        } finally {
               lock.unlock();        }    }

可以看到,加了lock锁,其工作流程是 先复制出一份,然后整出一个新的长度+1的数组,

然后在数据最后一位赋上新值,最后将新的数组赋值给旧的数组

**2,**在指定位置添加

public void add(int index, E element) {
           final ReentrantLock lock = this.lock;		lock.lock();        try {
               Object[] elements = getArray();            int len = elements.length;            if (index > len || index < 0)   //指定位置不能超过原数组长度 也不能小于 0                throw new IndexOutOfBoundsException("Index: "+index+                                                    ", Size: "+len);            Object[] newElements;            int numMoved = len - index;            if (numMoved == 0)  //在末尾添加                newElements = Arrays.copyOf(elements, len + 1);            else {
     //在指定位置添加                newElements = new Object[len + 1];                System.arraycopy(elements, 0, newElements, 0, index);                System.arraycopy(elements, index, newElements, index + 1,                                 numMoved);            }            newElements[index] = element;            setArray(newElements);        } finally {
               lock.unlock();        }

3,获取元素

public E get(int index) {
           return get(getArray(), index);    }	 private E get(Object[] a, int index) {
           return (E) a[index];    }

它是没加锁的,所以再添加的时候,获取的还是旧数组的元素

4.移除指定元素

public E remove(int index) {
       final ReentrantLock lock = this.lock;    lock.lock();    try {
           Object[] elements = getArray();        int len = elements.length;        E oldValue = get(elements, index);        int numMoved = len - index - 1;        if (numMoved == 0) //移除最后一个元素            setArray(Arrays.copyOf(elements, len - 1));        else {
   		   Object[] newElements = new Object[len - 1];            System.arraycopy(elements, 0, newElements, 0, index);            System.arraycopy(elements, index + 1, newElements, index,                             numMoved);            setArray(newElements);        }        return oldValue;    } finally {
           lock.unlock();    }}

移除的时候是加锁的,其流程是:先new一个新的长度减一的新数组,然后将前面的和后面的拷贝进新数组,

最后将新的数组赋值给旧的数组

5,移除指定元素:

public boolean remove(Object o) {
           Object[] snapshot = getArray();        int index = indexOf(o, snapshot, 0, snapshot.length);  //获取元素的位置        return (index < 0) ? false : remove(o, snapshot, index);    }		 private static int indexOf(Object o, Object[] elements,                               int index, int fence) {
           if (o == null) {
               for (int i = index; i < fence; i++)                if (elements[i] == null)                    return i;        } else {
               for (int i = index; i < fence; i++)                if (o.equals(elements[i]))                    return i;        }        return -1;  //-1就是指没找到    }		  private boolean remove(Object o, Object[] snapshot, int index) {
           final ReentrantLock lock = this.lock;        lock.lock();        try {
               Object[] current = getArray();            int len = current.length;            if (snapshot != current) findIndex: {
     // 当前数组已经被改变了                int prefix = Math.min(index, len);                for (int i = 0; i < prefix; i++) {
                       if (current[i] != snapshot[i] && eq(o, current[i])) {
                           index = i;                        break findIndex;                    }                }                if (index >= len)                    return false;                if (current[index] == o)                    break findIndex;                index = indexOf(o, current, index, len);                if (index < 0)                    return false;            }            Object[] newElements = new Object[len - 1];            System.arraycopy(current, 0, newElements, 0, index);            System.arraycopy(current, index + 1,                             newElements, index,                             len - index - 1);            setArray(newElements);            return true;        } finally {
               lock.unlock();        }    }

这里有点迷糊了,有机会再看

看两个常用方法:

Arrays.copyOf(): 参考: https://blog.csdn.net/yuxuan89814/article/details/49467939 功能是实现数组的复制， 返回复制后的数组。参数是被复制的数组和复制的长度, 复制的长度大于被复制数组的长度，则填充类型默认值，String得默认值是null,int的默认值是0 浅拷贝 使用对象数组时请注意

System.arraycopy :

参考: https://blog.csdn.net/qq_32440951/article/details/78357325 https://www.cnblogs.com/java-hr/p/11260506.html https://blog.csdn.net/chenqianleo/article/details/77480407 System中提供了一个native静态方法arraycopy(), 可以使用这个方法来实现数组之间的复制。基本类型不受影响 ,浅拷贝 使用对象数组时请注意 System.arraycopy(elements, 0, newElements, 0, index)方法 参数依次是: src - 源数组。 srcPos - 源数组中的起始位置。 dest - 目标数组。 destPos - 目的地数据中的起始位置。 length - 要复制的源数组元素的数量。

转载地址：https://blog.csdn.net/xy3233/article/details/109410346 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！