博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
JDK 1.8 ArrayList源码解读
阅读量:5801 次
发布时间:2019-06-18

本文共 14317 字,大约阅读时间需要 47 分钟。

前言 System.arraycopy的使用

/*** src被拷贝数组* srcPos开始下标* dest  被插入目标数组* destPos被插入目标数组下标* length 拷贝和复制的长度*/     public static void arraycopy(Object src,                             int srcPos,                             Object dest,                             int destPos,                             int length);                             /*//eg:elementData[a,b]      a[0,1,2]      System.arraycopy(elementData, 0, a, 0, 2);     返回[a,b,2]*/

全局变量

/**   * Shared empty array instance used for empty instances.   默认的空数组,用于构造函数或者重置ArrayList   */  private static final Object[] EMPTY_ELEMENTDATA = {};/**   * Shared empty array instance used for default sized empty instances. We   * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when   * first element is added.   无参构造函数,带默认容量10,时使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA   */  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};       /**   * The array buffer into which the elements of the ArrayList are stored.   * The capacity of the ArrayList is the length of this array buffer. Any   * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA   * will be expanded to DEFAULT_CAPACITY when the first element is added.   实际保存ArrrayList中元素的数组   ArrrayList当前容量(capacity)即此数组的长度   所有空的ArrayList都符合elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA   但当有元素插入,ArrayList将被扩充至DEFAULT_CAPACITY,即10      */  transient Object[] elementData; // non-private to simplify nested class access/**   * The size of the ArrayList (the number of elements it contains).   *当前ArrayList元素总数   * @serial   */  private int size;     /**   * The maximum size of array to allocate.   * Some VMs reserve some header words in an array.   * Attempts to allocate larger arrays may result in   * OutOfMemoryError: Requested array size exceeds VM limit   */  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

