Java中的Arraylist、Linkedlist与Hashmap

1. 概述

Java 中的集合基于几个核心接口和十几个实现类。不同实现的广泛选择有时会导致混乱。 决定为特定用例使用哪种集合类型并非易事。这个决定会对我们的代码可读性和性能产生很大影响。 我们不会在一篇文章中解释所有类型的集合，而是解释三个最常见的集合：ArrayList、LinkedList和*HashMap。*在本教程中，我们将了解它们如何存储数据、它们的性能，并推荐何时使用它们。

2. Collections

集合只是将其他对象组合在一起的 Java 对象。*Java Collections Framework *包含一组用于表示和操作集合的数据结构和算法。如果应用正确，所提供的数据结构有助于减少编程工作并提高性能。

2.1. 接口

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

让我们快速浏览一下我们将在本文中使用的四个核心接口中的三个：

• List接口专用于存储有序的对象集合。它允许我们按位置访问和插入新元素，以及保存重复值
• Map接口支持数据的键值对映射。要访问某个值，我们需要知道它的唯一键
• Queue接口支持按照先进先出的顺序存储数据。类似于真实世界的队列

HashMap 实现了Map接口。List接口由ArrayList 和 LinkedList 实现。LinkedList还实现了 Queue接口。

2.2. List与Map

我们有时会遇到的一个常见反模式是尝试使用地图来维护秩序。因此，不使用更适合该工作的其他集合类型。

仅仅因为我们可以用一种集合类型解决许多问题并不意味着我们应该这样做。

让我们看一个不好的例子，我们使用地图根据位置键保存数据：

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");

当我们遍历映射值时，我们不能保证按照放入它们的顺序检索它们。这仅仅是因为映射不是为维护元素的顺序而设计的。

我们可以使用列表以更易读的方式重写此示例。List是按定义排序的，因此我们可以按照插入它们的相同顺序遍历项目：

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

地图专为基于唯一键的快速访问和搜索而设计。当我们想要维护顺序或使用基于位置的索引时，列表是自然的选择。

3. ArrayList

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

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

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

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

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

3.1. 表现

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

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

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

添加新元素也需要O(1)时间，除非在特定位置/索引上添加元素，然后需要O(n)。检查给定列表中是否存在特定元素以线性*O(n)*时间运行。

删除元素也是如此。我们需要迭代整个数组以找到选择要删除的元素。

3.2. 用法

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

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

当项目的顺序不重要时，避免使用ArrayList。此外，当经常需要将项目添加到特定位置时，请尽量避免它。同样，请记住，当搜索特定项目值是一项重要要求时，ArrayList可能不是最佳选择，尤其是在列表很大的情况下。

4. LinkedList

LinkedList是一个双向链表实现。实现List和Deque（**队列的扩展）**接口。与ArrayList不同，当我们将数据存储在LinkedList中时，每个元素都维护到前一个元素的链接。

除了标准的List插入方法外，LinkedList还支持可以在列表末尾的开头添加元素的其他方法：

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

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

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

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

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

4.1.表现

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

LinkedList中的插入、添加和删除操作更快，因为没有在后台完成数组的大小调整。当在列表中间的某处添加新项目时，只有周围元素中的引用需要更改。

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

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

4.2. 用法

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

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

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

5. HashMap

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

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

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

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

5.1. 表现

有人可能会问，为什么不简单地使用List并一起摆脱键？特别是因为HashMap会消耗更多内存来保存键，并且它的条目没有排序。答案在于搜索元素的性能优势。

HashMap在检查键是否存在或根据键检索值方面非常有效。这些操作平均需要O(1)。**

基于键在HashMap中添加和删除元素需要O(1)常量时间。在不知道键的情况下检查元素需要线性时间O(n)，因为有必要遍历所有元素。

5.2. 用法

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

仅当我们要存储的数据有唯一键可用时，使用HashMap才有意义。我们应该在基于密钥搜索项目时使用它，快速访问时间是一个重要要求。

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