Java教程

JDK成长记2:ArrayList常用方法源码探索(上)

本文主要是介绍JDK成长记2:ArrayList常用方法源码探索(上),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

file

file

上一节相信你不光学会ArrayList构造函数的知识,更学会了先脉络后细节、连蒙带猜的思想。在之后的几节中,你将学会ArrayList常用方法的源码原理。学完之后,你将不会再被ArrayList的面试题问倒了,更可以得心应手的使用ArrayList。

今天这一节,你主要可以学到以下几点:

  1. ArrayList扩容原理
  2. 影响ArrayList性能的根本原因是什么
  3. 学会新的源码阅读思想和方法

让我们开始吧!

ArrayList第一次调用add方法发生了什么?

file

首先你要修改下上一节之前的Demo,修改如下:

import java.util.ArrayList;

import java.util.List;

public class ArrayListDemo {

 public static void main(String[] args) {
     //默认大小是0
     List<String> hostList = new ArrayList<>(); 
     hostList.add("host1");
 }

}

上面代码,假设你通过add方法向hostList添加了1个host主机地址。ArrayList第一次调用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;

    }

看之前,我又要多说两句,源码的注释和方法名,有时候能帮助你了解这个方法大致的作用。这是很关键的一点。比如注释的意思是add方法是追加一个具体的元素到list的末尾;方法名ensureCapacityInternal,是确保内部容量的意思。看过之后,你应该可以猜到这方法大致是确认容量相关的,可能是判断容量能否添加元素用的。

还要注意的是,你看一个方法的时候,不要着急直接从第一个行就开始看,也是先根据注释和方法名有一个大概的认识后,你需要看下整个方法的结构之后再开始。比如调用了哪些其他方法,有几个for循环或if结构。就像这个add方法,他主要有2步,第一步是调用了一个方法,应该是确保内部容量是否够添加元素,第二步是一个数组基本赋值操作并且size++一下。

如下图所示:

file

ArrayList的数组大小为0也能可以添加元素?

file

接着当你知道了整个方法的脉络,你再来看下细节,先看第一步:ensureCapacityInternal()。

这个方法入参是size + 1,size之前说你应该看到过,就是一个成员变量int size。它的默认值是0,所以size+1后,这个方法的实参就是1,那么形参minCapacity的值就是1。(实参就是传入方法实际的值,形参就是方法括号中使用的参数名)。可以看到ensureCapacityInternal的代码清单如下:

private void  ensureCapacityInternal(int minCapacity) {

  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

接着你可以看到这里又调用了calculateCapacity方法和ensureExplicitCapacity方法。我们先进入calculateCapacity看下,你可以记下它的实参是minCapacity=1,elementData还记得么?是ArrayList核心的那个成员变量Object[]数组。calculateCapacity代码如下:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA  = {};

transient Object[] elementData; 

private static final int DEFAULT_CAPACITY = 10;



private static int  calculateCapacity(Object[] elementData, int minCapacity) {

        if (elementData ==  DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

            return Math.max(DEFAULT_CAPACITY, minCapacity);

        }

        return minCapacity;

 }

这里你可以看熟悉的两个成员变量:

elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

在ArrayList无参构造函数的时候就看到过。第一次调用add方法的时候,它们俩的引用地址和值都是应该一样的,因为在构造函数中有过这么一句话this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

所以这里进入第一个if条件,然后使用DEFAULT_CAPACITY和minCapacity作比较,可以看到DEFAULT_CAPACITY这个变量的值是10,也就是说这里Math.max操作后会返回10。

到这里你可以在完善下之前画的图,就会变成如下所示:

file

也就是说calculateCapacity返回后,回到ensureCapacityInternal这个方法,会传入ensureExplicitCapacity的实参是10,因为calculateCapacity(elementData, minCapacity)= 10。

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

接着你又会进入ensureExplicitCapacity方法,看到如下代码:

 private void ensureExplicitCapacity(int  minCapacity) {

        modCount++;

        // overflow-conscious code

        if (minCapacity - elementData.length  > 0)

            grow(minCapacity);

    }

此时形参minCapacity也就是刚才传入的10,你可以从名字上看这个方法,ensureExplicitCapacity意思是确保精确的容量的意思。还是先看下方法的脉络,第一行有一个modCount++,之后你可以看到一行代码注释,overflow-consciouscode意思是说具有溢出意思的代码,之后有一个if条件,满足会进入grow方法。

到这里你可以连蒙带猜下,这里的grow方法,是不是就是说容量不够,会进行增长,也就是扩容呢?

因为我们知道,无参构造函数创建的ArrayList大小默认是一个为0的Object[]数组elementdata。而且elementdata.length肯定是0,难道也能添加元素么?肯定是不可以的。

接着我们逐行看下,第一行的modCount好像不太知道是什么,你可以点击下它,看到它是一个成员变量,而且有一大堆注释,好像也没看懂什么意思。所以这里要告诉大家另一个看源码的思想了:抓大放小。比如这里看上去modeCount和添加操作没啥关系,就先跳过!(其实这个modCount是并发操作ArrayList时,fail-fast机制的实现,下一节我会讲到的)

目前执行代码如下图所示:

file

ArrayList第一次添加元素会扩容么?

file

你接着往下看,很明显,minCapacity=10,elementData这个空数组length肯定是0。所以10-0>0,会满足if条件,进入grow方法,它的实参是10。它的代码清单如下:

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

    }