* 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     */    public ArrayList(int initialCapacity) {        if (initialCapacity > 0) {//明确默认长度的ArayList            this.elementData = new Object[initialCapacity];        } else if (initialCapacity == 0) {//否则用EMPTY_ELEMENTDATAz作为存放元素的数组elementData            this.elementData = EMPTY_ELEMENTDATA;        } else {            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);        }    }        /**     * Constructs an empty list with an initial capacity of ten.     无参构造函数,带默认容量10,时使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA     */    public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }            /**     * 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     Collection容器对象作参的构造函数     */    public ArrayList(Collection
c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[](see 6260652) //非Object[]数组即可进行数组复制(Object[]在数组复制时可能错误地不返回Object[] ) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }

trimToSize瘦身

/*ArrayList扩容是1.5+1的,此方法用于瘦身ArrayList,使用elementData的长度等于size*/ public void trimToSize() {        modCount++;        if (size < elementData.length) {            elementData = (size == 0)              ? EMPTY_ELEMENTDATA              : Arrays.copyOf(elementData, size);        }    }

ensureCapacity判断(确保)ArrayLit容量大于minCapacity,否则扩容

public void ensureCapacity(int minCapacity) {         //DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示ArrayList为默认容量10        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;        //minExpand        if (minCapacity > minExpand) {//明确进行扩容            ensureExplicitCapacity(minCapacity);        }    }

minCapacity如果超过DEFAULT_CAPACITY(10)即进行扩容

private void ensureCapacityInternal(int minCapacity) {        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);        }        ensureExplicitCapacity(minCapacity);    }

ensureExplicitCapacity明确扩容

private void ensureExplicitCapacity(int minCapacity) {        modCount++;        // overflow-conscious code        //大于当前数组容量即扩容        if (minCapacity - elementData.length > 0)            grow(minCapacity);    }

扩容实现grow

/**     * 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        //oldCapacit原容量        int oldCapacity = elementData.length;        //扩容个1.5倍(其实不是1.5,只是二进制右移1位 oldCapacity >> 1)        int newCapacity = oldCapacity + (oldCapacity >> 1);        //如果小于minCapacity(最小容量)则已minCapacity为准        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        //newCapacity比最大长度还大,则以Integer.MAX_VALUE作为容量        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);    }

hugeCapacity判断最小容量

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

contains ArrayList是否包含此元素

public boolean contains(Object o) {        //该元素下标大于等于0即包含        return indexOf(o) >= 0;    }

迭代elementData判断是否有此元素,有则直接返回下标

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

反向迭代elementData判断是否有此元素,有则直接返回下标

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

重写父类clone(),实现深度克隆

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

arrayList转成数组

//其实就是把elementData拷贝出来而已public Object[] toArray() {        return Arrays.copyOf(elementData, size);    }
//将ArrayList元素以T类型数组返回 public 
T[] toArray(T[] a) { //目标数组长度小于当前ArrayList size则直接拷贝elementData返回 if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); //否则使用System.arraycopy返回 //eg:elementData[a,b] a[0,1,2] 返回[a,b,2] System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }

elementData[i]下标所在元素,没做,判断容易下标越界

@SuppressWarnings("unchecked")    E elementData(int index) {        return (E) elementData[index];    }

返回下标元素

public E get(int index) {        rangeCheck(index);//检查是否超出size        return elementData(index);    }

设置下标元素,并返回原值

public E set(int index, E element) {        rangeCheck(index); //检查是否超出size        E oldValue = elementData(index);        elementData[index] = element;        return oldValue;    }

添加元素,先判断是否需要扩容再添加

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

指定下标插入元素

public void add(int index, E element) {        rangeCheckForAdd(index);//检查是否超出size        ensureCapacityInternal(size + 1);  // Increments modCount!!扩容        //拷贝数组,elementDatazai在index处向前进一位        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);        //仅方便gc回收                             elementData[--size] = null; // clear to let GC do its work        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 {        //找出第一个obj,执行删除            for (int index = 0; index < size; index++)                if (o.equals(elementData[index])) {                    fastRemove(index);                    return true;                }        }        return false;    }

fastRemove 根据下标快速移除元素

private void fastRemove(int index) {        modCount++;        int numMoved = size - index - 1;        //判断目标下标是否在数组中间,是则执行拷贝        if (numMoved > 0)            System.arraycopy(elementData, index+1, elementData, index,numMoved);        //yuan原数组尾元素置空            elementData[--size] = null; // clear to let GC do its work    }

### clear数组置空

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

### 添加另一个Collection对象所有元素进ArrayList

public boolean addAll(Collection
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
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; }

从指定区间元素开始删除(不包含toIndex所在元素)

protected void removeRange(int fromIndex, int toIndex) {        modCount++;        int numMoved = size - toIndex;        System.arraycopy(elementData, toIndex, elementData, fromIndex,                         numMoved);        // clear to let GC do its work        int newSize = size - (toIndex-fromIndex);        for (int i = newSize; i < size; i++) {            elementData[i] = null;        }        size = newSize;    }

移除包含在Collection中所有元素

public boolean removeAll(Collection
c) { Objects.requireNonNull(c); return batchRemove(c, false); }

批量删除 complement true:删除包含的,false:删除不包含的

private boolean batchRemove(Collection
c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { //迭代查找出符合complement的元素并依次保存elementData 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. //抽象地保存行为兼容性,即使c.contains()包含异常 //不等于意味迭代中间有异常 if (r != size) { //将没有判断的元素拷贝至已经并且符合complement的元素前 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } //如果w == size,即全部符合complement无需移除 if (w != size) { // clear to let GC do its work //否则执行删除下标W以后的元素 for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }

### writeObject输出元素

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

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            ensureCapacityInternal(size);            Object[] a = elementData;            // Read in all elements in the proper order.            for (int i=0; i

jdk7相关网页

转载地址:http://ncpfx.baihongyu.com/

你可能感兴趣的文章
深入理解PHP内核(十四)类的成员变量及方法
查看>>
Spring Boot2.0+中,自定义配置类扩展springMVC的功能
查看>>
参与博客编辑器改版,我的礼物 感谢51cto
查看>>
JavaWeb笔记——JSTL标签
查看>>
Eclipse插件大全 挑选最牛的TOP30
查看>>
一些实用性的总结与纠正
查看>>
Kubernetes概念
查看>>
逻辑卷管理器(LVM)
查看>>
一个小代码,欢迎大佬的意见,求指正
查看>>
搭建LAMP架构
查看>>
神经网络注意力机制--Attention in Neural Networks
查看>>
Spring.Net+WCF实现分布式事务
查看>>
在Linux上高效开发的7个建议
查看>>
java数据结构 - 数组使用的代码
查看>>
个人简历-项目经验
查看>>
swoole异步任务task处理慢请求简单实例
查看>>
DHCP
查看>>
oracle数据泵导入分区表统计信息报错(四)
查看>>
spring技术内幕读书笔记之IoC容器的学习
查看>>
细说多线程(五) —— CLR线程池的I/O线程
查看>>