精华内容
参与话题
问答
  • 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源码分析

    2017-06-28 09:23:23
    ArrayList 源码分析

    常用集合类

    1. ArrayList 源码分析

    ArrayList内部使用的是一个数组来保存数据. 主要是利用 Arrays.copyOf() 方法来动态扩展数组长度. ArrayList还是相对简单的.

    1.1 ArrayList原理

    ArrayList内部使用了一个 Object[] 来存储数据。

    // 存储数据的数组
    private transient Object[] elementData;

    ArrayList初始化时可以指定数组大小

    // 指定数组大小,初始化ArrayList.
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    如果不指定大小则, 默认是空数组

    // 默认空数组定义
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 无参数构造方法
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    1.2 ArrayList 优化函数.

    当不在添加元素时, 将剩余的空间释放掉.

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

    1.3 增加元素API

    默认情况下元素添加到最后一个元素的后面

    public boolean add(E e) {
        // 设置数组长度, 确保数组够长.如果不够会自动增加长度.
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // size是当前元素个数. 下面这句代码是将元素添加到最后.
        elementData[size++] = e;
        return true;
    }

    下面来看下 ensureCapacityInternal 更新数组实际长度的方法.

    private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // 判断当前数组长度是否小于数组长度. 如果不小于则增加长度.
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    下面来看下 grow 方法源码.

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

    上面的代码非常简单首先将数组长度增加2倍, 如果还是不够长度, 则直接将长度增加到minCapacity.之后还要比较此时长度是否超过最大长度.处理过程如下

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    在指定位置添加元素API

    public void add(int index, E element) {
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将要插入位置以后的元素, 整体后移.
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在index位置插入.
        elementData[index] = element;
        size++;
    }

    1.4 删除元素API

    remove(index)

    public E remove(int index) {
        rangeCheck(index);
    
        modCount++;
        // 获取要删除元素值.
        E oldValue = elementData(index);
        // 获取要删除元素的个数.
        int numMoved = size - index - 1;
        // 将index 之后的元素前移
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 将最后一个位置设置为null
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

    ArrayList的结构相对简单.也容易理解.

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 5,318
精华内容 2,127
关键字:

arraylist源码分析