所有分类
  • 所有分类
  • 未分类

Java–ArrayList扩容的原理

简介

说明

本文介绍Java的ArrayList是如何进行扩容的。即:扩容的机制。

重要大小

初始大小扩容倍数底层实现是否线程安全同步方式
ArrayList101.5倍Object数组线程不安全
Vector102倍Object数组线程安全synchronized

ArrayList在添加元素时实际容量如果不够了,就会扩容,没有HashMap那种加载因子的概念。(也可以理解为加载因子是1)。

下边介绍ArrayList的扩容机制。

扩容机制

1. new一个ArrayList对象

直接new 一个ArrayList对象时(未指定初始容量大小)是一个空的数组,容量大小为零。

public ArrayList() {
	// DEFAULTCAPACITY_EMPTY_ELEMENTDATA 变量为一个空的数组 
	// private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2. 调用add()方法

当第一次调用ArrayList对象的add方法时,分配容量大小

public boolean add(E e) {
	// size为ArrayList的实际数量大小而非容量大小,若未指定容量构建ArrayList对象,size为0
	ensureCapacityInternal(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
}
private void ensureCapacityInternal(int minCapacity) {
	// 如果为空数组,最小需要容量为默认容量DEFAULT_CAPACITY 也就是10 
	// private static final int DEFAULT_CAPACITY = 10;
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	// 调用扩容方法
	ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
	//protected transient int modCount = 0;
	modCount++;
	// 如果需要的最小容量大于此时的容量,调用真正的扩容方法
	// overflow-conscious code
	if (minCapacity - elementData.length > 0)
		grow(minCapacity);
}

3. 扩容

private void grow(int minCapacity) {
	// transient Object[] elementData;
	// overflow-conscious code
	int oldCapacity = elementData.length;

	// 第一次扩容1.5倍
	int newCapacity = oldCapacity + (oldCapacity >> 1);

	// 还是比需要的容量小就把需要的容量作为新的容量值
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;

    // 这里主要防止1.5倍扩容导致新容量值超过数组最大容量。
	// 如果新的容量比数组最大容量还大,则比较需求容量和数组最大容量
	//     如果需求容量比数组最大容量大就取整数最大值,反之取数组最大容量
	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);
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
		Integer.MAX_VALUE :
		MAX_ARRAY_SIZE;
}
3

评论7

请先

  1. 请问面试怎么答?这里都是代码。 :smile:
    叶叶叶ye 2024-04-15 0
    • 面试大致描述一下流程即可。代码不用太关注,重点看正文文字与代码里的注释即可。
      自学精灵 2024-04-15 0
      • 我发现有这样回答的: ArrayList 是一个数组结构的存储容器,默认情况下,数组的长度是 10. 当然我们也可以在构建 ArrayList 对象的时候自己指定初始长度。 随着在程序里面不断地往 ArrayList 中添加数据,当添加的数据达到 10 个的时候, ArrayList 就没有多余容量可以存储后续的数据。 这个时候 ArrayList 会自动触发扩容。 扩容的具体流程很简单, 1. 首先,创建一个新的数组,这个新数组的长度是原来数组长度的 1.5 倍。 2. 然后使用 Arrays.copyOf 方法把老数组里面的数据拷贝到新的数组里面。 扩容完成后再把当前要添加的元素加入新的数组里面,从而完成动态扩容的过程。
        叶叶叶ye 2024-04-15 2
        • 你发的这个是纯文本的形式。本文只提取纯文本也是一样的意思,本文也展示了源码,能知其然并知其所以然。
          自学精灵 2024-04-15 0
          • ok谢谢站主
            叶叶叶ye 2024-04-15 0
  2. ArrayList好像没有加载因子这种说法吧,对于ArrayList而言,没有明确的“加载因子”概念,这是因为在ArrayList中并不像HashMap那样根据负载因子决定何时扩容。扩容时机取决于添加元素时实际容量是否足够。
    钟余的尽头是忠于 2024-03-21 0
    • 是的,也可以认为加载因子为1。我把这个描述添加到文中了。
      自学精灵 2024-03-21 0
显示验证码
没有账号?注册  忘记密码?

社交账号快速登录