纯净、安全、绿色的下载网站

首页

当前位置:首页IT学院IT技术

Java ArrayList的扩容机制 Java基础之ArrayList的扩容机制

王哥爱编程   2021-05-08 我要评论
想了解Java基础之ArrayList的扩容机制的相关内容吗,王哥爱编程在本文为您仔细讲解Java ArrayList的扩容机制的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,ArrayList的扩容机制,Java,ArrayList,下面大家一起来学习吧。

我们知道Java中的ArrayList对象底层是基于数组实现的,而数组是有长度限制的,那基于数组实现的ArrayList是否有长度限制呢?我们通过ArrayList的构造方法来剖析

ArrayList提供了3种构造方法以便我们来获取:

  • ArrayList(int initialCapacity) 第一种需要赋值长度进行new
  • ArrayList() 第二种无参构造,不需要赋值数组初始长度
  • ArrayList(Collection<? extends E> c) 第三种入参一个继承了Collection对象转化为ArrayList
//需要赋值ArrayList一个int类型长度值
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //无参构造
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
	//入参继承了Collection对象转化为ArrayList
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        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;
        }
    }

接下来我们从ArrayList的赋值初始长度的构造方法和无参构造方法进行跟踪,来得到我们的答案;

1.ArrayList(int initialCapacity)

/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
    
public ArrayList(int initialCapacity) {
		//initialCapacity大于0的情况下,就去new一个Object类型、长度为initialCapacity的数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        //initialCapacity等于0的情况下,则生成已经创造好的Object[];
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        //initialCapacity小于0的情况下,直接抛异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

通过上述源码分析,在赋值初始长度的构造方法中,如果initialCapacity符合大于0的情况下的话,在new ArrayList的时候是会创造一个长度为initialCapacity的对象数组,而小于0的情况下则返回已经创造好的Object[] EMPTY_ELEMENTDATA;

2.ArrayList()

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    public ArrayList() {
    	//当你没有赋值初始长度时,同样是去赋值已经创造好的空数组,没有长度值
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

当ArrayList生成后,我们接着来看他的add()添加方法,找到ArrayList实现的add方法:

在这里插入图片描述

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    public boolean add(E e) {
    	//1、add的第一步先去调用ensureCapacityInternal方法传入size+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    //3、传入一开始我们new的数组和add后的数组长度
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
    	//如果elementData等于空数组,则对比DEFAULT_CAPACITY和minCapacity大小,返回大的值,DEFAULT_CAPACITY默认为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //否则返回minCapacity
        return minCapacity;
    }

	//2、在ensureCapacityInternal方法内部又去调用calculateCapacity(elementData, minCapacity)方法,传入add数据后的list的size长度
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
	//4、拿到minCapacity的值后,对modCount++,比对添加后的list的长度和现在的list的长度来判断是否需要进行扩容;
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 如果添加list的长度大于list现在的长度,则说明list的长度已经不够了,需要走grow(minCapacity)方法进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }    

经过上面的分析,我们发现在add时,ArrayList会先去判断你是不是一个空数组,如果是的话则会给你赋值数组的,长度值,默认为10,到这一步我们就知道了,不管是哪种构造方法都会在add时,都会进行判断给空数组进行赋值长度,也就是说对于ArrayList来讲,他是需要数组的长度的,同时他还会对比数组原来长度和add后的长度来判断是否需要进行扩容。

接下来我们看grow(minCapacity)扩容方法:

private void grow(int minCapacity) {
        // 拿到数组原来的长度
        int oldCapacity = elementData.length;
        //进行1.5倍计算
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果1.5倍的值小于add后的长度值,则把add后的长度值设置成新数组的长度
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果1.5倍的值大于array的最大长度则调用hugeCapacity(minCapacity)方法
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 调用Arrays.copyOf方法传入旧数组对象和新数组的长度,进行扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
            //如果add后的长度大于array的最大长度那就返回Integer的最大长度,否则返回array的最大长度,丢弃1.5倍的值,选择array的最大长度来进行扩容
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

到此,我们对于源码的分析就结束了。

结论:

1.new的时候可以给ArrayList设置数组的长度值,也可以不设置,不设置的情况下,在第一次add时会默认赋值长度为10

2.每一次add时都会去对比add后的长度值和数组原有长度值,判断是否需要走grow(int minCapacity)扩容方法

3.默认ArrayList是以1.5的长度进行扩容,会先去创造一个新的长度的数组,再将原来数组赋值过去,完成扩容操作

4.还会去对比1.5的长度和array的最大长度进行选择用array的最大长度还是选择Integer的最大长度

5.工作时,如果我们能知道ArrayList将要存储多少数据时,最好是new的时候赋值一个初始值,因为去数组扩容肯定是要浪费时间和cpu资源的


相关文章

猜您喜欢

网友评论

Copyright 2022 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们