Choosing where to put things

Most programs spend their time putting things in a collection and taking them out again. Picking the wrong one is the most common avoidable performance problem there is.

The families

Array backed or linked

ArrayList    index O(1), insert at the end amortised O(1),
             insert in the middle O(n)
LinkedList   index O(n), insert at a known position O(1)

The textbook answer is to use a linked list for frequent insertion. In practice ArrayList usually wins even there, because contiguous memory is far friendlier to the cache, and "find the position" is itself O(n) on a linked list. Unless you are inserting at a node you already hold, the array wins.

Hashed or ordered

HashSet / HashMap    O(1) average, no ordering
TreeSet / TreeMap    O(log n), sorted, range queries
LinkedHashMap        O(1), preserves insertion order

Choose hashed unless you need ordering or range queries, which is the same trade as hash tables against search trees in the DSA course.

The contract you must honour

Anything used as a hash key must implement hashCode and equals together, and the object must not change while it is in the collection.

Set<Point> set = new HashSet<>();
Point p = new Point(1, 2);
set.add(p);
p.setX(99);              // the hash changed
set.contains(p);         // false: it is in the bucket for the old hash

The object is in the set and cannot be found. This is the strongest practical argument for immutable keys.

Sizing and iteration

new ArrayList<>(10_000);     // avoids repeated doubling and copying

And modifying a collection while iterating it throws ConcurrentModificationException even on one thread. Collect what to remove and remove afterwards, or use the iterator's own remove, or removeIf.

Concurrency

HashMap is not thread safe, and concurrent writes can corrupt it rather than merely losing an update. The answers, in order of preference: ConcurrentHashMap, an immutable copy, or explicit locking. Wrapping with Collections.synchronizedMap locks the whole map for every operation and usually performs worse than ConcurrentHashMap, which locks per bucket.