arraylist源码分析

ArrayList源码分析
2019-03-30 11:33:41
根据arraylist源码分析，自己编写了一个类似于arraylist集合的代码
收起

ArrayList 源码分析

2017-06-28 11:49:50

ArrayList 源码分析

首先看下ArrayList的关系图 


ArrayList 继承自AbstractList,实现了List 、RandomAccess、Cloneable、Serializable接口 

点开List接口，你会发现我们常用的方法基本上都在这里，当然，实现都是在ArrayList当中。 


再回到ArrayList的源码，我们会发现ArrayList的几大特点：

ArrayList维护了一个动态的数组，可以增加或缩减其长度。
ArrayList 是线性不安全的，在多线程中操作一个ArrayList需要手动保证数据的同步。
每个ArrayList实例维护了一个capacity的属性，顾名思义，就是集合的容量，且其值会随着数据的变化增长或者衰减。

  ArrayList的两大精华
  
  扩容
  Iterator
  
首先看下这几个属性


/**
 * 默认的容器大小
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 *一个空的数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 在这里要清楚transient 的含义，被该属性修饰的变量不会被序列化
 */
transient Object[] elementData;

/**
 * 元素长度
 *
 */
private int size;

//这个属性来自AbstrctList  代表的含义是每当ArrayList的结构发生变化的时候 该变量+1；该属性同样使用了transient 修饰，因为没必要持久化。
protected transient int modCount = 0;


大精华之一：扩容：

最常见的add（）方法

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    //扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //赋值
    elementData[size++] = e;
    return true;
}

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    //最小长度 如果数组不为空 最小即为0 否则为默认的10
    int minExpand = (elementData != EMPTY_ELEMENTDATA)
        // any size if real element table
        ? 0
        // larger than default for empty table. It's already supposed to be
        // at default size.
        : DEFAULT_CAPACITY;
    //如果需要的长度  即目标长度大于最小长度 说明需要扩容
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

private void ensureCapacityInternal(int minCapacity) {
    //如果数组为空 最小容量取下面二者最大值
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {

    modCount++;

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

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */

//重点来了 此乃精华之一： 扩容
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);
}

//附带下copy方法  
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}


public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    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;
}


其实扩容也就在grow（）方法中的几行代码 主要是对集合长度的控制。


大精华之二 Iterator： 

最常见的listIterator（）方法

 /**
 * Returns a list iterator over the elements in this list (in proper
 * sequence), starting at the specified position in the list.
 * The specified index indicates the first element that would be
 * returned by an initial call to {@link ListIterator#next next}.
 * An initial call to {@link ListIterator#previous previous} would
 * return the element with the specified index minus one.
 *
 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}


ListItr是个什么鬼？原来是一个内部类，实现了ListIterator接口

private class ListItr extends Itr implements ListIterator<E> {
    //把坐标传递进来
    ListItr(int index) {
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }

    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public int nextIndex() {
        return cursor;
    }

    public int previousIndex() {
        return cursor-1;
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            AbstractList.this.add(i, e);
            lastRet = -1;
            cursor = i + 1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

//看完之后你会发现确实没什么东西 但是Iterator这个东西在很多地方都有用到，这里就显现出来接口的强大之处。




总结

看完ArrayList的源码之后，对ArrayList数据存储有了更深的理解，然而它的性能如何呢，要知道扩容和写数据都是需要时间的，经过测试，ArrayList在遍历和普通插入（add(object)）的性能上都优于LinkedList。但是LinkedList在首尾进行操作的性能上明显优于ArrayList.

收起

展开全文

arraylist源码分析

2021-03-23 16:30:12

ArrayList源码分析 1、成员变量 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long ...

ArrayList源码分析
1、成员变量
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, 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;
	
    // ....
}


serialVersionUID：序列化用的，暂时不清楚
DEFAULT_CAPACITY：默认容量为10
EMPTY_ELEMENTDATA：空数组，有参构造函数为0时用的
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：空数组，无参构造函数用的
elementData：ArrayList集合存放元素的位置
size：集合中元素占据的大小，注意不是elementData.legnth

2、构造方法
2.1、无参构造
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

方法说明：将elementData设置为空数组
2.2、有参构造1
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);
    }
}

参数说明：
initialCapacity：arraylist容量初始值
方法说明：
如果初始值大于0，将elementData设置为一个该长度的数组
如果为0，也是将elementData设置为空数组
如果小于0抛出异常
2.3、有参构造2
public ArrayList(Collection<? extends E> c) {
    this.elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

参数说明：
Collection<? extends E> c： E类型下的Collection的实现类集合
方法说明：
如果该集合中元素不是Object[] 集合就转化为Object[]集合
3、自动扩容
private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = 
            ArraysSupport.newLength(oldCapacity,
                                    minCapacity - oldCapacity,
                                    oldCapacity >> 1          
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[
            Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

private Object[] grow() {
    return grow(size + 1);
}

ArrayList的扩容机制：

执行add方法
如果size == elementData.length 会触发扩容机制，执行grow()
执行grow(size + 1)

第2行：首先拿到原来的容量
第3行：如果不是第一次添加

设置新的容量为原来的1.5倍，并且将复制数组到新数组里面


第9行：如果是第一次添加

执行初始扩容，将elementData设置为初始值





4、增删改查
4.1、add
public boolean add(E e) {	// 向最后添加元素
    modCount++;					
    add(e, elementData, size);	// 调用下面方法
    return true;
}

private void add(E e, Object[] elementData, int s){ // 检查是否要扩容
    if (s == elementData.length)	
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

public void add(int index, E element) {	// 向指定位置添加元素
    rangeCheckForAdd(index);	
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length) {
        //扩容
        elementData = grow();
    }
    
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);	
    elementData[index] = element;
    size = s + 1;
}

4.2、remove
public E remove(int index) {	// 指定位置删除元素
    // 检查索引是否不在范围
    Objects.checkIndex(index, size);
    
    // 新的指针指向elementData
    final Object[] es = elementData;
    @SuppressWarnings("unchecked") 
    E oldValue = (E) es[index];
    // 进行删除操作
    fastRemove(es, index);
	// 返回删除的元素
    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize = size - 1;	// newSize 原来size - 1 
    if (newSize > i)				// 如果删除的不是最后一个元素
        System.arraycopy(es, i + 1, es, i, newSize - i);
    size = newSize;
    // 这里不管删除的是不是最后一个元素，都将原数组最后一个置为null
    // 如果是删除的最后一个, 上一个if不执行，提高效率
    es[size] = null;	
}

4.3、set
将指定索引的元素改为新的值， 返回老的值
public E set(int index, E element) {
    Objects.checkIndex(index, size);
    checkForComodification();
    E oldValue = root.elementData(offset + index);
    root.elementData[offset + index] = element;
    return oldValue;
}

4.4、get
得到索引为index的元素
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

5、总结


ArrayList底层实现是数组。
当使用无参数构造函数创建ArrayList对象时，ArrayList对象中的数组初始长度为0（是一个空数组）。
ArrayList的扩容策略是每次都增加当前数组长度的一半（非固定分配）。
ArrayList的扩容方式是直接创建一个新的数组，并将数据拷贝到新数组中。

收起

展开全文