为什么数组列表的新容量是(旧容量 * 3)/2 + 1

Question

为什么 Java ArrayList 中的 ensureCapacity（） 使用 const 1.5 或 （oldCapacity * 3）/2 + 1 扩展容量？

Answer 1

调整数组大小是一项相对昂贵的操作。它想尝试并确保如果该方法被调用 ensureCapacity(11) ， ensureCapacity(12) ， ensureCapacity(13) ， ...它不必每次都调整数组的大小。因此，它按合理的块（增加 50%）而不是指定的最小值调整大小。

Answer 2

主要原因是将一系列元素添加到列表的（渐近）复杂性。

请注意，add 方法在内部调用 ensureCapacity(size+1) 。当内部数组的大小增加时，必须将所有元素复制到新的、更大的数组中。

如果大小只增加一个常量（每次调用 add 为 1），则添加 n 个元素的复杂度为 O（n²）。

相反，大小总是增加一个恒定因子。然后，添加 n 个元素的复杂度仅为 O（n）。