Choosing the Right Collection

Pick a collection by the questions your code asks of it, start from ArrayList, HashMap, HashSet and ArrayDeque, and know when the specialised ones pay off.

SyntaxList<T> -> ArrayList Map<K,V> -> HashMap Set<T> -> HashSet Queue/stack -> ArrayDeque sorted/ranges -> TreeMap, TreeSet enum keys -> EnumMap, EnumSet shared, many writers -> ConcurrentHashMap

Choose a collection by the operations your code performs most often, not by habit. Ask three questions: do I look things up by key or position, does order matter, and will more than one thread touch it?

Start with the defaults

You needUse
An ordered list, access by indexArrayList
Lookup by keyHashMap
Unique values, fast containsHashSet
A queue or a stackArrayDeque
Insertion order keptLinkedHashMap, LinkedHashSet
Sorted keys, ranges, nearest matchTreeMap, TreeSet
Enum keys or flagsEnumMap, EnumSet
Highest priority firstPriorityQueue
Fixed data shared freelyList.of, Map.copyOf
A map written by many threadsConcurrentHashMap

When the specialised ones pay off

  • TreeMap costs O(log n) per operation but answers questions a hash map cannot: floorEntry for "which pricing tier covers this amount", subMap for "events between these timestamps".
  • EnumMap and EnumSet are backed by arrays and bit sets, so they are compact and fast, and they iterate in the enum's declaration order.
  • LinkedHashMap with access order and removeEldestEntry is a small LRU cache in a few lines.
  • CopyOnWriteArrayList suits lists read constantly and changed rarely, such as registered listeners. Every write copies the whole array.

Classes to avoid in new code

Vector, Hashtable and Stack predate the framework and lock every call. LinkedList is rarely the right answer: ArrayList beats it for index access and memory, and ArrayDeque beats it as a queue.

Mistakes people make

  • Calling List.contains inside a loop over another large list. Turning the lookup side into a HashSet changes quadratic work into linear work, which matters once a batch reaches thousands of rows.
  • Caches with no bound. A HashMap that only grows is a memory leak in a long-running service. Give it a size limit or use a cache library with eviction.
  • Picking by big-O alone. For a dozen elements a List scan is perfectly fine and often faster than hashing. Measure before replacing simple code.
  • Using a plain HashMap as shared state in a web server, where every request runs on its own thread.

Example

Try it yourself
Loading editor…
Press Run to execute the code.

When to use it

  • Resolve a customer's pricing tier from monthly usage with TreeMap.floorEntry.
  • Count orders per status for a dashboard endpoint with an EnumMap that returns statuses in a fixed order.
  • Keep per-route hit counters in a ConcurrentHashMap shared by all request threads.

More examples

A small LRU cache with LinkedHashMap

Access order moves each key to the end when it is read, and removeEldestEntry drops the least recently used entry after every put. It is not thread-safe, so wrap it or use a cache library for shared use.

Example · java
class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    LruCache(int maxEntries) {
        super(16, 0.75f, true);           // true = order by access, not insertion
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}

void main() {
    var cache = new LruCache<String, String>(2);
    cache.put("user:1", "ada");
    cache.put("user:2", "linus");
    cache.get("user:1");                  // user:1 is now the most recently used
    cache.put("user:3", "grace");         // evicts user:2

    IO.println(cache.keySet());
    IO.println("user:2 cached: " + cache.containsKey("user:2"));
}
// Output:
// [user:1, user:3]
// user:2 cached: false

Counting from many threads with ConcurrentHashMap

ConcurrentHashMap.merge is atomic for each key, so no increment is lost even with a thousand concurrent tasks. The same loop with a plain HashMap can lose updates or corrupt the map.

Example · java
void main() {
    Map<String, Integer> hits = new ConcurrentHashMap<>();
    List<String> paths = List.of("/users", "/orders", "/users");

    try (var executor = Executors.newVirtualThreadPerTaskExecutor()) {
        for (int i = 0; i < 1000; i++) {
            String path = paths.get(i % paths.size());
            executor.submit(() -> hits.merge(path, 1, Integer::sum));
        }
    }                                     // close() waits for every task

    IO.println(new TreeMap<>(hits));
}
// Output:
// {/orders=333, /users=667}

Turning a lookup list into a Set

With a List, each check scans every blocked address, so a large batch against a large deny list does a huge number of comparisons. Building the Set once makes each check a hash lookup, and the stream over the List keeps the request order.

Example · java
void main() {
    List<String> blockedList = List.of("10.0.0.5", "10.0.0.9", "192.168.1.20");
    Set<String> blocked = Set.copyOf(blockedList);   // built once, constant-time contains

    List<String> requestIps = List.of("10.0.0.1", "10.0.0.9", "172.16.0.3", "192.168.1.20", "10.0.0.9");

    List<String> rejected = requestIps.stream().filter(blocked::contains).toList();
    List<String> accepted = requestIps.stream().filter(ip -> !blocked.contains(ip)).toList();
    IO.println("rejected: " + rejected);
    IO.println("accepted: " + accepted);
}
// Output:
// rejected: [10.0.0.9, 192.168.1.20, 10.0.0.9]
// accepted: [10.0.0.1, 172.16.0.3]

Related

java the collections frameworkjava queue and dequejava atomic variables and concurrent collectionsjava string and collection performancejava enums

Discussion

  • Be the first to comment on this lesson.