Java 集合扩容
xiantang
·
2018-12-07
·
via 咸糖 - 自律者自由
【注意】最后更新于 December 29, 2025，文中内容可能已过时，请谨慎使用。
集合扩容
ArrayList
对于 ArrayList 他默认的容量为 10，所以如果需要对 ArrayList 进行大数据量的处理的时候的话，就需要使用显式制定容量的方式进行处理。这样可以减少不必要的扩容操作。
主要是因为 ArrayList 的扩容操作需要额外开辟空间，他采用的是 Arrays.copyOf 的方式进行拷贝：
1
2
3
4
5
6
7
8
9
10
11
|
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);
}
|
Arrays.copyOf 的方式是采用开辟空间再复制的方式，很有可能会造成 OOM。
HashMap
HashMap 的默认容量为 16，并且他的容量一定是 2 的幂。
如果指定的容量不是 2 次幂，他也会求出距离当前容量最近的 2 次幂。
1
2
3
4
5
6
7
8
9
10
11
12
|
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
|
至于为什么是 2 的幂，是因为 SUN 的大师们发现，让容量为 2^n 时候，(length - 1) & hash 快于模运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
@Test
public void testModAndWith() {
long currentTimeMillis = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
int i1 = 6666 % 16;
assertEquals(10, i1);
}
long l = System.currentTimeMillis() - currentTimeMillis;
System.out.println("使用%时间: " + l);
long currentTimeMillis1 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
int i1 = 6666 & (16-1);
assertEquals(10, i1);
}
long l1 = System.currentTimeMillis() - currentTimeMillis1;
System.out.println("使用&时间: " + l1);
}
|
使用%时间：16
使用&时间：9
我们以 length 为 16 为例
当我们的 hash 为17时
原因是因为 16 - 1 的二进制为 01111 并且 17 的二进制为 1 0001
我们只需要计算低位，高位全部舍弃，低位进行 & 运算，得出结果是 1 与 17 % 16 的结果完全相同。
赞赏支持
微信打赏
支付宝打赏
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
