侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

ArrayList原理探究

林贤钦
2020-05-26 / 0 评论 / 13 点赞 / 612 阅读 / 0 字
温馨提示:
本文最后更新于 2020-05-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

ArrayList原理探究

ArrayList简介

ArrayList 是一个数组队列,相当于动态数组,与java数组相比,它的容量能动态增长

ArrayList继承体系

ArrayList继承于AbstractList,实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。

  • 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。

  • 实现了RandmoAccess接口,即提供了随机访问功能。RandmoAccess是java中用来被List实现,为List提供快速访问功能的。在ArrayList中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。

  • 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。

  • 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。

ArrayList时间复杂度

  • add(E e)方法

    添加元素到末尾,平均时间复杂度为O(1)。

  • add(int index, E element)方法

    添加元素到指定位置,平均时间复杂度为O(n)。

  • get(int index)方法

    获取指定索引位置的元素,时间复杂度为O(1)。

  • remove(int index)方法

    删除指定索引位置的元素,时间复杂度为O(n)。

  • remove(Object o)方法

    删除指定元素值的元素,时间复杂度为O(n)。

ArrayList属性

    //序列化id
    private static final long serialVersionUID = 8683452581122892189L;

    //默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    //一个空对象
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //一个空对象,如果使用默认构造方法创建,则默认对象内容是该值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //当前数据对象存放地方,当前对象不参与序列化
    transient Object[] elementData; 

    //数组长度
    private int size;

    // 数组最大长度
    private static final int MAX_ARRAY_SIZE = 2147483639;

ArrayList构造方法

  • 无参构造方法

    public ArrayList() {
        //如果使用默认的构造方法,则初始对象为空,size=0
        //当第一次add的时候才默认长度size = DEFAULT_CAPACITY=10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
  • 带int的构造方法

    1. 如果参数为大于0,则创建一个大小为initialCapacity的数组
    2. 如果等于0,则数据存放对象等于空对象
    3. 如果小于0,则抛出异常
    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);
        }
    }
    
  • 带Collection对象的构造函数

    1. 将collection对象转换成数组,然后将数组的地址的赋给elementData。
    2. 更新size的值,同时判断size的大小,如果是size等于0,直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData
    3. 如果size的值大于0,则执行Arrays.copy方法,把collection对象的内容(可以理解为深拷贝)copy到elementData中。
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

ArrayList的crud

1、get方法

public E get(int index) {
    //检查数组是否越界
    rangeCheck(index);
    return elementData(index);
}

private void rangeCheck(int index) {
    //如果索引超过大小,抛出索引越界异常
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

2、add方法

带一个参数的add方法将指定元素追加到此列表的末尾

  1. 如果原数组长度为0,则扩容到默认长度10
  2. 如果原数组长度不为0,有两种情况
    • size+1不超过数组长度,新元素直接加在末尾,不用扩容
    • 如果size+1超过数组长度,进行扩容,新数组长度等于旧数组长度*1.5,即扩容1.5倍,然后将新元素插入size位置
public boolean add(E e) {
    //确保内部容量
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    //将calculateCapacity方法返回的结果比较,看是否需要扩容
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//判断原数组是否是空对象,如果是就返回返回Math.max(DEFAULT_CAPACITY, minCapacity),一般返回10
//不是就返回原来的minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果数组等于默认空对象数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //如果小于默认容量,则返回默认容量,否则返回原来的minCapacity
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果增加的索引大于数组的大小,则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //扩容1.5倍
    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);
}

带两个参数的add方法在此列表的指定位置插入元素

  1. 检查插入索引是否越界
  2. 确保内部容量,和上面一样,如果空数组就默认容量10,然后扩容,如果越界就扩容,没越界就不用
  3. 数组拷贝,index位置的元素和后续的元素后移
  4. 在index位置插入元素
  5. size++
