精华内容
下载资源
问答
  • 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> cE类型下的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的扩容机制:

    1. 执行add方法
    2. 如果size == elementData.length 会触发扩容机制,执行grow()
    3. 执行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、总结

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,869
精华内容 2,747
关键字:

arraylist源码分析