Java HashMap 与 ArrayList 的性能我是否正确

HashMap vs ArrayList performance am I correct

提问by Ankur

I currently believe that:

我目前认为：

• When you need a structure from which you will be retrieving items randomly - use a HashMap
• When you will be retrieving items in order (e.g. using a for loop) - use an ArrayList

• 当您需要一个从中随机检索项目的结构时 - 使用 HashMap
• 当您按顺序检索项目时（例如使用 for 循环） - 使用 ArrayList

Am I generally correct? Are there situations where this is not correct?

我一般正确吗？是否存在不正确的情况？

采纳答案by harto

Generally, yes, you are correct. There's also a combined data structure, the LinkedHashMap, which offers fast access to arbitrary elements as well as predictable ordering.

一般来说，是的，你是对的。还有一个组合数据结构LinkedHashMap，它提供对任意元素的快速访问以及可预测的排序。

However, it's worth noting that ArrayList and HashMap are only two implementations of the List and Map interfaces, respectively. There are other implementations of each that might be more suitable for more specific requirements. For example, a LinkedList might provide higher performance than an ArrayList for certain queueing/dequeueing requirements.

但是，值得注意的是，ArrayList 和 HashMap 分别只是 List 和 Map 接口的两种实现。每个都有其他实现可能更适合更具体的要求。例如，对于某些排队/出队要求，LinkedList 可能提供比 ArrayList 更高的性能。

回答by dan gibson

For me, it's more whether I care about the ordering of the items in the collection. If you do care about the order then use the ArrayList. If you don't care about the order (you just want to store a bunch of items) then you can use a HashMap.

对我来说，更重要的是我是否关心集合中项目的排序。如果您确实关心顺序，请使用 ArrayList。如果您不关心订单（您只想存储一堆项目），那么您可以使用 HashMap。

回答by CPerkins

I'd disagree slightly. For me it depends more on how I want to retrieve the items. If I want to do so based on something like their order (by index, to be precise) I would tend to use a linear structure like an ArrayList (or even an array). If I need to look up items, I'd use a map structure like the HashMap.

我有点不同意。对我来说，这更多地取决于我想如何检索项目。如果我想根据它们的顺序（准确地说是按索引）来这样做，我会倾向于使用线性结构，例如 ArrayList（甚至是数组）。如果我需要查找项目，我会使用像 HashMap 这样的地图结构。

Another complicating factor has to do with insertions and order, as dan pointed out.

正如 dan 指出的那样，另一个复杂因素与插入和顺序有关。

回答by Kendall Helmstetter Gelner

Don't forget it's also much faster to get to one specific item with a map (if you have the key) than it is from an array (unless you have an index, but a key will always get you the right value whereas having an index may not work if new elements are inserted or older ones removed).

不要忘记，使用映射（如果您有键）访问特定项目也比从数组中访问要快得多（除非您有索引，但键总是会为您提供正确的值，而具有如果插入新元素或删除旧元素，索引可能不起作用）。

回答by aberrant80

I would say that you're generally correct, but not entirely accurate. You use a HashMapfor data retrieval, but not always randomly. You use an ArrayListfor iteration but you can also use it for lookups via the index.

我会说你通常是正确的，但并不完全准确。您使用 aHashMap进行数据检索，但并不总是随机的。您使用ArrayListfor 迭代，但您也可以使用它通过索引进行查找。

More generally, you use a Mapimplementation when you need to efficiently retrieve items by lookup, i.e. retrieving something based on the key - such as dictionaries, caches, repositories, etc.

更一般地，Map当您需要通过查找有效地检索项目时，您可以使用实现，即根据键检索某些内容 - 例如字典、缓存、存储库等。

You use a Listimplementation when you just want a data structure where you can iterate over your data, usually when you want them in a predetermined and/or predictable order.

List当您只想要一个可以迭代数据的数据结构时，您可以使用实现，通常是当您希望它们以预定和/或可预测的顺序进行时。

In other words, you use Maps as an indexing data structure, and you use Lists as you would usually use arrays.

换句话说，您使用Maps 作为索引数据结构，并List像通常使用数组一样使用s。

回答by stolsvik

A Map is a map, or "associative array". It has a key->value layout. A List is on the other hand a list, which is an ordered collection of elements.

Map 是一个映射，或“关联数组”。它有一个键->值布局。另一方面，List 是一个list，它是元素的有序集合。

A more direct comparison would possibly be between Setand List: Both these hold values, where the list is explicitly ordered (you can get element # x), and the set is (typically) not ordered (well, unless it is an SortedSet, in which case iteration order will be ordered by a Comparator).

更直接的比较可能是在Set和 List之间：这两个都包含值，其中列表是明确排序的（您可以获得元素 # x），并且集合（通常）没有排序（好吧，除非它是SortedSet，在这种情况下，迭代顺序将由比较器排序）。

The two most common implementations for Set and List is HashSet and ArrayList. To check if an element belongs in an arraylist (contains(element)), the implementation iterate over all the elements of it, checking whether one have found the element using the equals() method. To check if an element belongs in a hashset, first the element's hashCode() is calculated, then one goes "directly" to the position where this element shouldreside, and checks if it is there.

Set 和 List 的两个最常见的实现是 HashSet 和 ArrayList。为了检查一个元素是否属于一个数组列表（包含（元素）），实现迭代它的所有元素，检查是否使用 equals() 方法找到了该元素。要检查一个元素是否属于散列集，首先计算该元素的 hashCode()，然后“直接”到该元素应驻留的位置，并检查它是否在那里。

Thus, a significant difference between ArrayList and HashSet is the speed of contains().

因此，ArrayList 和 HashSet 之间的显着差异是 contains() 的速度。

On a list, you can ask for element# x, in addition to what you can do on a set, which is add, remove, ask-whether-present (contains), and iterate over all elements.

在列表上，除了可以在集合上执行的操作之外，您还可以请求元素#x，即添加、删除、询问是否存在（包含）以及迭代所有元素。

On a map, you can ask for an element by its key, instead of by its index as you do with a list.

在地图上，您可以通过键来请求元素，而不是像使用列表那样通过索引来请求。

A HashSet is currently implemented simply by a HashMap where the value part of the key->value relationship is not used. This is completely absurd and has no use whatsoever other than wasting at least 4 bytes, on could argue 12, for every and all elements inserted in the HashSet.

HashSet 目前仅由 HashMap 实现，其中不使用键->值关系的值部分。这完全是荒谬的，除了为 HashSet 中插入的每个和所有元素浪费至少 4 个字节（可能是 12 个）之外，没有任何用处。