grow方法形参minCapacity的值是10,你进入这个grow方法后,从脉络上来看,有两个if分支,有两个局部变量oldCapacity和newCapacity,还有一步elementData通过Arrays.copyOf方法的赋值操作。

而且oldCapacity应该是0,因为我们知道elementData数组是空的。接着你会看到一句:intnewCapacity = oldCapacity +(oldCapacity >> 1);

这句话是什么意思呢?其实就是oldCapacity右位移1位。如果你还记得计算机基础中的话,右移一位,有点类似于除以2,底层是二进制的运算而已。这里可以举个例子:

比如oldCapacity=10,如果先左移1,就是乘以2,在右移 1就是除以2,如下所示:

file

那么int newCapacity = oldCapacity +(oldCapacity >> 1); 其实这句话的意思就是在原有大小基础上增加一半大小。

但是由于oldCapacity=0,所以增加一半大小,newCapacity=0+0>>1=0+0=0

而此时minCapacity=10。这样就会进入第一个if条件,因为newCapacity - minCapacity < 0,即0-10<0,然后进行了一步赋值操作,newCapacity就会变成和minCapacity一样,值是10。

这里你可以总结一下,也就是说如果创建ArrayList时,不指定大小, ArrayList第一次添加元素,会指定默认的容量大小为10。

你可以继续完善你的图,grow方法逻辑如下:

file

ArrayList计算完扩容容量大小后,又干了什么?

file

除了上面计算扩容容量大小的代码,是grow的核心逻辑之一。

第一次添加元素时,在grow中,最后还会执行一行代码:

elementData**= Arrays.copyOf(elementData, newCapacity);**

这个也是grow方法中另一个核心步骤,数组的拷贝。

你可以点击Arrays.copyOf,看看它底层做了些什么。代码如下:

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

还是从脉络上看下,这里Arrays.copyOf它实参是elementData(Object[]空数组)和newCapacity=10。可以看到它内部直接调用了一个重载方法。

在重载方法中,首先调用了一个三元表达式和一个System.arraycopy方法调用,接着执行了

System.arraycopy(original, 0, copy, 0,Math.min(original.length,newLength));

这句话,它看样子像是操作了original和 copy的样子。

之后你再来仔细分析下细节。

ArrayList的缺点,原因原来是在这里!

file

根据传递的参数elementData的class是Object[].class的类型,可以看出三元表达式会执行(T[]) new Object[newLength]。

接着就会执行System.arraycopy这个方法。你可以查阅下JDK的API,它的主要是作用是数组的拷贝。

由于这个方法的API不是很好理解。这里我给大家讲下,它的方法签名如下:

System.arraycopy(Objectsrc,int srcPos,Object dest,int destPos, int length)****。

这里,如果大家遇见难以理解的代码,除了画图,另外一个方法就是**举例子。**比如:

file

好了,你知道了这个API基本的使用,再来看源码中的代码:

System.arraycopy(original,0,copy,0,Math.min(original.length, newLength));

首先original就是我们传递进来的elementData。它的length是0。newLength是传递进来的newCapacity,也就是10。copy 是我们刚创建的Object[]数组,长度为10。Math.min取最小后是0。也就是变成:

