DEBUG ArrayList

1,ArrayList面试必问

  • 说说ArrayList和LinkedList的区别?

    ArrayList基于数组实现,LinkedList基于链表实现,不同的数据结构决定了ArrayList查询效率比较高,而LinkedList插入删除效率比较高,反过来就比较慢了。

  • ArrayList默认初始容量为多少?按照几倍来扩容?

    10,1.5倍。

  • 说说数组扩容的原理?

    ArrayList扩容调用的是Array.copyof函数,把老数组遍历赋值给新数组返回。

  • 说说ArrayList常见方法的时间复杂度?

    • get方法通过下标获取元素,时间复杂度为O(1)
    • add方法直接添加会添加到集合的尾部,时间复杂度为O(1)
    • add方法通过下标添加到非尾部会引起数组的批量移动,时间复杂度为O(n),否则为O(1)
    • remove方法通过下标删除非尾部元素引起数组批量移动,时间复杂度为O(n),反之则为O(1)
    • remove方法根据对象删除需要遍历集合,时间复杂度为O(n),如果删除的为非尾部元素,会使数组批量移动,时间复杂度为O(n^2)

    总之,通过下标操作的时间复杂度为O(1),如果触发了数组的批量移动,时间复杂度为O(n),如果通过对象操作需要遍历集合,时间复杂度已经为O(n),若同时触发了数组的移动,时间复杂度为O(n^2).

  • ArrayList和vector的区别

    • 最大的区别在于线程是否安全
    • 其次Vector是两倍扩容
    • 最后就是在不指定大小的情况下,ArrayList容量初始化是在添加元素的时候,而Vector有一个无参构造器直接初始化为10

2,Debug ArrayList源码

由于1.7和1.8几乎没什么变化,本文以jdk1.8为例。

2.1 用Debug分析一个元素是如何add进ArrayList

编写测试用例,打上断点:

DEBUG ArrayList

先分析构造函数如何初始化,关键步骤如下:

DEBUG ArrayList

elementData是ArraList底层数组的实现,(ps:hashMap数组使用table命名)

DEBUG ArrayList

DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示默认的空数组,也就是说ArrayList在构造函数初始化时并不会进行底层数组的初始化。

DEBUG ArrayList

给元素的添加打上断点,分析过程:

DEBUG ArrayList

进入add方法内部:

public boolean add(E e) {
		//确保内部容量,在元素添加进来前可能要进行扩容操作,size初始化为0,表示集合的长度
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //添加元素,size自增
        elementData[size++] = e;
        return true;
    }

进入ensureCapacityInternal方法内部:此时elementData为空,size+1=minCapacity=1

ensureExplicitCapacity:确保明确的能力

DEBUG ArrayList

计算容量,calculateCapacity方法:

private static int calculateCapacity(Object[] elementData, int minCapacity) {
	//判断数组是否为空,若为空,返回默认容量和最小容量的最大值,若不为空,返回最小容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

DEFAULT_CAPACITY默认容量为10:

DEBUG ArrayList

继续分析,进入:

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));此时参数为10,也就是ArrayList的默认容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;   //集合的修改次数

    //如果最小容量减去数组长度大于0,进行扩容,此时最小容量为10,数组长度为0
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

核心扩容函数grow:(ps:HashMap中扩容函数为resize)

private void grow(int minCapacity) {
    //oldCapacity:旧数组容量
    int oldCapacity = elementData.length;
   
   //新容量等于旧容量加上旧容量的一半,>>1相当于除以2(ArrayList扩容是1.5倍)
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //新容量小于最小容量,则赋值为最小容量,此时newCapacity等于0,minCapacity为10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
        
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //赋值给新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

数组复制Arrays.copyOf:

DEBUG ArrayList

DEBUG ArrayList

2.2 用Debug分析如何通过数组下标获取ArrayList元素

打上断点,debug:

DEBUG ArrayList

首先进行范围检查,而后返回元素

DEBUG ArrayList

DEBUG ArrayList

2.3 用Debug分析如何通过数组下标删除一个元素

打上断点:

DEBUG ArrayList

进入remove方法内部,

public E remove(int index) {
 		//下标范围检查
        rangeCheck(index);
		//修改次数自增
        modCount++;
        //保留当前删除元素的值,稍后返回
        E oldValue = elementData(index);
		//需要移动元素的个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
        //底层使用native方法,debug进不去。native方法:java调用其他语言的接口
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //最后一位置空                     
        elementData[--size] = null; // clear to let GC do its work
		//返回删除元素的值
        return oldValue;
    }

2.4 用Debug分析如何通过对象删除一个元素

DEBUG ArrayList

进入remove方法:

public boolean remove(Object o) {
//如果对象为空,则遍历ArrayList集合
        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;
    }

进入fastRemove方法:

private void fastRemove(int index) {
        modCount++;
        
        //numMoved:需要移动数组的个数
        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 wrk
    }

2.5 用Debug分析向数组中间添加元素

DEBUG ArrayList

进入add方法

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

关于System.arraycopy时间复杂度问题,在添加或者删除最后一个元素的时候不会触发数组的复制机制,时间复杂度为O(1),若是添加到数组中间,由于会触发数组的复制,时间复杂度为O(n)。对于删除元素同样,根据数组下标删除的情况下,删除尾部元素是不会触发数组的扩容机制的,若删除中间的元素,同样会触发数组的复制。若根据对象删除元素,由于本身遍历到对象的时间复杂度为O(n),删除元素后再对数组进行重组,所以时间复杂度为O(n^2)。

DEBUG ArrayList

原文 

http://www.cnblogs.com/noneplus/p/13336006.html

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » DEBUG ArrayList

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址