Java容器（二）——「ArrayList、LinkedList性能测试与分析」，
分享于 点击 44382 次 点评：92
Java容器（二）——「ArrayList、LinkedList性能测试与分析」，
测试目标
集合中最常用的就是List，用于存储可重复的数据集。
为了了解List的几个实现类的性能区别以及使用场景，进行简单的性能测试对比。
我们常规对于ArrayList、LinkedList的认知是：
1. 数据查询的效率（Get的效率）
ArrayList：使用数组，获取数据通过数组下标进行快速定位，性能为O(1)，数据顺序、随机获取的速度快。
LinkedList：使用链表进行数据存储，查询数据需要从头或者从尾部遍历链表，性能O(n)，因此数组数据越多、查询位置越靠中间性能越差。
2. 数据添加的效率（Add的效率）
ArrayList：数组的数据添加，如果在头部或者中间性能最差，因为需要更改后面所有数据的位置和索引。如果在尾部性能则影响不大。
LinkedList：插入的效率比ArrayList和Vector都高，因为只需要更改相应位置前后节点的指向就行。
3. 数据移除的效率（Remove的效率）
数据移除同添加
4. 数据替换的效率（Set的效率）
ArrayList：数据替换由于不需要更改后续数组的位置和索引，因此效率比插入高。同时LinkedList需要定位位置，因此ArrayList也会比LinkedList快。
LinkedList：需要定位替换的位置，效率较低。
根据这些认知，我们可以得到假设：
1. ArrayList
不适宜应用于经常需要在集合中间或者首位进行插入或者删除操作的场景，适宜应用于读取操作多的场景。
2. LinkedList
不适宜应用于随机位置进行读取的场景，适宜于需要在集合中进行插入或者删除的场景。
测试目标：
1. 测试在头、尾进行插入的效率
2. 测试在集合中间随机位置进行随机插入的效率
3. 测试在从集合随机位置获取数据的效率
4. 测试从随机位置替换数据的效率
5. 测试随机位置的数据移除操作
测试代码
ListNature.java
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
/**
* @author lzy
* @date 2018/1/17
*/
public class ListNature extends BaseNature{
private static Logger logger = LoggerFactory.getLogger(ListNature.class);
/**
*
* @param listSize
* @param removeCount
*/
public void testRemoveRandom(int listSize, int removeCount) {
if (listSize < removeCount) {
throw new IllegalArgumentException("removeCount需要小于listSize");
}
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
testAddLast(arrayList, listSize);
System.gc();
long arrayRemove = testRemoveRandom(arrayList, removeCount);
arrayList.clear();
System.gc();
testAddLast(linkedList, listSize);
System.gc();
long linkedRemove = testRemoveRandom(linkedList, removeCount);
linkedList.clear();
System.gc();
logger.debug("于{}集合数据量下，{}次测试Array与LinkedList测试随机删除，结果如下：===",listSize,removeCount);
logger.debug("ArrayList：耗时{}",arrayRemove);
logger.debug("LinkedList：耗时{}",linkedRemove);
}
/**
*
* @param listSize
* @param replaceCount
*/
public void testReplaceRandom(int listSize, int replaceCount) {
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
testAddLast(arrayList, listSize);
long arrayReplace = testReplaceRandom(arrayList, replaceCount);
arrayList.clear();
System.gc();
testAddLast(linkedList, listSize);
long linkedReplace = testReplaceRandom(linkedList, replaceCount);
linkedList.clear();
System.gc();
logger.debug("于{}集合数据量下，{}次测试Array与LinkedList测试随机替换，结果如下：===",listSize,replaceCount);
logger.debug("ArrayList：耗时{}",arrayReplace);
logger.debug("LinkedList：耗时{}",linkedReplace);
}
/**
* 测试ArrayList和LinkedList集合随机获取数据的效率
*
* @param listSize 集合原始容量
* @param getCount 获取次数
*/
public void testGetRandom(int listSize, int getCount) {
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
testAddLast(arrayList, listSize);
long arrayGet= testGetRandom(arrayList, getCount);
arrayList.clear();
System.gc();
testAddLast(linkedList, listSize);
long linkedGet = testGetRandom(linkedList, getCount);
linkedList.clear();
System.gc();
logger.debug("于{}集合数据量下，{}次测试Array与LinkedList测试随机获取，结果如下：===",listSize,getCount);
logger.debug("ArrayList：耗时{}",arrayGet);
logger.debug("LinkedList：耗时{}",linkedGet);
}
/**
* 测试ArrayList和LinkedList集合中随机插入数据的效率
*
* @param listSize 数组原始容量
* @param insertCount 插入次数
*/
public void testInsertRandom(int listSize, int insertCount) {
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
testAddLast(arrayList, listSize);
long arrayInsert = testInsertRandom(arrayList, insertCount);
arrayList.clear();
System.gc();
testAddLast(linkedList, listSize);
long linkedInsert = testInsertRandom(linkedList, insertCount);
linkedList.clear();
System.gc();
logger.debug("于{}集合数据量下，{}次测试Array与LinkedList测试随机添加，结果如下：===",listSize,insertCount);
logger.debug("ArrayList：耗时{}",arrayInsert);
logger.debug("LinkedList：耗时{}",linkedInsert);
}
/**
* 测试ArrayList和LinkedList集合中首尾插入数据的效率
*
* @param addCount 插入次数
*/
public void testAddFirstAndLast(int addCount) {
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
long arrayListAddFirst = testAddFirst(arrayList, addCount);
System.gc();
long arrayListAddLast = testAddLast(arrayList, addCount);
arrayList.clear();
System.gc();
long linkedListAddFirst = testAddFirst(linkedList, addCount);
System.gc();
long linkedListAddLast = testAddLast(linkedList, addCount);
linkedList.clear();
System.gc();
logger.debug("{}次测试Array与LinkedList测试头尾添加，结果如下：===",addCount);
logger.debug("ArrayList：头部添加耗时{},尾部添加耗时{}",arrayListAddFirst,arrayListAddLast);
logger.debug("LinkedList：头部添加耗时{},尾部添加耗时{}",linkedListAddFirst,linkedListAddLast);
}
private long testAddFirst(List list, int addCount) {
int[] array = getRandomArray(addCount);
long time1 = System.currentTimeMillis();
for (int i = 0; i < addCount; i++) {
list.add(0, array[i]);
}
long time2 = System.currentTimeMillis();
long interval = time2 - time1;
return interval;
}
private long testAddLast(List list, int addCount) {
int[] array = getRandomArray(addCount);
long time1 = System.currentTimeMillis();
for (int i = 0; i < addCount; i++) {
list.add(array[i]);
}
long time2 = System.currentTimeMillis();
long interval = time2 - time1;
return interval;
}
private long testInsertRandom(List list, int insertCount) {
int[] array = getRandomArray(insertCount, list.size());
long time1 = System.currentTimeMillis();
for (int i = 0; i < insertCount; i++) {
list.add(array[i], array[i]);
}
long time2 = System.currentTimeMillis();
long interval = time2 - time1;
return interval;
}
private long testReplaceRandom(List list, int replaceCount) {
int[] array = getRandomArray(replaceCount, list.size());
long time1 = System.currentTimeMillis();
for (int i = 0; i < replaceCount; i++) {
list.set(array[i], array[i]);
}
long time2 = System.currentTimeMillis();
long interval = time2 - time1;
return interval;
}
private long testGetRandom(List list, int getCount) {
int[] array = getRandomArray(getCount, list.size());
long time1 = System.currentTimeMillis();
for (int i = 0; i < getCount; i++) {
list.get(array[i]);
}
long time2 = System.currentTimeMillis();
long interval = time2 - time1;
return interval;
}
private long testRemoveRandom(List list, int removeCount) {
int[] array = getRandomArray(removeCount, list.size() / 100);
long time1 = System.currentTimeMillis();
for (int i = 0; i < removeCount; i++) {
list.remove(array[i]);
}
long time2 = System.currentTimeMillis();
long interval = time2 - time1;
return interval;
}
}ListNatureTest.java
import org.junit.Test;
/**
* @author lzy
* @date 2018/1/18
*/
public class ListNatureTest {
@Test
public void testAdd() {
int[] testCount = {10000, 50000,100000};
ListNature natureTest = new ListNature();
for (int i : testCount) {
natureTest.testAddFirstAndLast(i);
}
}
@Test
public void testInsert() {
int[] testCount = {10000, 50000,100000};
int[] listSize = {10000, 50000,100000};
ListNature natureTest = new ListNature();
for (int i : testCount) {
for (int j : listSize) {
natureTest.testInsertRandom(j, i);
}
}
}
@Test
public void testGet() {
int[] testCount = {10000, 50000,100000};
int[] listSize = {10000, 50000,100000};
ListNature natureTest = new ListNature();
for (int i : testCount) {
for (int j : listSize) {
natureTest.testGetRandom(j, i);
}
}
}
@Test
public void testReplace() {
int[] testCount = {10000, 50000,100000};
int[] listSize = {10000, 50000,100000};
ListNature natureTest = new ListNature();
for (int i : testCount) {
for (int j : listSize) {
natureTest.testReplaceRandom(j, i);
}
}
}
@Test
public void testRemove() {
int[] testCount = {10000, 50000};
int[] listSize = {100000,200000};
ListNature natureTest = new ListNature();
for (int i : testCount) {
for (int j : listSize) {
natureTest.testRemoveRandom(j, i);
}
}
}
}测试结果
测试的结果影响因素很多，但是我们主要是定性测试，因此不要纠结于具体的时间毫秒数，而是要了解每个组件的性能趋势。
1.查询测试
数据的查询考虑的是查询次数以及数组长度两个维度，因此各自使用1w、5w、10w三种测试场景，单位毫秒(ms)。
A：ArrayList
L：LinkedList
| 测试次数 | A(1w) | L(1w) | A(5w) | L(5w) | A (10w) | L(10w) |
|---|---|---|---|---|---|---|
| 1w | 1 | 99 | 1 | 552 | 1 | 1156 |
| 5w | 1 | 285 | 1 | 1649 | 1 | 6133 |
| 10w | 1 | 1079 | 1 | 4773 | 1 | 11421 |
2.添加测试
A首：ArrayList首位添加
L首：LinkedList首位添加
A尾：ArrayList的尾部添加
L尾：LinkedList的尾部添加
结果1：
| 测试次数 | A首(ms) | L首(ms) | A尾(ms) | L尾(ms) |
|---|---|---|---|---|
| 1w次 | 15 | 4 | 1 | 2 |
| 5w次 | 210 | 6 | 4 | 2 |
| 10w次 | 899 | 2 | 8 | 1 |
测试在数组中随机插入，主要需要考虑数组的原本的长度，因此取三个较大的数组长度的放大两者之间的差距1w、10w、100w
A中：在N条数据内的随机插入，ArrayList的中间随机插入
L中：LinkedList的中间随机插入
结果2：
| 测试次数 | A中(1w) | L中(1w) | A中(5w) | L中(5w) | A中 (10w) | L中(10w) |
|---|---|---|---|---|---|---|
| 1w次 | 19 | 480 | 51 | 1734 | 92 | 1685 |
| 5w次 | 222 | 4523 | 307 | 13740 | 687 | 21928 |
| 10w次 | 935 | 9287 | 1676 | 49533 | 2648 | 82517 |
3.删除测试
原计划是分队列头部、尾部、随机位置三个场景测试，考虑到头部删除、尾部删除于头尾插入类似，因此只需要测试随机位置删除即可。测试需要考虑数组的原本的长度以及删除的数据数量，即删除数量需要大于数组原本长度。因此测试数据量为10w、100w
| 测试次数 | A(10w) | L(10w) | A (20w) | L(20w) |
|---|---|---|---|---|
| 1w次 | 105 | 17 | 216 | 34 |
| 5w次 | 349 | 79 | 949 | 211 |
4.替换测试
直接上替换测试结果：
| 测试次数 | A(1w) | L(1w) | A(5w) | L(5w) | A (10w) | L(10w) |
|---|---|---|---|---|---|---|
| 1w次 | 3 | 81 | 1 | 308 | 1 | 742 |
| 5w次 | 2 | 337 | 1 | 2160 | 1 | 4792 |
| 10w次 | 1 | 831 | 4 | 4818 | 1 | 10023 |
测试结果分析
从测试结果反应的时间来看，可以得到以下几点结论：
源码分析
1. Get对比
ArrayList的get非常简单，伴随着一个数组范围检查后直接是范围相应位置的元素，非常的简单高效。
public E get(int index) {
//判断 index<size,否则抛出IndexOutOfBoundsException
rangeCheck(index);
return elementData(index);
}LinkedList的get通过链表的头或者尾进行遍历，直到找到index位置的对象。
public E get(int index) {
//判断index>=0&&index<size，否则抛出IndexOutOfBoundsException
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}从两者的Get实现角度看，集合中元素的数量对于ArrayList的获取性能影响不大，性能比较稳定。而LinkedList的效率则关乎获取元素的位置，离集合的头或尾越近，性能越好，反之则越差。
2.Add对比
ArrayList 在顺序插入时,如果数据容量不够,会经常扩容,其中扩容代码Arrays.copyOf(elementData, newCapacity); 会消耗大量时间,但如果数据量较大,此时扩容次数明显下降(扩容总是会在当前容量的1.5倍),因此扩容消耗的时间平均下来明显降低。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//扩容判断
private void ensureExplicitCapacity(int minCapacity) {
//用于Fail-Fast判断
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 新的数组长度为原数组的长度*1.5，若是小于最小长度则赋值为最小长度。若大于最大长度（Integer.MAX_VALUE-8），则赋值为Integer.MAX_VALUE
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);
}LinkedList 顺序插入，先新增一个前节点，绑定前一节点为last，最后把新增节点置为last。
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}3. add(int index, E element)中间插入对比
ArrayList需要进行数组拷贝，把index位置之后的元素整体后移一位，如果数组较长且index位置靠前（即index之后元素较多），会浪费大量时间,因此插入时间会呈指数级增长。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}LinkedList的数据插入，主要消耗在index位置的链表定位上，index位置的查找速度越快，则插入速度越快。
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}remove也是同理，ArrayList主要是拷贝，LinkedList主要是定位。
set对于ArrayList同get，而LinkedList主要是定位。
综合以上各项数据,对于两个集合使用有以下建议：
1、大部分的情况下使用ArrayList即可
2、在数组长度能够确定的情况下，使用ArrayList更优，避免了数组扩容
3、频繁添加删除(在 list 开始部分)，但不需要频繁访问，可以考虑使用LinkedList
4、分不清场景下需要使用哪一种的，建议结合着业务做一下测试。
相关文章
- 暂无相关文章
用户点评