何时使用HashMap而不是LinkedList或ArrayList，反之亦然

Question

为什么我们不能总是使用 HashMap，即使它在添加、删除操作中比 ArrayList 或 LinkedList 更高效，而且不管元素数量如何。

我查了一下谷歌，找到了一些原因，但总是有解决方案可以使用 HashMap，而且仍然具有优势。

- user517491

---

“列表”和“映射”是两种完全不同的数据结构，具有不同的操作和约束条件。您能解释一下在哪些情况下两者都是可接受的解决方案的背景/要求吗？ - Mark Peters

显然你从未需要将一组物品“按特定顺序”保持... - Brian Roach

为什么要点踩呢？我认为这是一个适当的问题。虽然显示了缺乏知识，但在SO上，问题不应因显示缺乏知识而被点踩。事实上，问题本身就是缺乏知识的结果。 - user517491

Answer 1

列表表示元素的顺序排列。 地图用于表示键/值对的集合。

虽然您可以将地图用作列表，但这样做确实存在一些明显的缺点。

维护顺序：

• 按定义，列表是有序的。您添加项目，然后能够通过与插入项目的顺序相同的顺序反向迭代列表。当您向HashMap添加项目时，不能保证以相同的顺序检索项目。 HashMap的子类（如LinkedHashMap）将保持顺序，但通常情况下，Map不保证顺序。

键/值语义：

• 地图的目的是基于可用于稍后检索项目的键存储项目。仅在键恰好是列表中的位置的有限情况下，才能使用列表实现类似功能。

代码可读性: 请考虑以下示例。

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

集合功能 通过Collections类，可以为列表提供许多实用的工具函数。例如...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);

- polster

---

链表经常因为性能问题而被认为是不好的。我经常使用LinkedLists而不是ArrayLists，因为它可以保持元素的顺序。如果我使用以位置为键的HashMaps，是否会更好（对于性能和内存）？ - Cesar Castro

Answer 2

列表和映射是不同的数据结构。映射用于将键与值关联起来，而列表则是有序的集合。

Map是Java Collection Framework中的接口，而HashMap是Map接口的一种实现。HashMap在基于键查找值以及基于键插入和删除值方面非常高效。HashMap的条目不是有序的。

ArrayList和LinkedList都是List接口的实现。LinkedList提供了顺序访问，并且通常更有效地在列表中插入和删除元素，但是对于访问列表中的元素则较为低效。ArrayList提供随机访问，并且在访问元素时更加高效，但通常在插入和删除元素方面则较慢。

- jazzdawg

Answer 3

我将在这里列举一些实际案例和场景，告诉你何时使用其中之一，这可能对其他人有所帮助：

HashMap

当您的应用程序需要使用缓存时。Redis和membase是某种扩展的HashMap。（不管元素的顺序如何，您需要快速（O（1））读取访问（值），使用键）。

LinkedList

当顺序很重要（它们按添加到LinkedList中的顺序排序），元素数量未知（不浪费内存分配）并且需要快速插入时间（O（1））时使用。待办事项列表可以按顺序列出，因为它们被添加到其中。

- vhbazan

Answer 4

ArrayList和LinkedList的缺点在于，通过它们进行迭代时，根据搜索算法，查找项目所需的时间随列表大小增加而增加。

哈希表的优点在于，虽然你需要牺牲一些额外的时间来搜索元素，但所花费的时间不会随着映射的大小增加而增加。这是因为HashMap通过将要查找的元素转换为索引来查找信息，从而可以进行跳跃。

简而言之... LinkedList：消耗的内存比ArrayList多一点，插入（添加和删除）的成本较低。 ArrayList：内存占用低，但类似于LinkedList，当列表很大时需要额外的搜索时间。 HashMap：对于大型映射，可以执行跳转到值，使搜索时间保持恒定。消耗更多的内存，并且查找值比小型列表需要更长的时间。

- Simon Walker