ArrayList vs. LinkedList vs. HashMap in Java – 阵列表与链接表的对比与Java中的HashMap的对比

最后修改: 2020年 12月 13日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

Collections in Java are based on a couple of core interfaces and more than a dozen implementation classes. The wide selection of different implementations can sometimes lead to confusion.

Java中的集合是基于几个核心接口和十几个实现类。不同实现的广泛选择有时会导致混乱。

Deciding on which collection type to use for a particular use case is not a trivial task. That decision can have a great impact on our code readability and performance.

决定在特定的用例中使用哪种集合类型并不是一件微不足道的事情。这一决定会对我们的代码可读性和性能产生很大影响。。

Instead of explaining all types of collections in a single article, we’ll explain three of the most common ones: ArrayList, LinkedList, and HashMap. In this tutorial, we’ll look at how they store data, their performance, and recommend when to use them.

我们不会在一篇文章中解释所有类型的集合，而是解释三种最常见的集合。ArrayList、LinkedList、和HashMap。在本教程中，我们将探讨它们如何存储数据，它们的性能，并推荐何时使用它们。

2. Collections

2.收藏

A collection is simply a Java object that groups other objects together. The Java Collections Framework contains a set of data structures and algorithms for representing and manipulating collections. If applied correctly, the provided data structures help reduce programming effort and increase performance.

集合是一个简单的Java对象，它将其他对象组合在一起。 Java 集合框架包含一组数据结构和算法，用于表示和操作集合。如果应用得当，所提供的数据结构有助于减少编程工作并提高性能。

2.1. Interfaces

2.1.接口

The Java Collections Framework contains four basic interfaces: List, Set, Map, and Queue. It is important to understand the intended usage of these interfaces before looking at the implementation classes.

Java集合框架包含四个基本接口。List、Set、Map和Queue。在查看实现类之前，了解这些接口的预期用途是很重要的。

Let’s have a quick look at three of the four core interfaces that we’ll use in this article:

让我们快速浏览一下本文将使用的四个核心界面中的三个。

  • The List interface is dedicated to storing ordered collections of objects. It allows us to positionally access and inserts new elements, as well as save duplicate values
  • The Map interface supports a key-value pair mapping of the data. To access a certain value, we need to know its unique key
  • The Queue interface enables the storage of data based on the first-in-first-out order. Similar to a real-world queue line

HashMap implements the Map interface. The List interface is implemented by both ArrayList and LinkedList. LinkedList additionally implements the Queue interface.

HashMap 实现了Map界面。List接口由ArrayList 和LinkedList实现。LinkedList另外还实现了Queue接口。

2.2. List vs. Map

2.2. List与Map的比较

A common antipattern we sometimes encounter is trying to maintain order using a map. Thus, not making use of other collection types more suitable for the job.

我们有时会遇到一个常见的反模式，就是试图用地图来维持秩序。因此，没有利用其他更适合这项工作的集合类型。

Just because we can solve many problems with a single collection type doesn’t mean we should.

我们可以用一个单一的集合类型来解决许多问题，但这并不意味着我们应该这样做。

Let’s look at a bad example, where we use a map to save data based on the positional key:

让我们看看一个不好的例子，我们使用一个地图来保存基于位置键的数据。

Map<Integer, String> map = new HashMap<>();
map.put(1, "Daniel");
map.put(2, "Marko");
for (String name : map.values()) {
    assertThat(name).isIn(map.values());
}
assertThat(map.values()).containsExactlyInAnyOrder("Daniel", "Marko");

When we iterate through the map values, we’re not guaranteed to retrieve them in the same order we put them in. That is simply because a map wasn’t designed for maintaining the order of elements.

当我们遍历地图的值时，我们不能保证以相同的顺序检索它们。这只是因为地图的设计并不是为了保持元素的顺序。

We can rewrite this example in a much more readable way using a list. Lists are ordered by definition, so we can iterate through the items in the same order that we inserted them:

我们可以用一个列表的方式来重写这个例子，这样可读性更强。列表根据定义是有序的，所以我们可以按照插入项目的顺序来迭代。

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add("Marko");
for (String name : list) {
    assertThat(name).isIn(list);
}
assertThat(list).containsExactly("Daniel", "Marko");

Maps are designed for quick access and search based on unique keys. When we want to maintain order or work with position-based indexes, lists are a natural choice.

Maps是为快速访问和基于唯一键的搜索而设计的。当我们想保持秩序或使用基于位置的索引时，列表是一个自然的选择。

3. ArrayList

3.数组列表

ArrayList is the most commonly used implementation of the List interface in Java. It is based on built-in arrays but can dynamically grow and shrink as we add or remove elements.

ArrayList是Java中最常用的List接口的实现。它基于内置的数组，但可以在我们添加或删除元素时动态地增长和缩小。

We use indexes that start from zero to access list elements. We can insert a new element either at the end, or the specific position of the list:

我们使用从零开始的索引来访问列表元素。我们可以在列表的末尾或特定位置插入一个新元素。

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add(0, "Marko");
assertThat(list).hasSize(2);
assertThat(list.get(0)).isEqualTo("Marko");

