ArrayyList底层分析

时间:2020-8-27 作者:admin


ArrayList源码分析

今天写了第一篇博客,学了这么久,第一次来,加油!这里用了最熟悉的md来排版,本地使用typora,如果有什么写的不好的欢迎提出。

1、ArrayList概述

1、ArrayList是一个可以动态增长和缩减的索引序列,它是基于数组实现的List类。

2、该类封装了一个动态再分配的Object[]数组,每一个类对象都有一个capacity(容量)属性,表示 它们所封装的Object[]数组的长度,当向ArrayList中添加元素时,该属性值会自动增加。如果想 ArrayList中添加大量元素,可使用ensureCapacity方法一次性增加capacity,可以减少增加重分配 的次数提高性能。

3、ArrayList的用法和Vector向类似,但是Vector是一个较老的集合,具有很多缺点,不建议使用。

另外,ArrayList和Vector区别是,前者是线程不安全的,多条线程访问下,需要手动保证该集合的同步性,而后者是线程安全的。

ArrayList和Collection的关系:

ArrayyList底层分析

2、ArrayList的数据结构

ArrayList的数据结构如下:

ArrayyList底层分析

eg:底层的数据结构就是数组,数组元素类型为Object类型,即可以存放所有数据类型,我们对ArrayList类的实例所有的操作底层都是基于数组的。

3、ArrayList源码分析

1、继承层次

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

可以看到ArrayList实现List的接口的同时继承了AbstractList接口,但AbstractList接口也实现了List接口,本以为有什么用意,查了以后才发现这是作者的失误,具体可以看https://stackoverflow.com/questions/18558536/why-does-arraylist-class-implement-list-as-well-as-extend-abstractlist?r=SearchResults

Cloneable接口:实现了该接口,就可以使用Object.Clone()方法了。 Serializable接口:实现该序列化接口,表明该类可以被序列化,什么是序列化?简单的说,就是能够 从类变成字节流传输,然后还能从字节流变成原来的类。

2、类中的属性

	//版本号
	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; 
	//实际元素大小,默认为0
    private int size;

3、构造方法

可以看到这里有三个构造方法,两个有参一个无参

ArrayyList底层分析

