Java教程

ArrayList源码深度解读

本文主要是介绍ArrayList源码深度解读,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

我们可以看到它继承了AbstractList并且实现了List,RandomAccess(标识为可随机读取), Cloneable(标识为可克隆), java.io.Serializable(标识为可序列化)。

变量

 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; //数组长度

构造函数

//赋予ArrayList初始容量
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) { //如果大于0
            this.elementData = new Object[initialCapacity];
            // 创建一个大小为initialCapacity的数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA; //创建一个空数组
        } else {
            //抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//创建一个空数组
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//将传入的值变为数组并赋值给elementData
        if ((size = elementData.length) != 0) { //如果数组长度不为0
            // 如果elementData的类不是Object
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);//复制
        } else {
            // 变为空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

常用的方法

add增

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保空间够
        elementData[size++] = e;//将当前数组的下一个(也就是数组尾部)把当前元素加上
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);//第一次添加此语句成立返回10
        }
        return minCapacity;
    }

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

        // 如果容量不够,则调用grow扩容
        if (minCapacity - elementData.length > 0)
            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)//判断新容量和minCapacity的大小
            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) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
//在对应位置上添加元素   
 public void add(int index, E element) {
        rangeCheckForAdd(index); //检查是否越界

        ensureCapacityInternal(size + 1);  // 检查容量够不够用,参考上边那个
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); //调用本地方法拷贝
        elementData[index] = element; //把数组中第index个元素换为element
        size++;
    }
//越界或者index<0则抛出异常
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

remove删

    
    public E remove(int index) {
        rangeCheck(index);//越界检查

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

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//拷贝移除后的数组
        elementData[--size] = null; // 置空触发GC回收

        return oldValue;
    }
    //越界就抛出异常
   private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    //查找元素
    E elementData(int index) {
        return (E) elementData[index];
    }
//删除指定元素,和上边类似,不再赘述
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;
    }
//如果list中存在要移除的元素
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
    }

set改

 public E set(int index, E element) {
        rangeCheck(index);//越界检查

        E oldValue = elementData(index); //拿到旧元素
        elementData[index] = element;//数组中替换
        return oldValue;
    }

get查

public E get(int index) {
        rangeCheck(index); //越界检查

        return elementData(index); //从数组中取值
    }

indexOf

//查找某个元素的下标
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; //如果不存在就返回-1
    }

lastIndexOf

//查找元素最后出现的位置
public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--) //逆序查找
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--) //逆序查找
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

clear

public void clear() {
        modCount++;

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

        size = 0;
    }

我们需要记住的点:

  • 操作ArrayList本质就是操作Array
  • 它增删慢是因为,增删元素坐标之后的元素都要整体移动
  • 我用的jdk1.8,调用无参构造之后并未初始化容量,在第一次调用add之后将容量变为10,容量不足时,扩充为原来的1.5倍。

个人理解,如有不正确的地方请指出

这篇关于ArrayList源码深度解读的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!