java - 如果需要迭代和随机访问元素，则使用 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已经是商店的一个字段时，将其作为键似乎是多余的。我也不知道 HashMap 的迭代设计得怎么样。

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

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

Answer 1

使用HashMap - 这显然是您需要的抽象，因此它是最好的选择。 HashMap 上每个元素的迭代顺序为 O(1)，整个映射的总迭代次数为 O(n)(请注意，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.

简而言之 - 它会使迭代稍微快一些，同时使其他操作稍微慢一些。在我看来，追求更多是不成熟的。

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

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