ArrayList扩容机制

您所在的位置：网站首页 › arraylist扩容机制默认大小 › ArrayList扩容机制

ArrayList扩容机制

2024-05-25 01:11| 来源: 网络整理| 查看: 265

1. ArrayList简介：

ArrayList类又称动态数组，同时实现了Collection和List接口，其内部数据结构由数组实现，因此可对容器内元素实现快速随机访问。但因为ArrayList中插入或删除一个元素需要移动其他元素，所以不适合在插入和删除操作频繁的场景下使用。(注意：ArrayList是非线程安全的。)

ArrayList中的属性：

// 默认的容量大小（常量） private static final int DEFAULT_CAPACITY = 10; // 定义的空数组（final修饰，大小固定为0） private static final Object[] EMPTY_ELEMENTDATA = {}; // 定义的默认空容量的数组（final修饰，大小固定为0） private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 定义的不可被序列化的数组，实际存储元素的数组 transient Object[] elementData; // 数组中元素的个数 private int size;

ArrayList的三种构造方法:

无参的构造方法根据传入的数值大小，创建指定长度的数组通过传入Collection元素列表进行生成 1.1 无参的构造方法 // 无参构造方法 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

使用无参构造方法创建ArrayList时，elementData被赋予了默认空容量的数组。

注意，因为默认空容量数组是被final修饰的，此时ArrayList数组是空的、固定长度的，也就是说其容量此时是0，元素个数size为默认值0。

1.2 根据传入的数值大小，创建指定长度的数组 // 传容量大小的构造方法 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); } } 当initialCapacity > 0时，会在堆上new一个大小为initialCapacity的数组，然后将其引用赋给elementData，此时ArrayList的容量为initialCapacity，元素个数size为默认值0。当initialCapacity = 0时，elementData被赋予了默认空数组，因为其被final修饰了，所以此时ArrayList的容量为0，元素个数size为默认值0。当initialCapacity < 0时，会抛出异常。 1.3 通过传入Collection元素列表进行生成 // 传入Collection元素列表的构造方法 public ArrayList(Collection c) { // 将列表转化为对应的数组 elementData = c.toArray(); if ((size = elementData.length) != 0) { // 此处见下面详细解析 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // 赋予空数组 this.elementData = EMPTY_ELEMENTDATA; } }

传入Collection元素列表后，构造方法首先会将其转化为数组，将其索引赋给elementData。

如果此数组的长度为0，会重新赋予elementData为空数组，此时ArrayList的容量是0，元素个数size为0。如果此数组的长度大于0，会更新size的大小为其长度，也就是元素的个数，然后执行里面的程序。执行完后此时ArrayList的容量为传入序列的长度，也就是size的大小，同时元素个数也为size，此时ArrayList是满的。 2. Array List的扩容机制

ArrayList的add方法：

第一个add：传入添加元素

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

第二个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++; }

调用add方法时，主要使用的ensureCapacityInternal(size+1)函数。

下面为ensureCapacityInternal()函数，里面又调用了ensureExplicitCapacity

private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //默认无参构造走这里 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//扩容为10 } ensureExplicitCapacity(minCapacity);//真正扩容的地方 }

下面代码中，如果需要的最小容量 > 当前容量的大小，就执行 grow() 函数进行扩容

private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

下面是grow函数:

private void grow(int minCapacity) { // overflow-conscious code // 获取数组的大小。即老容量 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

扩容分析：

(1)当oldCapacity为0时，newCapacity = 0，此时会进入到if (newCapacity - minCapacity < 0) ，此时扩容的大小为1。以下两种情况会触发此扩容机制：

传容量的构造方法传入的是0时，elementData被赋予的是EMPTY_ELEMENTDATA，此时数组容量为0。此时添加元素时，符合if的条件，会进入此扩容情况，容量从0扩展到1。****传Collection元素列表的构造方法被传入空列表时，elementData被赋予的是EMPTY_ELEMENTDATA，数组容量为0。此时添加元素时，符合if的条件，会进入此扩容情况。

(2)当 oldCapacity 为1时，此时执行 newCapacity = oldCapacity + (oldCapacity >> 1) 时，执行结果还是为 1 ，因此同样需要走 if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}语句。

(3)最后一种情况，这时就会按照oldCapacity + (oldCapacity >> 1);的方式进行1.5倍扩容。

3.总结

ArrayList特点：

ArrayList的底层是数组，因此查找遍历快，增删慢。ArrayList可随着元素的增长而自动扩容，正常扩容的话，每次扩容到原来的1.5倍。ArrayList的线程是不安全的。

ArrayList的扩容：

分两种情况：

第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同：

无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，此后若需要扩容，则正常扩容。传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的。传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的。

第二种情况，当ArrayList的容量为1时，此时添加元素的话，需要扩容，ArrayList在扩容时略有不同：

此时 oldCapacity 为1时，此时执行 newCapacity = oldCapacity + (oldCapacity >> 1) 时，执行结果还是为 1 ，因此同样需要走 if (newCapacity - minCapacity < 0) {newCapacity = minCapacity;}语句。

第三种情况，当ArrayList的容量大于1，并且ArrayList是满的时，此时添加元素的话，进行正常扩容，每次扩容到原来的1.5倍。

【本文地址】

ArrayList扩容机制

ArrayList扩容机制

今日新闻

推荐新闻