ArrayList--扩容的原理

深藏阁楼爱情的钟 2022-09-17 03:05 253阅读 0赞

原文网址：[ArrayList--扩容的原理\_IT利刃出鞘的博客-CSDN博客][ArrayList--_IT_-CSDN]

# 简介 #

本文介绍Java的ArrayList是如何进行扩容的。

# 扩容机制 #

**重要大小**

<table> 
 <tbody> 
 <tr> 
 <td> Class </td> 
 <td> 初始大小 </td> 
 <td> 加载因子 </td> 
 <td> 扩容倍数 </td> 
 <td> 底层实现 </td> 
 <td> 是否线程安全 </td> 
 <td> 同步方式 </td> 
 </tr> 
 <tr> 
 <td> ArrayList </td> 
 <td> 10 </td> 
 <td> 1 </td> 
 <td> 1.5倍 </td> 
 <td> Object数组 </td> 
 <td> 线程不安全 </td> 
 <td> 无 </td> 
 </tr> 
 <tr> 
 <td> Vector </td> 
 <td> 10 </td> 
 <td> 1 </td> 
 <td> 2倍 </td> 
 <td> Object数组 </td> 
 <td> 线程安全 </td> 
 <td> synchronized </td> 
 </tr> 
 </tbody> 
</table>

**流程**

（1）直接new 一个ArrayList对象时（未指定初始容量大小）是一个空的数组，容量大小为零。

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

（2）当第一次调用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);
 }
 
 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;
 }

# **其他网址** #

[ArrayList扩容机制。\_a1275118943的博客-CSDN博客][ArrayList_a1275118943_-CSDN]

[ArrayList--_IT_-CSDN]: https://knife.blog.csdn.net/article/details/120944429
[ArrayList_a1275118943_-CSDN]: https://blog.csdn.net/a1275118943/article/details/88769460