To remove an element from the list, we need to provide the object reference or its index:

要从列表中删除一个元素，我们需要提供对象的引用或其索引。

List<String> list = new ArrayList<>(Arrays.asList("Daniel", "Marko"));
list.remove(1);
assertThat(list).hasSize(1);
assertThat(list).doesNotContain("Marko");

3.1. Performance

3.1. 性能

ArrayList provides us with dynamic arrays in Java. Although slower than the built-in arrays, ArrayList helps us save some programming effort and improve code readability.

ArrayList为我们提供了Java中的动态数组。虽然比内置数组慢，但ArrayList可以帮助我们节省一些编程的精力，并提高代码的可读性。

When we talk about time complexity, we make use of the Big-O notation. The notation describes how the time to perform the algorithm grows with the size of the input.

当我们谈论时间复杂性时，我们使用了Big-O符号。该符号描述了执行算法的时间是如何随着输入的大小而增长的。

ArrayList allows random access since arrays are based on indexes. That means that accessing any element always takes a constant time O(1).

ArrayList允许随机访问，因为数组是基于索引的。这意味着访问任何元素总是需要一个恒定的时间O(1)。

Adding new elements also takes O(1) time, except when adding an element on a specific position/index, then it takes O(n). Checking if a specific element exists in the given list runs in linear O(n) time.

添加新元素也需要O(1)时间，除了在特定位置/索引上添加元素时，则需要O(n)。检查一个特定的元素是否存在于给定的列表中，运行的时间是线性的O(n)。

The same is true for the removal of elements. We need to iterate the entire array to find the element selected for removal.

移除元素的情况也是如此。我们需要遍历整个数组，以找到被选中要删除的元素。

3.2. Usage

3.2.使用方法

Whenever we’re unsure what collection type to use, it’s probably a good idea to start with an ArrayList. Keep in mind that accessing items based on indexes will be very fast. However, searching for items based on their value or adding/removing items at a specific position will be expensive.

每当我们不确定使用哪种集合类型时，从ArrayList开始可能是个好主意。请记住，基于索引访问项目的速度将非常快。然而，根据项目的值搜索项目或在特定位置添加/删除项目将是昂贵的。

Using ArrayList makes sense when it is important to maintain the same order of items, and quick access time based on the position/index is an important criterion.

当需要保持项目的相同顺序，并且基于位置/索引的快速访问时间是一个重要标准时，使用ArrayList 是有意义的。

Avoid using ArrayList when the order of items is not important. Also, try to avoid it when items often need to be added to a specific position. Likewise, bear in mind that ArrayList may not be the best option when searching for specific item values is an important requirement, especially if the list is large.

当项目的顺序不重要时，避免使用ArrayList。另外，当项目经常需要被添加到一个特定的位置时，尽量避免使用它。同样，请记住，当搜索特定的项目值是一个重要的要求时，ArrayList可能不是最好的选择，特别是当列表很大时。

4. LinkedList

4.LinkedList

LinkedList is a doubly-linked list implementation. Implementing both the List and Deque (an extension of Queue) interfaces. Unlike ArrayList, when we store data in a LinkedList, every element maintains a link to the previous one.

LinkedList是一个双重链接的列表实现。它同时实现了List和Deque（Queue的扩展）接口。与 ArrayList 不同，当我们在 LinkedList 中存储数据时，每个元素都保持着与前一个元素的链接。

Besides standard List insertion methods, LinkedList supports additional methods that can add an element at the beginning or the end of the list:

除了标准的List插入方法，LinkedList支持额外的方法，可以在列表的开头或结尾添加一个元素。

LinkedList<String> list = new LinkedList<>();
list.addLast("Daniel");
list.addFirst("Marko");
assertThat(list).hasSize(2);
assertThat(list.getLast()).isEqualTo("Daniel");

This list implementation also offers methods for removing elements from the beginning or at the end of the list:

这个列表的实现还提供了从列表的开头或结尾删除元素的方法。

LinkedList<String> list = new LinkedList<>(Arrays.asList("Daniel", "Marko", "David"));
list.removeFirst();
list.removeLast();
assertThat(list).hasSize(1);
assertThat(list).containsExactly("Marko");

The implemented Deque interface provides queue-like methods for retrieving, adding, and deleting elements:

实现的Deque接口为检索、添加和删除元素提供类似队列的方法。

LinkedList<String> list = new LinkedList<>();
list.push("Daniel");
list.push("Marko");
assertThat(list.poll()).isEqualTo("Marko");
assertThat(list).hasSize(1);

4.1. Performance

4.1.业绩

A LinkedList consumes a bit more memory than an ArrayList since every node stores two references to the previous and next element.

LinkedList比ArrayList消耗更多的内存，因为每个节点都存储了对上一个和下一个元素的两个引用。

The insertion, addition, and removal operations are faster in a LinkedList because there is no resizing of an array done in the background. When a new item is added somewhere in the middle of the list, only references in surrounding elements need to change.

在LinkedList中，插入、添加和删除的操作更快，因为在后台没有对数组进行大小调整。当一个新的项目被添加到列表的中间位置时，只有周围元素的引用需要改变。

