ArrayList底层是数组elementData,用来存放插入的数据。初始大小0,有数据插入时,默认大小DEFAULT_CAPACITY = 10。

什么时候扩容

当插入数据,导致size+1>elementData.length时,开始扩容。(就是存不下了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! // add一个元素时,size + 1
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private static int calculateCapacity(Object[] elementData, int minCapacity) { // 计算新容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 代表elementData数组还是一个空数组,没有任何数据
return Math.max(DEFAULT_CAPACITY, minCapacity); // elementData为空时,会扩容到DEFAULT_CAPACITY = 10和minCapacity的最大值,而minCapacity在插入数据时第一次值为1(size + 1 = 1),会扩容为10
}
return minCapacity;
}

如何扩容?

新数组容量为旧数组的1.5倍:newCapacity = 1.5 * oldCapacity ,并且将旧数组内容通过Array.copyOf全部复制到新数组。此时,size还未真正+1,新旧数组长度(size一致),不过容量不同。
把这里的系数1.5,称作扩容因子k = newCapacity / oldCapacity。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}

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

扩容因子为何是1.5?

扩容因子最合适的范围为(1,2)。

当扩容因子 k = 2 时,每次扩容后的容量刚好大于之前分配的总和:

也就是说,之前分配的内存空间不可能被使用。这样对缓存不友好。因此,扩容因子最合适的范围为(1,2)。

下面举一组 k = 2, k = 1.5 的对比例子。当然容量 c 不可能为 4,这里只是为了方便说明

1
2
3
4
5
6
7
8
9
10
11
k = 2, c = 4
0123
01234567
0123456789ABCDEF
0123456789A...
k = 1.5,c = 4
0123
012345
012345678
<--(0123456789ABC)
0123456789ABC

可以看到,k = 1.5 在几次扩容后,可以重用之前的空间。

为什么不是1.2、1.7呢

因为 1.5 可以充分利用移位操作,减少运算时间和运算次数。

1
2
// 新容量计算
int newCapacity = oldCapacity + (oldCapacity >> 1);

哪为什么 HashMap 扩容因子是 2 呢?

为了方便计算,HashMap 的容量必须为 2 的次幂,默认 16。

  1. HashMap 向集合添加元素时,会使用(n-1) & hash的计算方法来得到该元素在集合中的位置。
  2. HashMap 在扩容时会使用hash & oldCap是否等 0 的比较,来决定该元素在扩容后的数组中的位置。==0:在原位置, ==1:在原位置+oldCap

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题 鲁ICP备-20012065号