使用ArrayList和HashMap遇到的一些问题(持续更新)

使用ArrayList和HashMap遇到的一些问题(持续更新)

ArrayList和HashMap是日常开发中最常用的数据结构,当我们不了解它们时,我们并不知道使用它们需要注意哪些问题,也不知道为什么会造成一些奇怪的问题,影响到程序运行的性能。在这里将记录下实际开发中遇到的相关问题,并深入源码进行分析。

使用的机器配置

名称 属性
处理器 Intel® Core™ i7-10750H CPU @ 2.60GHz 2.59 GHz
内存 16.0 GB (15.9 GB 可用)
操作系统 windows 11 专业版 21H2 64 位操作系统, 基于 x64 的处理器

ArrayList

扩容机制

在工作中实现将某个表中的数据批量导出到Excel中,由于数据量不大不小,采用了将数据存入到ArrayList中再一起写入Excel的方式。在使用ArrayList的时候,并未对ArrayList初始化其大小,而是不断循环加入到ArrayList中,导致每次addAll的时候都需要进行一次扩容操作。

实验代码

采用add方法的情况

1
2
3
4
5
6
7
int size = 100000000;
List<Integer> list = new ArrayList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
System.out.println("program spend " + (System.currentTimeMillis() - start) + " ms");

通过上述代码运行得出结果:

100000000个整型数据的情况下

  • 不设置list默认的capacity情况下的运行时间为:47368 ms
  • 设置list默认的capacity情况下的运行时间为:42079 ms

10000个整型数据的情况下

  • 不设置list默认的capacity情况下的运行时间为:2 ms
  • 设置list默认的capacity情况下的运行时间为:2 ms

采用addAll方法的情况

1
2
3
4
5
6
7
8
9
10
11
12
int size = 100000000;
List<Integer> list = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
temp.add(i);
if (i == size - 1 || i != 0 && i % 1000 == 0) {
list.addAll(temp);
temp = new ArrayList<>();
}
}
System.out.println("program spend " + (System.currentTimeMillis() - start) + " ms");

通过上述代码运行得出结果:

100000000个整型数据的情况下

  • 不设置list默认的capacity且不设置temp默认capacity的情况下的运行时间为:39070 ms
  • 设置list默认的capacity情况下且不设置temp默认capacity的运行时间为:56354 ms
  • 不设置list默认的capacity情况下且设置temp默认capacity的运行时间为:31233 ms
  • 设置list默认的capacity情况下且设置temp默认capacity的运行时间为:32205 ms

源码

经过实验后,进入到源码中看看执行addAll和add的时候,究竟发生了什么事情。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
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) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
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);
}
  • ensureExplicitCapacity:确保扩容容量充足
  • calculateCapacity:计算需要扩容的容量
  • grow:扩大容量

根据方法的调用逐层下去,我们可以看到它每次添加元素的时候会确保容量足以放下需要添加的元素数量,然后new一个新的数组,并将以前的数据拷贝到新数组中,使用新数组替代原来的数组。

根据实验情况,我们可以很容易得出,当我们在数据量小的时候,直接用add方法是没什么区别的,如果我们让list的容量一开始就初始化好,可以避免频繁的去扩容数组。因此在批量插入的时候,如果不设置temp的容量,则会产生过多的扩容操作,因此在使用ArrayList的时候尽量确保开始的时候给予足够的空间避免过多的扩容,也不能说一次性给予太大的空间,避免空间浪费。


使用ArrayList和HashMap遇到的一些问题(持续更新)
http://codebro.cn/posts/blog/The_Problem_In_Using_ArrayList_And_HashMap.html
作者
Vector
发布于
2022年8月14日
许可协议