Java Collections Cheat Sheet

A practical reference covering how Java’s core collections work under the hood — HashMap bucket internals, ConcurrentHashMap’s lock-free design, ArrayList vs LinkedList performance, sorted/ordered maps, and choosing the right queue.

---

HashMap Internals

Array of buckets where each bucket is a linked list (Java 7) or a red-black tree when the bucket size exceeds 8 (Java 8+). Load factor 0.75 means resize at 75% capacity — doubles the array and rehashes all entries. hashCode() + equals() contract is critical: equal objects must have equal hash codes.

buckets array
┌─────┐
│  0  │──▶ null
├─────┤
│  1  │──▶ ["alice", 25] ──▶ ["carol", 31]  (collision → linked list)
├─────┤
│  2  │──▶ null
├─────┤
│  3  │──▶ ["bob", 30]
└─────┘
 ...
When bucket list length > 8 → converts to red-black tree → O(log n) lookup

// hashCode + equals contract
class Money {
    final long amount;
    final String currency;

    @Override
    public int hashCode() {
        return Objects.hash(amount, currency); // both fields
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Money m)) return false;
        return amount == m.amount && currency.equals(m.currency);
    }
}

// If you override equals() without hashCode():
Map<Money, String> map = new HashMap<>();
map.put(new Money(100, "EUR"), "hundred");
map.get(new Money(100, "EUR")); // returns null! — different hash buckets

// Initial capacity to avoid rehashing
Map<String, Integer> map = new HashMap<>(expectedSize / 0.75 + 1);

---

ConcurrentHashMap

Java 8 replaced segment-based locking with CAS + per-bucket synchronization. Reads are completely lock-free. Writes synchronize only on the specific bucket being modified — far less contention than a single lock. size() is approximate (uses LongAdder internally).

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// Atomic compound operations
map.putIfAbsent("key", 1);
map.computeIfAbsent("key", k -> expensiveLoad(k));  // atomic
map.merge("key", 1, Integer::sum);  // atomic read-modify-write

// Common mistake: non-atomic check-then-act
if (!map.containsKey("key")) {      // check
    map.put("key", compute("key")); // act — NOT atomic! race condition
}
// Fix: use computeIfAbsent

// size() is approximate — avoid in logic
int approxSize = map.size(); // may not reflect concurrent inserts

// forEach is weakly consistent — sees snapshot, won't throw ConcurrentModificationException
map.forEach((k, v) -> process(k, v));

---

ArrayList vs LinkedList

ArrayList wins in almost all real-world cases due to CPU cache locality. Contiguous memory means the prefetcher works. LinkedList nodes are scattered in the heap — every .get(i) is a cache miss.

// ArrayList — O(1) random access, O(n) insert at middle
List<String> list = new ArrayList<>();
list.get(500);           // O(1) — direct index into array
list.add(0, "first");    // O(n) — shifts all elements right

// LinkedList — O(1) insert at iterator position, O(n) get(i)
LinkedList<String> ll = new LinkedList<>();
ll.addFirst("head");     // O(1)
ll.get(500);             // O(n) — traverses 500 nodes

// When LinkedList wins: frequent insert/delete via iterator
Iterator<String> it = ll.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) it.remove(); // O(1) at current position
}
// Same with ArrayList is O(n) per remove due to shifting

// In practice: ArrayList + removeIf() is often still faster
list.removeIf(s -> shouldRemove(s)); // bulk shift once

---

TreeMap vs LinkedHashMap

TreeMap: sorted by natural order or Comparator, O(log n) ops, backed by a red-black tree. LinkedHashMap: maintains insertion or access order, O(1) ops — the classic LRU cache base.

// TreeMap — sorted keys
TreeMap<String, Integer> tree = new TreeMap<>();
tree.put("banana", 2);
tree.put("apple", 1);
tree.put("cherry", 3);
tree.firstKey();                    // "apple"
tree.subMap("apple", "cherry");     // range query
tree.floorKey("blueberry");         // "banana" — largest key <= query

// LinkedHashMap — LRU cache
int MAX = 100;
Map<String, Data> lruCache = new LinkedHashMap<>(MAX, 0.75f, true) {
    // accessOrder=true: get() moves entry to end
    protected boolean removeEldestEntry(Map.Entry e) {
        return size() > MAX; // evict oldest on overflow
    }
};
lruCache.put("key", data);
lruCache.get("key"); // moves "key" to most-recently-used end

---

Queue Family

Choose the right queue for the job:

Queue type              Bounded?  Blocking?   Use case
────────────────────────────────────────────────────────
ArrayDeque              No        No          General stack/queue, faster than LinkedList
PriorityQueue           No        No          Min-heap, task scheduling
ArrayBlockingQueue      YES       Yes         Producer-consumer with back-pressure
LinkedBlockingQueue     Optional  Yes         Producer-consumer (default unbounded!)
SynchronousQueue        0-size    Yes         Direct handoff, no buffering
DelayQueue              No        Yes         Scheduled tasks (expires after delay)

// ArrayDeque — general purpose, no null allowed, faster than LinkedList
Deque<String> deque = new ArrayDeque<>();
deque.push("a");    // stack: push to front
deque.pop();        // stack: pop from front
deque.offer("b");   // queue: add to back
deque.poll();       // queue: remove from front

// PriorityQueue — min-heap
PriorityQueue<Task> pq = new PriorityQueue<>(
    Comparator.comparingInt(t -> t.priority)
);
pq.offer(new Task(3, "low"));
pq.offer(new Task(1, "high"));
pq.poll(); // returns Task(1, "high") — lowest priority value first

// BlockingQueue — producer-consumer
BlockingQueue<Order> queue = new ArrayBlockingQueue<>(100);
// Producer
queue.put(order);      // blocks if full
queue.offer(order, 1, SECONDS); // times out if full

// Consumer
Order o = queue.take();          // blocks if empty
Order o = queue.poll(1, SECONDS);// times out if empty

// SynchronousQueue — zero buffer, direct handoff
BlockingQueue<Work> handoff = new SynchronousQueue<>();
// put() blocks until a consumer calls take() — and vice versa