如果需要迭代和随机访问元素，Hashmap 或 ArrayList？

Question

我有一堆商店：

public class Shop {
    private final String shopName;
    private boolean shopProperty1;
    private boolean shopProperty2;
}

现在有时我需要通过商店名称检索商店，有时我需要对所有现有商店执行操作。

和ArrayList

List<Shop> shops = new ArrayList<>();
Shop shop1 = new Shop("Megastore", false, true);
Shop shop2 = new Shop("PC-shop", true, true);
Shop shop3 = new Shop("Jim's junkyard", false, false);
shops.add(shop1);
shops.add(shop2);
shops.add(shop3);

迭代：

for (Shop shop : shops) {
    doOperation(shop);
}

正在通过商店名称检索 Megastore：

Shop retrieved;
for (Shop shop : shops) {
    if ("Megastore".equals(shop.getShopName())) {
        retrieved = shop;
        break;
    }
}

我对使用这种方法的担忧：

使用 ArrayList 按名称检索似乎很慢，而 HashMap 会好得多。

用HashMap

Map<String, Shop> shops = new HashMap<>();
Shop shop1 = new Shop("Megastore", false, true);
Shop shop2 = new Shop("PC-shop", true, true);
Shop shop3 = new Shop("Jim's junkyard", false, false);
shops.put(shop1.getShopName(), shop1);
shops.put(shop2.getShopName(), shop2);
shops.put(shop3.getShopName(), shop3);

迭代：

for (Shop shop : shops.values()) {
    doOperation(shop);
}

正在通过商店名称检索 Megastore：

Shop retrieved = shops.get("Megastore");

我对使用这种方法的担忧：

当 shopName 已经是 Shop 的字段时，将 shopName 作为键似乎是多余的。我也不知道 HashMap 的迭代设计有多好。

所以问题是：哪种方法是更好的设计实践，或者是否有更好的方法？程序员通常如何处理这种情况？

不是 When to use HashMap over LinkedList or ArrayList and vice-versa 的重复，因为这解释了这些方法的潜在问题。不过在代码审查中可能会更好。

Answer 1

使用HashMap - 这显然是您需要的抽象，因此它是最佳选择。 HashMap 上的迭代对于每个元素的顺序为 O(1)，对于整个映射的总迭代为 O(n)（注意 n 是 HashMap 的容量，而不是它的大小！）。您也可以使用 LinkedHashMap（如 Peter Lawrey 所建议），但请注意：

Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

简而言之 - 它会使迭代速度稍快，同时使其他操作速度稍慢。追求更多是 IMO 过早的操作。

不过，如果您需要 每一点 的速度，数据是相当静态的（即集合仅创建 [添加元素] 一次，并使用 [迭代、检查多次包含]），并且您不介意使用大约 2 倍的内存 - 您可以同时使用，添加到两者，并使用 array/ArrayList 进行迭代和 HashMap 进行查找。不过，我不建议将其用于临时用途，因为它会使代码更难阅读和维护，并且很可能会违反 Single Responsibility Principle。如果您打算使用它，IMO 最好编写一个合成 class，将 ArrayList 的迭代器与 Map 接口中的方法并行公开。

至于在对象中存储名称及其冗余 - 您只存储对键的引用，而不是键本身。因此，您的 "wastage"（请注意，在大多数情况下并不是真正的浪费）每个集合项大约有 4 个字节。除非您打算拥有一个包含数十亿个元素的集合，否则这不是问题。 OTOH，问问自己为什么要在商店实例中存储商店名称？如果您希望能够在键（商店名称）和商店之间建立双射关系[能够通过名称获取商店并知道每家商店的名称] - 您要么必须将名称存储在对象，或为其使用第二张地图。在大多数情况下，前者比后者更好（这更多的是适当抽象的问题，而不是 memory/CPU 这里，再次）。因此，在对象中复制密钥通常是处理它的最简单和最明显的方法。

如果需要迭代和随机访问元素，Hashmap 或 ArrayList？

Hashmap or ArrayList if needed to both iterate and randomly access elements?

java

arraylist

hashmap