System.arraycopy(original,0, copy, 0,0);

这个就很好理解了,就是从original位置0开始移动0个元素到copy数组,从copy数组0位置开始覆盖。这就等于什么都没拷贝,直接返回了我们新创建的数组T[] copy,这个数组大小为10。

最终Arrays.copyOf获得了一个长度为10的数组,但里面没有任何元素。接着这句话就执行完了。elementData = Arrays.copyOf(elementData, newCapacity);结束grow方法的也就执行完了。

而grow方法执行完就意味着ensureCapacityInternal执行完了。这个方法已经确保了内部数组的容量大小可以放入新元素。

我们回到开始,执行完第一步,内部容量确保后,接着第二步直接执行了elementData[size++]= e;通过数组的赋值操作,就完成第一次元素的添加了!

到这里可以发现,当添加的时候,如果大小不够就会进入grow方法,进入grow方法就会进行一次1.5倍的扩容。而且代码规范一般都建议我们要指定ArrayList的大小,如果不指定,可能会造成频繁的扩容和拷贝,造成性能低下。

  public boolean add(E e) {

        ensureCapacityInternal(size +  1);  // Increments modCount!!

        elementData[size++]  = e;

        return true;

    }

好了,到这里ArrayList最常用的add(E e)方法的源码原理就已经研究透彻了。

最终的源码原理图如下:

file

最后我给大家把收获到的总结下:

1、你知道了ArrayList的扩容机制:底层通过grow方法。它的核心一个是计算出扩容大小,是基于右移1位来计算,一般扩容大小为1.5倍,另一个核心是进行数组拷贝,底层通过System.arraycopy来创建新数组,来最终实现空间的扩容。

2、你也知道了频繁扩容会造成频繁的数组拷贝,会造成耗时,影响ArrayList的性能。

3、更重要的是,这一节你学会了抓大放小的思想、对先脉络后细节、连蒙带猜的思想更熟练了,还进行了适当的举例子和画图分析源码。

你可以通过今天学的思路和方法,去看看ArrayList的另一个方法源码:**add(int index, E element)**这个方法意思是在指定位置添加一个元素,研究下它的源码原理。

金句甜点

file

除了今天知识,技能的成长,给大家带来一个金句甜点,结束我今天的分享:改变自己比改变别人更重要

其实生活中很多矛盾和问题,都来自于我们总是无形的要求别人做什么,夫妻之间,亲人之间,朋友之间……当别人没有做到你期望的,你就可能会不开心,抱怨,甚至吵架,有脾气。一个人有脾气,其实你对事,对人的包容不够,想想你对一个美女和一个丑女的包容肯定是不一样的。

比如不要总是希望父母理解你做什么,而是改变自己去理解他们,他们的认知和你不一样。比如我的父亲,他比我快要大一倍的岁数,过了今年就60岁了,他的思想观念很多都是和毛主席那个年代的人一样,他有时候不理解这个时代,他的家里和手机壁纸都是毛主席的画像,他甚至不会用微信转账,还在用现金,不知道大数据,云计算到底是什么,总被微信朋友圈忽悠的一塌糊涂。我不应该要求他们非要用微信转账,支付宝付款,也不应该总是给他非要讲明白大数据云计算。而是应该改变我自己下,我应该理解他,理解他可能没什么文化,他认知就比较越低,认知越低,有时候也就越顽固,更要改变自己,不总是逼我爸学习,当然他想学我就耐心教他。渐渐地他还是学会了基本转账,因为他喜欢抢红包。

所以,其实你可以想想,生活中,很多时候男女朋友或者夫妻吵架,大多都是因为你要求对方做什么导致的。那么你就不要总想着改变别人,要求别人,改变自己比改变别人更重要。改变了自己才能更好的影响别人。相信各位每天改变一下,学习一篇成长记,会更能影响别人,跟你一起学习和成长。

最后,大家可以在阅读完源码后,在茶余饭后的时候问问同事或同学,你也可以分享下,讲给他听听。

欢迎大家在评论区留言和我交流。

(声明:JDK源码成长记基于JDK 1.8版本,部分章节会提到旧版本特点)

这篇关于JDK成长记2:ArrayList常用方法源码探索(上)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!