ArrayList扩容机制详解

图片[1]-ArrayList扩容机制详解-梦境学习站

简介

ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList,实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口,所以ArrayList 是支持快速访问、复制、序列化的。

扩容机制

1.1首先,创建一个ArrayList对象

ArrayList arrayList = new ArrayList();

底层原理:调用无参构造器

 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的值为“{}”,为空数组

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

即使用ArrayList()创建ArrayList对象时,并没有初始化底层数组elementData,等到调用add(E e) 方法的时候再初始化elementData,这种”懒加载”模式可以节省内存。

1.2 调用add(E e) 方法

 arrayList.add("test");

执行add方法,添加元素。

public boolean add(E e) {
        // 确认elementData容量是否足够
        ensureCapacityInternal(size + 1);  // 第一次调用add()方法时,size=0
        elementData[size++] = e;
        return true;
    }

先调用ensureCapacityInternal(int minCapacity) 方法,对数组容量进行检查,不够时则进行扩容。

private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData为"{}"即第一次调用add(E e),重新定义minCapacity的值,赋值为DEFAULT_CAPACITY=10
    // 即第一次调用add(E e)方法时,定义底层数组elementData的长度为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
	// 判断是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity(minCapacity) 判断是否需要扩容

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

// 第一次进入时,minCapacity=10,elementData.length=0,对数组进行扩容
// 之后再进入时,minCapacity=size+1,elementData.length=10(每次扩容后会改变),
// 需要minCapacity>elementData.length成立,才能扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

grow(minCapacity) 对数组进行扩容

private void grow(int minCapacity) {
        // 将数组长度赋值给oldCapacity
        int oldCapacity = elementData.length;
    	// 将oldCapacity右移一位再加上oldCapacity,即相当于newCapacity=1.5oldCapacity(不考虑精度损失)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    	// 如果newCapacity还是小于minCapacity,直接将minCapacity赋值给newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    	// 特殊情况:newCapacity的值过大,直接将整型最大值赋给newCapacity,
	// 即newCapacity=Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 将elementData的数据拷贝到扩容后的数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

// 如果大于临界值,进行整型最大值的分配
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

结论:

使用ArrayList()创建ArrayList对象时,不会定义底层数组的长度,当第一次调用add(E e) 方法时,初始化定义底层数组的长度为10,之后调用add(E e)时,如果需要扩容,则调用grow(int minCapacity) 进行扩容,长度为原来的1.5倍。

ArrayList还有有参构造器:ArrayList(int initialCapacity)和ArrayList(Collection<? extends E> c),前者创建可以指定初始容量的集合,后者创建一个包含指定collection元素的集合,两者的底层数组初始化和扩容机制与上述ArrayList()一样,且添加方法add(int index, E e)和add(E e)的扩容机制一样。

Arraylist扩展内容
------本页内容已结束,喜欢请分享------

感谢您的来访,获取更多精彩文章请收藏本站。

© 版权声明
THE END
喜欢就支持一下吧
点赞8 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片