LinkedList supports O(1) constant-time insertion at any position in the collection. However, it is less efficient at accessing items in a specific position, taking O(n) time.

LinkedList支持O(1)在集合的任何位置进行恒定时间插入。然而，它在访问特定位置的项目时效率较低，需要O(n) 时间。

Removing an element also takes O(1) constant-time, since we just need to modify a few pointers. Checking if a specific element exists in the given list takes O(n) linear time, same as for an ArrayList.

删除一个元素也需要O(1)恒定时间，因为我们只需要修改几个指针。检查一个特定的元素是否存在于给定的列表中需要O(n)线性时间，与ArrayList.相同。

4.2. Usage

4.2.使用情况

Most of the time we can use ArrayList as the default List implementation. However, in certain use-cases, we should make use of LinkedList. Those include when we prefer constant insertion and deletion time, over constant access time, and effective memory usage.

大多数时候，我们可以使用ArrayList作为默认的List实现。然而，在某些使用情况下，我们应该使用LinkedList。这些情况包括我们更喜欢恒定的插入和删除时间，而不是恒定的访问时间，以及有效的内存使用。

Using LinkedList makes sense when maintaining the same order of items and quick insertion time (adding and removing items at any position) is an important criterion.

当保持项目的相同顺序和快速插入时间（在任何位置添加和删除项目）是一个重要标准时，使用LinkedList是有意义的。

Like an ArrayList, we should avoid using LinkedList when the order of items is not important. LinkedList is not the best option when fast access time or searching for items is an important requirement.

与ArrayList一样，当项目的顺序不重要时，我们应该避免使用LinkedList。当快速访问时间或搜索项目是一个重要的要求时，LinkedList并不是最佳选择。

5. HashMap

5、HashMap

Unlike ArrayList and LinkedList, HashMap implements the Map interface. That means that every key is mapped to exactly one value. We always need to know the key to retrieve the corresponding value from the collection:

与ArrayList和LinkedList不同，HashMap实现了Map接口。这意味着每个键都被精确地映射到一个值。我们总是需要知道键才能从集合中检索到相应的值。

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
assertThat(map.get("654321")).isEqualTo("Marko");

Similarly, we can only delete a value from the collection using its key:

同样地，我们只能用它的键从集合中删除一个值。

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
map.remove("654321");
assertThat(map).hasSize(1);

5.1. Performance

5.1.业绩

One might ask, why not simply use a List and get rid of the keys all together? Especially since HashMap consumes more memory for saving keys and its entries are not ordered. The answer lies in the performance benefits for searching elements.

有人可能会问，为什么不简单地使用一个List，而把键全部去掉呢？特别是由于HashMap在保存键值时消耗了更多的内存，而且它的条目是没有顺序的。答案就在于搜索元素的性能优势。

HashMap is very efficient at checking if a key exists or retrieving a value based on a key. Those operations take O(1) on average.

HashMap在检查一个键是否存在或基于一个键检索一个值方面非常高效。这些操作平均需要O(1)。

Adding and removing elements from a HashMap based on a key takes O(1) constant-time. Checking for an element without knowing the key takes linear time O(n), as it’s necessary to loop over all the elements.

从基于键的 HashMap 中添加和删除元素需要O(1)恒定时间。在不知道键的情况下检查一个元素需要线性时间O(n)，因为有必要在所有元素上循环。

5.2. Usage

5.2.使用情况

Along with ArrayList, HashMap is one of the most frequently used data structures in Java. Unlike different list implementations, HashMap makes use of indexing to perform a jump to a specific value, making the search time constant, even for large collections.

与ArrayList一起，HashMap是Java中最常用的数据结构之一。与不同的列表实现不同，HashMap利用索引来执行对特定值的跳转，使得搜索时间不变，即使是大型集合。

Using HashMap makes sense only when unique keys are available for the data we want to store. We should use it when searching for items based on a key and quick access time is an important requirement.

只有当我们想要存储的数据有唯一的键时，使用HashMap才有意义。当根据一个键来搜索项目并且快速访问时间是一个重要的要求时，我们应该使用它。

We should avoid using HashMap when it is important to maintain the same order of items in a collection.

当需要保持集合中项目的相同顺序时，我们应该避免使用HashMap。

6. Conclusion

6.结语

In this article, we explored three common collection types in Java: ArrayList, LinkedList, and HashMap. We looked at their performance for adding, removing, and searching for items. Based on that, we provided recommendations on when to apply each of them in our Java applications.

在这篇文章中，我们探讨了Java中三种常见的集合类型。ArrayList、LinkedList、和HashMap。我们考察了它们在添加、删除和搜索项目方面的性能。在此基础上，我们就何时在我们的 Java 应用程序中应用它们提出了建议。

In the examples, we covered only basic methods for adding and removing items. For a more detailed look at each implementation API, please visit our dedicated ArrayList, ArrayList, and HashMap articles.

在这些例子中，我们只涉及了添加和删除项目的基本方法。要想更详细地了解每个实现的API，请访问我们专门的ArrayList, ArrayList，和HashMap文章。

As always, the complete source code is available over on GitHub.

一如既往，完整的源代码可在GitHub上获得，。