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

Question

I have a bunch of Shops:

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

Now sometimes I need to retrieve a Shop by its shopName and sometimes I need to perform an operation to all existing Shops.

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

Iterating:

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

Retrieving Megastore by shopName:

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

My concerns for using this approach:

Retrieving by name seems rather slow with ArrayList and HashMap would be much better there.

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

Iterating:

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

Retrieving Megastore by shopName:

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

My concerns for using this approach:

It seems redundant to have shopName as key when it is already a field of the Shop. Also I don't know how well HashMap has been designed to be iterated through.

So the question is: Which approach is better design practice or are there even better ways? How do programmers usually deal with this kind of situation?

Not a duplicate of When to use HashMap over LinkedList or ArrayList and vice-versa because this explains the potential problems with the approaches. Could be better in codereview though.

Answer 1

Use HashMap - it's obviously the abstraction you need, thus it's the best choice. Iteration on HashMap is in order of O(1) for each element, O(n) for total iteration over the entire mapping (note that n is the capacity of the HashMap, not it's size!). You can also use LinkedHashMap (as suggested by Peter Lawrey), but note:

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.

in short - it'd make the iteration slightly faster, while making other ops slightly slower. Going for anything more is IMO premature op.

Still, if you need that every little bit of speed, the data is rather static (i.e. collection is created [elements added] only once, and used [iterated, checked for containing] many times), and you don't mind using about 2x the memory - you may use both, adding to both, and using array/ArrayList for iteration and HashMap for lookup. I wouldn't recommend this for casual uses though, as it makes the code harder to read & maintain, and because it could very well violate the Single Responsibility Principle. If you're aiming to use it, IMO it's best to write a compositing class, exposing the iterator of ArrayList in parallel to methods from the Map interface.

As to storing the names in the objects and the redundancy of it - you're only storing a reference to the key, not the key itself. As such, your "wastage" (not a real wastage in most situations, mind me) is at about 4 bytes per collection item. Unless you intent to have a collection with billions of elements, no, it's not an issue. OTOH, ask yourself why you want to store the name of the shop in the shop instances? If you want to be able to have bijective relation between the keys (shop names) and the shops [being able to get the shop by name and to know the name of every shop] - you'd either have to store the name in the objects, or to use a second map for it. In most cases, the former is better than the latter (it's more a matter of proper abstraction than memory/CPU here, again). As such, having the key duplicated in the object is usually the simplest and most obvious way to deal with it.