精华内容
下载资源
问答
  • ArrayList源码解读

    2019-07-16 12:44:46
    ArrayList源码解读 由于本文内容较长,还请各位耐心阅读 ArrayList类图 ArrayList API 源码解读 public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, ...

    ArrayList源码解读

    由于本文内容较长,还请各位耐心阅读

    ArrayList类图

    在这里插入图片描述

    ArrayList API

    在这里插入图片描述在这里插入图片描述

    源码解读

    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;
    
    /**
     * 当new ArrayList();返回一个size()等于0的数据
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    /**
     * 一个空数组实例
     *   - 当用户没有指定 ArrayList 的容量时(即调用无参构造函数),
     *   返回的是该数组==>刚创建一个 ArrayList 时,其内数据量为 0。
     *   - 当用户第一次添加元素时,该数组将会扩容,
     *   变成默认容量为 10(DEFAULT_CAPACITY) 的一个数组===>通过ensureCapacityInternal() 实现
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * 存储ArrayList元素的数组缓冲区,arrayList的容量是这个数组缓冲区的长度,
     * 由于elementdata==defaultcapacity_empty_elementdata的空arraylist
     * 将在添加第一个元素时扩展为默认容量
     */
    transient Object[] elementData; // non-private to simplify nested class access
    
    /**
     * arratList的存储长度
     */
    private int size;
    
    /**
     * 创建一个指定长度的ArrayList();
     */
    public ArrayList(int initialCapacity) {
        //初始长度大于0,则创建指定长度大小
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //等于0,创建为空
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //小于0,抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }
    
    /**
     * 创建一个空的arrayList
     * 当第一次add()后,长度自动扩容为10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 创建一个Collection的ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        // 将其装换成Object[] toArray()
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 判断toArray()方法后,转换是否成功
            if (elementData.getClass() != Object[].class)
                // 若 c.toArray() 返回的数组类型不是 Object[],则利用 Arrays.copyOf();
                // 来构造一个大小为 size 的 Object[] 数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替换为空
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    
    /**
     * 去空后,得到数组实际长度
     */
    public void trimToSize() {
        //protected transient int modCount = 0;
        modCount++;
        /**
         * 实际长度 < 默认初始化长度
         */
        if (size < elementData.length) {
            /**
             * 如果实际长度等于0,长度为默认长度,
             * 如长度不等于0,则变为实际长度
             */
            elementData = (size == 0)
                    ? EMPTY_ELEMENTDATA
                    : Arrays.copyOf(elementData, size);
        }
    }
    
    /**
     * 指定扩容长度
     * @param   minCapacity  扩容长度
     */
    public void ensureCapacity(int minCapacity) {
        /**
         * 判断其长度是不是0,如果是,不进行扩容,否则扩容为10
         */
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                ? 0 : DEFAULT_CAPACITY;
        //若用户指定的长度大于最长扩容长度,选择用户指定的长度
        if (minCapacity > minExpand) {
            //调用内部方法
            ensureExplicitCapacity(minCapacity);
        }
    }
    
    // 新增时长度
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    /**
     *  指定的长度减去默认长度大于0
     * @param minCapacity  指定长度
     */
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //防止溢出
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /**
     * 数组缓冲区最大存储容量
     * 减8 以防止OutOfMemoryError(当该值 > VM 的限制时)
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    /**
     * 确保 ArrayList 至少能存储 minCapacity 个元素
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        // 防止溢出代码
        int oldCapacity = elementData.length;
        //扩容为原来的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 若 newCapacity 依旧小于 minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 若 newCapacity 大于最大存储容量,则进行大容量分配
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    //私有方法:大容量分配,最大分配 Integer.MAX_VALUE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }
    
    /**
     * 返回ArrayList实际存储的元素数量
     */
    public int size() {
        return size;
    }
    
    /**
     * ArrayList是否有元素
     */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 判断是否包含某元素
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    
    /**
     * 根据索引顺序查找
     */
    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;
    }
    
    /**
     * 逆向查找
     */
    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;
    }
    
    /**
     *  克隆
     */
    public Object clone() {
        try {
            /**
             * 克隆对象,并将实际长度进行复制
             */
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    
    /**
     * 将其转化为Object[]
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    
    /**
     * 返回一个ArratList 元素组成的数组
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // 新建复制
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        // 复制
        if (a.length > size)
            a[size] = null;
        return a;
    }
    
    // 访问指定下标的元素
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
    
    /**
     * 访问指定下标的元素,从0开始
     */
    public E get(int index) {
        rangeCheck(index);//判断访问下标是否越界
        return elementData(index);
    }
    
    /**
     * 设置指定小编元素的值
     */
    public E set(int index, E element) {
        rangeCheck(index);
        //获取旧值
        E oldValue = elementData(index);
        //替换
        elementData[index] = element;
        return oldValue;
    }
    
    /**
     * 新增元素
     * @param e
     * @return
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //元素位置
        elementData[size++] = e;
        return true;
    }
    
    /**
     * 指定下标位置新增
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);//判断是否越界
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        elementData[index] = element;
        size++;
    }
    
    /**
     * 移除指定位置元素
     */
    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;
    
        return oldValue;
    }
    
    /**
     * 指定元素移除
     */
    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;
    }
    
    /*
     * 快速删除第 index 个元素
     */
    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
    }
    
    /**
     * 清空
     */
    public void clear() {
        modCount++;
    
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
    
        size = 0;
    }
    
    /**
     * 新增Collection元素
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    /**
     * 指定位置,新增Collection元素
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
    
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
    
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                    numMoved);
    
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }
    
    /**
     * 移除list中 (fromIndex,toIndex) 的元素
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        //移动的数量
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                numMoved);
        //移动后的长度
        int newSize = size - (toIndex-fromIndex);
        //将移除后的滞空
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    
    /**
     * 判断下标与实际长度大小
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /**
     * 下标越界
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    /**
     * 异常返回,操作长度与实际长度
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    
    /**
     * 删除多少c
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
    
    /**
     * 批量移除
     */
    public boolean retainAll(Collection<?> c) {
        //是否空指针
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            if (r != size) {
                System.arraycopy(elementData, r,
                        elementData, w,
                        size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
    
    /**
     * 序列化方法
     */
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();
    
        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);
    
        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
    
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
    
    /**
     * 反序列化
     */
    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
            ensureCapacityInternal(size);
    
            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }
    
    /**
     * 返回从指定索引开始到结束的带有元素的list迭代器
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }
    
    /**
     * 返回从0索引开始到结束的带有元素的list迭代器
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }
    
    /**
     * 以一种合适的排序返回一个iterator到元素的结尾
     */
    public Iterator<E> iterator() {
        return new Itr();
    }
    

    希望对看到的小伙伴有所帮助

    展开全文
  • ArrayList 源码解读

    2017-09-24 21:22:00
    ArrayList 源码解读 基于JDk 1.7.0_80 public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable ArrayList的底层是使用数组实现...

    ArrayList 源码解读     基于JDk 1.7.0_80

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

    ArrayList的底层是使用数组实现的,因为数组的容量是固定的,要实现可变容量List,所以一定存在着容量检测,数组复制等方法。

    对象属性

        /**
         * 默认大小
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * 空对象数组 ,用来做比较
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * 存储数据的数组
         */
        private transient Object[] elementData;
    
        /**
         * 大小
         */
        private int size;

    构造方法

      /**
         * 指定大小*/
        public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }
    
        /**
         * 默认 
         */
        public ArrayList() {
            super();
            this.elementData = EMPTY_ELEMENTDATA;
        }
    
        /**
         * 传入一个Collection*/
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            size = elementData.length;
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }

    add 方法  

      public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
        // 在指定位置添加对象
        public void add(int index, E element) {
            // 判断添加的位置是否合理
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);
            elementData[index] = element;
            size++;
        }
        //判断是否是空数组
        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);
        }
        //增加容量
        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);
        }

    remove 方法

        /**
         * Removes the element at the specified position in this list.
         */
        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);
           //最后一位设为null     
            elementData[--size] = null; // clear to let GC do its work
            return oldValue;
        }
    
        /**
         * Removes the first occurrence of the specified element from this list,
         */
        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;
        }
    
        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
        }
    
       private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }            

    get方法

        public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }

    set方法 

        public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

    内部类Itr 实现了Iterator接口  ,实现了 next()   hasNext()  remove() 三个方法

    public Iterator<E> iterator() {
    return new Itr();
    }

    /**
    * An optimized version of AbstractList.Itr
    */
    private class Itr implements Iterator<E> {
    // 下一个返回的位置
    int cursor; // index of next element to return
    // 上次返回的位置
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
    return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
    throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
    throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
    }

    public void remove() {
    if (lastRet < 0)
    throw new IllegalStateException();
    checkForComodification();

    try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
    }
    }
       //当你在使用迭代器时,不能使用 使用 set add 等方法,改变 存储的数据
    final void checkForComodification() {
    if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
    }
    }

    ListItr 内部类

        


    private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { super(); cursor = index; } public boolean hasPrevious() { return cursor != 0; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor - 1; } @SuppressWarnings("unchecked") public E previous() { checkForComodification(); int i = cursor - 1; if (i < 0) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i; return (E) elementData[lastRet = i]; } public void set(E e) { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.set(lastRet, e); } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } public void add(E e) { checkForComodification(); try { int i = cursor; ArrayList.this.add(i, e); cursor = i + 1; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }

     

    转载于:https://www.cnblogs.com/alway-july/p/7583495.html

    展开全文
  • ArrayList 源码 解读

    2020-03-27 15:39:16
    就是new一个初始容量为10的ArrayList,之后向里面加入2个元素,然后因为初始容量为10,所以现在的数组容量为10,但我们只向 arraylist 里面 add了两个元素,size为2,也就是说这个方法将elementData的数组设置为...

    目录

    ArrayList简介

    trimToSize()删除多余容量

    ensureCapacity(int minCapacity) 对底层扩容

    EMPTY_ELEMENTDATA 空元素以及 默认 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是 {}

    transient Object[] elementData

    isEmpty() 判空

    contains(Object o) 判断是否存在元素

    indexOf(Object o) 获取元素坐标位置

    lastIndexOf(Object o) 元素最后索引位置

    clone()克隆


    ArrayList简介

    实现了接口List,List接口继承了Collection接口。Collection是所有集合类的父类。ArrayList使用非常广泛,不论是数据库表查询,excel导入解析,还是网站数据爬取都需要使用到

    ArrayList非线程安全,底层是一个Object[],添加到ArrayList中的数据保存在了elementData属性中。

    • 当调用new ArrayList<>()时,将一个空数组{}赋值给了elementData,这个时候集合的长度size为默认长度0;

    add()添加

    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

    ensureCapacityInternal 用来确保容量。容量如果不够,那么进行扩容。

    向数组elementData中插入数据。

    add(int index, E element) 按照下标添加数据

    public void add(int index, E element) {
            rangeCheckForAdd(index);

            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }

    rangeCheckForAdd首先进行下标越界检查。看 index 是否越界,

    ensureCapacityInternal 确保容量

    System.arraycopy从指定的源数组(从指定位置开始)将数组复制到目标数组的指定位置。

    remove(int index) 按照下标移除

    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; // clear to let GC do its work

            return oldValue;
        }

    首先进行rangeCheck 判断是不是 IndexOutOfBoundsException 下标越界

    然后用 oldValue 来保存索引处的值

    numMoved表示有多少个元素需要移动,或者说元素一共要移动多少步。如果移动步数大于0,则将index之后的元素前移。然后最后一个数组空间设置为null,然后让GC回收它。

    remove(Object o) 按照元素移除

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

    寻找元素坐标

    如果 元素为 null 则需要按照 == 进行比较查询并删除,如果 元素不为空 则需要按照 equals 来进行查询删除

    然后调用fastRemove (int index)

    fastRemove (int index) (快速删除)跳过边界检查 且不返回已删除值 的私有删除方法。

    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
        }

    和上面的按照 下标 删除 基本一样。只是不需要进行下标越界 检查 以及 不返回 需要删除的 元素值

    trimToSize()删除多余容量

    判断size是不是为0。为0的话就给elementData 一个 空的 元素 数据 {}

    就是new一个初始容量为10的ArrayList,之后向里面加入2个元素,然后因为初始容量为10,所以现在的数组容量为10,但我们只向 arraylist 里面 add了两个元素,size为2,也就是说这个方法将elementData的数组设置为ArrayList实际的容量,动态增长的多余容量被删除了。

    ensureCapacity(int minCapacity) 对底层扩容

    每次扩容 1.5倍 比如 你插入33个数据。那么扩容到 49 (33*1.5=49.5 ;10个的话就扩容到15)

    public void ensureCapacity(int minCapacity) {
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }

    any size if not default element table(任何大小(如果不是默认元素表)) minExpand = 0

    larger than default for default empty table.It's already supposed to be at default size(大于默认空表的默认值。它已经被假定为默认大小)

    EMPTY_ELEMENTDATA 空元素以及 默认 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 都是 {}

    transient Object[] elementData

    数组被定义为transient

    假如elementData的长度为10,而其中只有5个元素,那么在序列化的时候只需要存储5个元素,而数组中后面5个元素是不需要存储的。于是将elementData定义为transient,避免了Java自带的序列化机制,并定义了两个方法,实现了自己可控制的序列化操作。

    isEmpty() 判空

    public boolean isEmpty() {
                return size == 0;
           }

    contains(Object o) 判断是否存在元素

    根据元素坐标位置来判断,位置大于等于0存在,小于0不存在

    public boolean contains(Object o) {
              return indexOf(o) >= 0;
           }

    indexOf(Object o) 获取元素坐标位置

    分为 null 和 不为 null 进行循环 判断

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

    lastIndexOf(Object o) 元素最后索引位置

    反向 indexOf 操作。由i++ 改为 i--

    clone()克隆

    为什么出现克隆呢?如果你 用 list1 = list 2; 此时,其实只存在一个list 列表。 list1和list2 都是指向这个list。如果list1改变。那么list2也会改变。所以需要克隆。

    利用System.arraycopy() 进行数组的复制

    public static native void arraycopy()

    Java数组的复制操作可以分为深度复制和浅度复制,简单来说深度复制,可以将对象的值和对象的内容复制;浅复制是指对对象引用的复制。

    System中提供了一个native静态方法arraycopy(),可以使用这个方法来实现数组之间的复制。对于一维数组来说,这种复制属性值传递,修改副本不会影响原来的值对于二维或者一维数组中存放的是对象时,复制结果是一维的引用变量传递给副本的一维数组,修改副本时,会影响原来的数组。

    其实没有二维数组的概念,平常实现的二维数组只是元素是一维数组的一维数组,而数组也是引用类型,继承自Object类。数组是new出来的。这些性质也就导致arraycopy()二维数组时出现的问题。 

    展开全文
  • Arraylist源码解读

    2020-09-23 15:57:24
    Arraylist 成员变量 /** * Default initial capacity. * 默认初始容量10。 */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. * 用于空实例...

    Arraylist

    在这里插入图片描述

    成员变量

    /**
     * Default initial capacity.
     * 默认初始容量10。
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * Shared empty array instance used for empty instances.
     * 用于空实例的共享空数组实例。
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    /**
     * 用于默认大小的空实例的共享空数组实例。我们将其与EMPTY_ELEMENTDATA区分开来,
     * 以知道在添加第一个元素时要扩容多少。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * 存储ArrayList元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。
     * 任何空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
     * 将在添加第一个元素时扩展到默认容量。
     */ 
    transient Object[] elementData; // non-private to simplify nested class access
    
    /**
     * ArrayList的大小(它包含的元素数)。
     */
    private int size;
    

    构造方法

    1、带参构造,即List list = new ArrayList(1);

    /**
     * Constructs an empty list with the specified initial capacity.
     * 构造具有指定初始容量的空列表。
     * @param  initialCapacity  the initial capacity of the list 初始大小
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     * 如果initialCapacity为负数,报错IllegalArgumentException
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//如果指定初始大小大于0,elementData为指定大小的数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//如果指定初始大小等于0,elementData为空数组实例
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//如果为负数,报错
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    

    2、无参构造,即List list = new ArrayList();

    /**
     * Constructs an empty list with an initial capacity of ten.
     * 构造初始容量为10的空列表
     * 源码注释是这么说,但是new的时候容量还是0,在add的时候创建容量为10的列表
     */
    public ArrayList() {
    	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    3、参数为集合的构造

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        //toArray()返回一个新的数组,包含c所有元素,顺序为参数原始顺序
        elementData = c.toArray();
        //如果size不为0
        if ((size = elementData.length) != 0) {
        	// c.toArray might (incorrectly) not return Object[] (see 6260652)
            // c.toArray可能(错误地)不返回Object[](参见6260652)
            if (elementData.getClass() != Object[].class)
                //转成Object[]
            	elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            //size为0,则elementData为空数组实例
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    
    /**
     * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this list in
     *         proper sequence
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    
    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) {
        @SuppressWarnings("unchecked")
        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;
    }
    

    方法

    add(E e)

     /**
      * 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;
     }
    
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //这里主要是判断是否是以无参构造创建的list,无参构造创建的list默认大小10,拿默认大小跟所需最小容量比较,取大值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//记录操作次数
    
        // overflow-conscious code
        //如果所需的最小容量比数组长度要大,则需要进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /**
     * 要分配的数组的最大大小。一些vm在数组中保留一些头字。尝试分配较大的数组可能会导致
     * OutOfMemoryError:请求的数组大小超过了虚拟机限制
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    /**
     * 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;//原数组大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容1.5倍后的容量
        //如果扩容后的大小比所需最小容量(minCapacity)要小,list新的大小等于所需最小容量(minCapacity)
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果扩容后的大小比MAX_ARRAY_SIZE还要大,那么扩容后的大小为Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //扩容以后要进行全量copy
        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;
    }
    

    add(int index, E element)

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     * 在list指定位置插入指定元素,将当前位于该位置的元素和任何后续元素向右移动(如果有的话)
     *
     * @param index index at which the specified element is to be inserted 要插入指定元素的索引
     * @param element element to be inserted 要插入的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index); //检查索引
    
        //这里跟上面add方法一样,判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //copy,从elementData索引为index开始copy,copy到目标数组elementData,目标数组索引为index + 1开始,要copy的元素个数为size - index
        System.arraycopy(elementData, index, elementData, index + 1,
        			size - index);
        //指定索引位置元素为element
        elementData[index] = element;
        //list大小+1,所包含的元素数
        size++;
    }
    
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    

    addAll(Collection<? extends E> c)

    public boolean addAll(Collection<? extends E> c) {
    	//返回一个新数组,包含参数所有元素,且顺序一样
        Object[] a = c.toArray();
        int numNew = a.length;
        //判断是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //copy,源数组a,从0开始copy,目标数组elementData,从size开始,即最后面,copy大小为传入数组大小
        System.arraycopy(a, 0, elementData, size, numNew);
        //更新size
        size += numNew;
        return numNew != 0;
    }
    

    addAll(int index, Collection<? extends E> c)

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);//检查索引
    
        //返回一个新数组,包含参数所有元素,且顺序一样
        Object[] a = c.toArray();
        int numNew = a.length;
        //判断是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
    
        int numMoved = size - index;
        //如果index在数组中间,先将index后面的元素copy到index + numNew的位置
        if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
        numMoved);
    
        //copy,源数组a,从0开始copy,目标数组elementData,从index开始,copy大小为传入数组大小
        System.arraycopy(a, 0, elementData, index, numNew);
        //更新size
        size += numNew;
        return numNew != 0;
    }
    

    remove(int index)

    public E remove(int index) {
        rangeCheck(index);//检查索引
    
        modCount++;//记录操作次数
        E oldValue = elementData(index); //得到指定索引的值
    
        int numMoved = size - index - 1;
        //如果index在数组中间,copy,源数组elementData,从index+1开始copy,目标数组elementData,从index开始,copy大小为numMoved
        if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
        //往前移一位后最后一个置为null
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }
    
    @SuppressWarnings("unchecked")
    E elementData(int index) {
    	return (E) elementData[index];
    }
    

    remove(Object o)

    //这个就很容易看懂了,如果o为null,循环拿到索引,不为空也是循环拿到索引,fastRemove里逻辑跟remove里一样了
    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;
    }
    
    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
    }
    

    removeAll(Collection<?> c)

    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c); //判断c是否为空,为空报空指针
        return batchRemove(c, false);
    }
    
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData; //拿到数组
        int r = 0, w = 0;
        boolean modified = false;
        try {
            //如果contains不报错,正常执行完循环,这步操作将把需要移除的数据都替换掉,不需要移除的数据前移。
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            //这个if作用主要是防止contains报错,没有执行完循环 r!=size
            if (r != size) {
                //这一步copy为,从源数组elementData索引为r开始copy(即索引r以及之后的元素还没有执行过替换,因为到r contains报错了),copy到目标数组elementData索引为w的后面(即w之前的已经执行过替换了)
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                //最后将前移后,索引在w及后面的元素置null,也就是元素前移后,后面空出来的位置
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                //修改次数为size减去新数组大小
                modCount += size - w;
                //更新数组大小
                size = w;
                //操作成功,true
                modified = true;
            }
        }
        return modified;
    }
    
    说明:
    size=8
    原数组:["张三:0","李四:1","王五:2","赵六:3","麻子:4","小明:5","小红:6","露西:7"] elementData
    需要移除数组:["麻子","露西"] c
    
    说明:w++ 先用再加,即第一次循环w=0,elementData[w++]意思为:elementData[0]然后再w+1
        
                                        
    循环次数 r值	c.contains值 	if判断值 w值循环前 elementData[w++] = elementData[r] w值循环后	
    1       0   false		 	true	0	     elementData[0]=elementData[0]		1
    2		1   false		 	true	1     	 elementData[1]=elementData[1]		2
    3		2   false		 	true	2    	 elementData[2]=elementData[2]		3
    4		3   false		 	true	3    	 elementData[3]=elementData[3]		4
    5		4   true         	false    
    6		5	false		 	true   	4	   	 elementData[4]=elementData[5]		5
    7		6	false		 	true   	5	   	 elementData[5]=elementData[6]		6
    8		7	true		 	false
        	8
    r=8,w6
    
    循环执行完之后,再对比一下两个数组的数据,
    替换后数组:
    ["张三","李四","王五","赵六","小明","小红","小红","露西"]
    原始数组:
    ["张三","李四","王五","赵六","麻子","小明","小红","露西"]
    可以看出,将需要移除的元素替换后,后面的元素向前移了一位,
    所以后面finally里的循环就是将小红,露西置空,成功remove。
    
    另外一种情况,如果第六次循环contains报错,执行完第一个if后数组为:
                                                       5
    第六次替换报错的数组:["张三","李四","王五","赵六","小明","小明","小红","露西"]
    未遍历到的:"小明","小红","露西"
    已遍历的:"张三","李四","王五","赵六"
    
    执行完第一个if后:["张三","李四","王五","赵六","小明","小红","露西",null]
    这样就确保了异常抛出前的部分可以完成期望的操作,而未被遍历的部分接到已经遍历过的后面
    此时 r=5 w=4
        w += size - r=7
            
    

    clear()

    //这个不说了,自己看
    public void clear() {
            modCount++;
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }
    

    retainAll(Collection<?> c)

    # 跟removeAll的区别就在于第二个参数是true了,remove是删除指定的集合,retainAll就是删除不在指定集合中的元素
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    

    set(int index, E element)

    public E set(int index, E element) {
        rangeCheck(index);//检查索引
    
        E oldValue = elementData(index);//拿到旧值
        elementData[index] = element;//将指定下标index的值替换为element
        return oldValue;//返回旧值
    }
    

    indexOf(Object o)

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

    lastIndexOf(Object o)

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

    扩容后的元素copy

    /** 从指定的源数组(从指定位置开始)将数组复制到目标数组的指定位置。包含起始位
     * @param      src      the source array.源数组
     * @param      srcPos   starting position in the source array.源数组中的起始位置。
     * @param      dest     the destination array.目标数组。
     * @param      destPos  starting position in the destination data.目标数据中的起始位置。
     * @param      length   the number of array elements to be copied.要复制的数组元素数。
     */
    System.arraycopy(Object src, int  srcPos, 
    				  Object dest, int destPos, int length);
    

    ArrayList和Vector的区别

    Vector,它是ArrayList的线程安全版本,其实现90%和ArrayList都完全一样,区别在于:

    1、Vector是线程安全的,ArrayList是线程非安全的

    2、Vector可以指定增长因子,如果该增长因子指定了,那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子;如果不指定增长因子,那么就给原数组大小*2,源代码是这样的:

    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                         capacityIncrement : oldCapacity);
    

    总结

    优缺点

    1. ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快。
    2. ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已。
    3. 删除元素的时候,涉及到一次元素复制,如果要复制的元素很多,那么就会比较耗费性能
    4. 插入元素的时候,涉及到一次元素复制,如果要复制的元素很多,那么就会比较耗费性能

    特点:允许元素为null,允许重复元素,有序,非线程安全。

    展开全文
  • arraylist源码解读

    2019-12-10 21:51:41
    本次源码解析,只暂时解析构造函数,add,remove方法。其余的等有时间再做补充 三种初始化方式 无参数 public ArrayList() { 无参数时将会初始化为一个空的数组 this.elementData = ...

空空如也

空空如也

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

arraylist源码解读