//index:数组下标,element:参数
public void add(int index, E element) {
    //检查插入索引是否越界
    rangeCheckForAdd(index);
    //确保内部容量,和上面一样
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //数组拷贝,将index位置的元素和后续的元素后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //在index位置插入元素
    elementData[index] = element;
    size++;
}
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3、set方法

用指定的元素替换此列表中指定位置的元素。

  1. 检查索引是否越界
  2. 获取原来位置的元素
  3. 将元素替换指定位置
  4. 返回原索引的元素
public E set(int index, E element) {
    //检查索引是否越界
    rangeCheck(index);
    //获取原来位置的元素
    E oldValue = elementData(index);
    //将元素替换指定位置
    elementData[index] = element;
    //返回原索引的元素
    return oldValue;
}

4、remove方法

  1. 检查索引是否越界
  2. 修改次数加1
  3. 获取原来位置的元素
  4. 判断index是否在有效元素中
  5. 如果有效,就将index+1和之后的元素前移一位
  6. 数组的最后一位置为null
  7. 返回原索引的元素
public E remove(int index) {
    //检查索引是否越界
    rangeCheck(index);
	//修改次数加1
    modCount++;
    //获取原来位置的元素
    E oldValue = elementData(index);
	//判断index是否在有效元素中
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //如果有效,就将index+1和之后的元素前移一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //数组的最后一位置为null
    elementData[--size] = null; // clear to let GC do its work
	//返回原索引的元素
    return oldValue;
}

指定元素删除

  • 遍历数组,无论元素是否为null,都获取到一个相对于的index,如果没有就返回false
  • 如果有就判断index是否在有效元素中
  • 如果有效,就将index+1和之后的元素前移一位
  • 数组的最后一位置为null
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、addAll方法

public boolean addAll(Collection<? extends E> c) {
    //将集合转为数组
    Object[] a = c.toArray();
    //获取插入数组长度
    int numNew = a.length;
    //检查数组长度时候需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //拷贝数组,添加在数组末尾
    System.arraycopy(a, 0, elementData, size, numNew);
    //数组长度+插入元素长度
    size += numNew;
    return numNew != 0;
}

ArrayList其他方法

1、clear方法

删除所有元素

  • 遍历置为null
public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

2、sublist方法

返回此列表中指定的 fromIndex (包括)和 toIndex之间的独占视图。

 public List<E> subList(int fromIndex, int toIndex) {
     	//索引越界检查
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
 }
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}
private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
	//返回数组大小
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

3、iterator方法

interator方法返回的是一个内部类,由于内部类的创建默认含有外部的this指针,所以这个内部类可以调用到外部类的属性。

public Iterator<E> iterator() {
    return new Itr();
}

4、trimToSize方法

  1. 修改次数加1

  2. 将elementData中空余的空间(包括null值)去除

    例如:数组长度为10,其中只有前三个元素有值,其他为空,那么调用该方法之后,数组的长度变为3.

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

5、contains方法

就是遍历,一一比较是否存在

public boolean contains(Object o) {
      return indexOf(o) >= 0;
}
 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;
 }

总结

  • ArrayList自己实现了序列化和反序列化的方法,因为它自己实现了 private void writeObject(java.io.ObjectOutputStream s)和 private void readObject(java.io.ObjectInputStream s) 方法
  • ArrayList基于数组方式实现,无容量的限制(会扩容)
  • 添加元素时可能要扩容(所以最好预判一下),删除元素时不会减少容量(若希望减少容量,trimToSize()),删除元素时,将删除掉的位置元素置为null,下次gc就会回收这些元素所占的内存空间。
  • 线程不安全
  • add(int index, E element):添加元素到数组中指定位置的时候,需要将该位置及其后边所有的元素都整块向后复制一位
  • get(int index):获取指定位置上的元素时,可以通过索引直接获取(O(1))
  • remove(Object o)需要遍历数组
  • remove(int index)不需要遍历数组,只需判断index是否符合条件即可,效率比remove(Object o)高
  • contains(E)需要遍历数组
  • 使用iterator遍历可能会引发多线程异常
13

评论区