有参构造方法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
     */

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //将自定义的容量大小当成初始化initialCapacity的大小
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
            //等同于无参构造
        } else {
            //判断如果自定义大小的容量小于0,则报下面这个非法数据异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

无参构造方法

 /**
     * Constructs an empty list with an initial capacity of ten.
     * 看这里翻译就知道 意思是初始容量默认给一个10的大小
     */
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA:是个空的Object[], 将elementData初始化,elementData也是个Object[]类型。空的Object[]会给默认大小10,等会会解释什么时候赋值的。

有参构造方法2

/**
     * 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
     将其元素放入此列表的集合,如果指定集合为null,则抛出空指针异常
     */ 
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//转化为数组
    //每个集合的toarray()的实现方法不一样,所以需要判断一下,如果不是Object[].class类型,那么久需要使用ArrayList中的方法去改造一下。
        if ((size = elementData.length) != 0) {
            
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4、add方法(重要)

	 /**
     * Appends the specified element to the end of this list.
     *添加一个特定的元素到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) {
        //确定内部容量是否够了,size是数组中数据的个数,因为要添加一个元素,所以size+1,先判断size+1的这个个数数组能否放得下,就在这个方法中去判断是否数组.length是否够用了。
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        //在数据中正确的位置上放上元素e,并且size++
        return true;
    }

其中ensureCapacityInternal方法,不难看出就是确定容量的方法,这里单独分析

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

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //这里判断初始化的elementData是不是空的数组,也就是没有长度
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //如果是空,那minCapacity=size+1其实就是等于1,空的数组没有长度也不能存东西,就把minCapacity变成默认大小10,但在这里还没初始化其大小
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //这里确认实际容量,上面只是将minCapacity的大小=10,这里才是判断elementData是否够用
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        //minCapacity如果大于了实际elementData的长度,那么就说明elementData数组的长度不够用,不够用那么就要增加elementData的length。
        //这里有的同学就会模糊minCapacity到底是什么呢,这里给你们分析一下
/*第一种情况:由于elementData初始化时是空的数组,那么第一次add的时候,minCapacity=size+1;也就minCapacity=1,在上一个方法(确定内部容量ensureCapacityInternal)就会判断出是空的数组,就会给将minCapacity=10,到这一步为止,还没有改变elementData的大小。
第二种情况:elementData不是空的数组了,那么在add的时候,minCapacity=size+1;也就是minCapacity代表着elementData中增加之后的实际数据个数,拿着它判断elementData的length是否够用,如果length不够用,那么肯定要扩大容量,不然增加的这个元素就会溢出。*/
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

5、grow方法,也很重要

    private void grow(int minCapacity) {
        // overflow-conscious code
        //将扩充前的elementData大小给oldCapacity
        int oldCapacity = elementData.length;
        //newCapacity就是1.5倍的oldCapacity(应该都看得懂>>1吧)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //这句话就是适应于elementData就空数组的时候,length=0,那么oldCapacity=0,newCapacity=0,所以这个判断成立,在这里就是真正的初始化elementData的大小了,就是为10.前面的工作都是准备工作。
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果newCapacity超过了最大的容量限制,就调用hugeCapacity,也就是将能给的最大值给newCapacity
        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();
        //如果minCapacity都大于MAX_ARRAY_SIZE,那么就Integer.MAX_VALUE返回,反之将MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity,可能扩充的太大了,就用minCapacity来判断了。
//Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE:2147483639 也就是说最大也就能给到第一个数值。还是超过了这个限制,就要溢出了。相当于arraylist给了两层防护。
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

ArrayyList底层分析

6、扩容总结

正常情况下扩容1.5倍,特殊情况下(已达到最大值就取最大值)

当我们调用add方法,实际调用函数如下

ArrayyList底层分析
ArrayyList底层分析

7、set()

ArrayList底层是一个数组,set()方法也就变得非常简单,直接对数组的指定位置赋值即可。

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置,复制的仅仅是引用
    return oldValue;
}

8、get()

get()方法同样很简单,唯一要注意的是由于底层数组是Object[],得到元素后需要进行类型转换。

public E get(int index) {
        rangeCheck(index);

        return elementData(index);//注意类型转换
    }

8、remove方法

remove()方法也有两个版本,一个是remove(int index)删除指定位置的元素,另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必须显式的为最后一个位置赋null值。

public E remove(int index) {
        rangeCheck(index);;//检查index的合理性

        modCount++;//这个作用很多,比如用来检测快速失败的一种标志。
        E oldValue = elementData(index);//通过索引直接找到该元素

        int numMoved = size - index - 1;//计算要移动的位数。
        if (numMoved > 0)
            //这个方法用来移动元素的。
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
    //将--size上的位置赋值为null,让gc(垃圾回收机制)更快的回收它。
        elementData[--size] = null; // clear to let GC do its work
	//返回删除的元素。
        return oldValue;
    }

当然了这里的gc不一定会回收了,为什么?因为对象能否被GC的依据是是否还有引用指向它,上面代码中如果不手动赋null值,除非对应的位置被其他元素覆盖,否则原来的对象就一直不会被回收。

9、indexOf()方法

// 从首开始查找数组里面是否存在指定元素
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;
}

4、特性总结

1、ArrayList可以存放null

2、ArrayList本质上是一个动态(elementData)数组

3、ArrayList比数组厉害的地方就是会自动扩展,这个特性主要由grow实现

4、ArrayList因为本质是数组,所以查询快,增删慢(需要增删建议使用LinkedList)

5、常见面试题

1、ArrayList是否会越界?

多线程下ArrayList调用add()可能会出现数组下标异常
具体见关于ArrayList越界问题

2、ArrayList的大小是如何自动增加的?

见上面扩容机制

3、在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?

主要还是围绕底层数组特性来回答

4、ArrayList如何顺序删除节点 ?

这个有点难,一种是通过for循环,注意从后往前删,否则删不干净

//通过一般for循环,必须从后往前删除!
for (int i=(arraylist.size()-1);i>=0;i--){
    arraylist.remove(i);
}

另一种使用自带的迭代器中的remove即可

//迭代器的方式顺序移除节点
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    iterator.next();//没有这一行, 就会抛出java.lang.IllegalStateException异常
    iterator.remove();//这里只能调用迭代器对应的remove()方法
}

注意:不调用iterator.next();这一行, 会抛出IllegalStateException异常。

原因是:通过Iterator来删除,首先需要使用next方法迭代出集合中的元素,然后才能调用remove方法,否则集合可能抛出IllegalStateException异常。

5、你在什么时候用ArrayList?

基于特性来回答,如果不需要排序,也不增删时用这个,如果需要这些就不考虑了

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。