ArrayList源码

我们知道ArrayList是List接口的实现类,List又是继承Collection接口的,因此,先看下这两个接口里面有哪些方法.

//没写完
public interface Collection<E>{

        int size();

        boolean isEmpty();

        boolean contains(Object o);

        Object[] toArray();

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(Collection<?> c);

        boolean addAll(Collection<? extends E> c);

        boolean removeAll(Collection<?> c);

        void clear();
}

List接口在Collection的基础上新加的方法有:

E get(int index);
//set一个element到index位置上
E set(int index,E element);
//找到o第一次出现的位置,不存在的话返回-1
int indexOf(Object o)
//最后一次出现的位置
int lastIdexOf(Object o);
//子list
List<E> subList(int fromIndex, int toIndex);

可以看出来不管是ArrayList还是LinkedList都可以通过get(index)方法来遍历,LInkedList的get实现还是通过next来做的.并且都可以通过add来添加,remove来移除.

再来看一下ArrayList的实现方式:

public class ArrayList extends AbstractList implements List RandomAccess, Cloneable, java.io.Serializable

AbstractList是一个实现了List接口的抽象类实现一些基本的功能,具体参见抽象类的功能,实现了RandomAccess(随机访问),Cloneable,Serializable(序列化)的接口,序列化是网络传输或者保存到本地的需要,对于不想序列化的参数可以用transient或者readObject,writeObject来实现,后面会讲到.

ArrayList底层是通过数组来实现的,默认的数组大小为10.

private static final int DEFAULT_CAPACITY = 10;

通过elementData数组来存放数据,因为elementData在超过threshold时会扩容,因此不需要将所有的都序列化,因此加了个transient关键字.

transient Object[] elementData;

get方法:

public E get(int index) {
    //先判断输入index是否有效
      rangeCheck(index);
      //直接返回对应下标的值
      return elementData(index);
  }

add方法:

public boolean add(E e) {
         //保证容量
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

remove 某个index的方法:

public E remove(int index) {
        //
        rangeCheck(index);
        //记录数组被修改的次数, 修改数组可能会对正在进行的迭代造成不正确的结果
        modCount++;
        E oldValue = elementData(index);
        //需要移动的数据的总数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            /**arrayCopy方法:
            **第一个elementData:源数组
            **index+1:开始的位置
            **第二个elementData:目标数组
            **index:开始的位置
            **numMoved:总共需要复制多少个
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
          //将最后一个设置为nul,让GC回收
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

remove某个Object的方法:逻辑很简单,遍历数组找到与o相同的,然后调用fastRemove方法

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

clear方法:

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

    size = 0;
}

readObject方法:

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

ArrayList的扩容机制: 在add操作时,有个判断当前容量的ensureCapacityInternal方法,首先会把modCount++,然后判断 minCapcity(传过来的是size+1)比数组的长度大时扩容

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

很明显可以看出,扩容是按照1.5倍进行扩容.

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

本网站发布的一切文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。如有侵权请联系邮箱:1194325527@qq.com处理

目录
×

给作者杯卡布奇诺

github