Chọn collection: List, Set, Map, Queue hay Deque cho shop-backend

Hai cái đó đúng là đủ cho 80% trường hợp. Nhưng 20% còn lại là chỗ bug và chậm. Cách chọn: hỏi dữ liệu cần gì (thứ tự? trùng lặp? tra theo key? lấy đầu/cuối?), rồi chọn interface, cuối cùng mới chọn implementation.

1. Bài toán: 4 nhu cầu trong shop-backend

• Dòng sản phẩm trong giỏ hàng, giữ thứ tự thêm vào.
• Danh sách productId đã xem, không trùng.
• Tra Customer theo email; báo cáo doanh thu theo ngày, có thứ tự.
• Hàng đợi đơn chờ gửi email xác nhận.

2. Vấn đề khi chỉ dùng ArrayList

List<String> viewed = new ArrayList<>();
if (!viewed.contains(pid)) viewed.add(pid);       // contains O(n) → n lần = O(n²)

List<Customer> customers = repo.findAll();
customers.stream().filter(c -> c.getEmail().equals(email)).findFirst();  // O(n) mỗi lần tra

List<Order> pending = new ArrayList<>();
Order next = pending.remove(0);                   // dịch toàn bộ mảng: O(n)

3. Giải pháp: cây quyết định

Cần tra theo key?
 ├─ Có → Map
 │    ├─ không cần thứ tự .................. HashMap
 │    ├─ giữ thứ tự thêm vào / LRU .......... LinkedHashMap
 │    └─ sắp theo key, cần range (từ..đến) .. TreeMap
 └─ Không
      ├─ Không trùng lặp? → Set
      │    ├─ HashSet / LinkedHashSet / TreeSet (giống 3 Map trên)
      ├─ Lấy ra ở đầu/cuối (FIFO/LIFO)? → Deque: ArrayDeque
      ├─ Lấy phần tử ưu tiên nhất? → PriorityQueue
      └─ Truy cập theo index, giữ thứ tự → List: ArrayList

4. Code từng bước

Bước 1: Khai báo theo interface

List<CartLine> lines = new ArrayList<>();          // không phải ArrayList<CartLine> lines
Set<String> viewed    = new LinkedHashSet<>();      // không trùng, giữ thứ tự xem
Map<String, Customer> byEmail = new HashMap<>();
NavigableMap<LocalDate, BigDecimal> revenue = new TreeMap<>();
Deque<Order> emailQueue = new ArrayDeque<>();

Bước 2: Dùng đúng thao tác

viewed.add(pid);                                       // O(1), tự bỏ trùng

Map<String, Customer> byEmail = customers.stream()
        .collect(Collectors.toMap(Customer::getEmail, c -> c));
byEmail.get(email);                                    // O(1)

revenue.merge(order.getDate(), order.getTotal(), BigDecimal::add);
revenue.subMap(from, true, to, true);                  // doanh thu trong khoảng, O(log n)

emailQueue.offer(order);                               // thêm cuối
Order next = emailQueue.poll();                        // lấy đầu, O(1)

Bước 3: Trả ra ngoài bằng collection bất biến

public record Cart(String customerId, List<CartLine> lines) {
    public Cart {
        lines = List.copyOf(lines);          // copy phòng thủ + immutable
    }
}

List.of("NEW", "PAID");                        // immutable, không cho null
Map.of("VIP", 10, "GOLD", 5);                 // tối đa 10 cặp; nhiều hơn dùng Map.ofEntries
Collections.unmodifiableList(list);           // chỉ là "view": list gốc đổi thì view đổi theo
stream.toList();                               // Java 16, unmodifiable

Bước 4: Test: curl localhost:8080/reports/revenue?from=2026-10-01&to=2026-10-14 → TreeMap trả về đúng thứ tự ngày, không cần sort lại.

5. Cách hoạt động

                Iterable
                   │
               Collection                         Map (không phải Collection)
      ┌────────────┼──────────────┐           ┌────────┼──────────┐
     List         Set           Queue       HashMap  LinkedHashMap  TreeMap
   ArrayList   HashSet          │                        (SortedMap/NavigableMap)
   LinkedList  LinkedHashSet   Deque ── ArrayDeque, LinkedList
               TreeSet         PriorityQueue

6. So sánh: bảng chi phí

Chi tiết về Big-O xem bài 1.14.

* amortized.

7. Khi nào nên dùng / không nên

• Mặc định: ArrayList, HashMap, HashSet, ArrayDeque.
• Cần thứ tự thêm vào khi trả JSON → LinkedHashMap. Cần sort theo key hoặc range → TreeMap.
• Đa luồng: không dùng mấy class trên trực tiếp; xem concurrent collections.
• Trả ra từ method public: ưu tiên immutable để caller không sửa state bên trong.

Bạn hiểu đúng lý thuyết, nhưng thiếu một vế: O(1) chỉ đúng khi đã đứng sẵn ở node đó (qua iterator, hoặc ở đầu/cuối). Xóa theo index hay theo giá trị thì vẫn phải đi tìm từ đầu: O(n).

lines.remove(5);         // LinkedList: đi 5 bước rồi gỡ → O(n)
                         // ArrayList:  System.arraycopy phần sau → O(n) nhưng copy bộ nhớ liền mạch, cực nhanh
lines.get(5);            // LinkedList O(n), ArrayList O(1)

Thực tế đo được, ArrayList thắng trong hầu hết trường hợp vì CPU cache thích mảng liền kề, còn mỗi node của LinkedList là một object rải rác, tốn thêm ~24–40 byte. Giỏ hàng vài chục dòng thì khác biệt không đáng kể; cứ dùng ArrayList. Cần thêm/xóa ở hai đầu thì ArrayDeque. Bài 1.6 sẽ mổ xẻ bên trong cả hai.

Đúng, cả hai đều không cho add, nhưng mức "bất biến" khác nhau:

String[] arr = {"NEW", "PAID"};
List<String> view = Arrays.asList(arr);
arr[0] = "X";                       // view.get(0) cũng thành "X"

List<String> statuses = new ArrayList<>(List.of("NEW", "PAID"));   // cần sửa thì bọc lại
statuses.add("CANCELLED");          // ✅

Thêm một bẫy: List.of(...).contains(null) ném NPE. Chọn List.of cho hằng số và giá trị trả về; cần sửa thì copy sang ArrayList.

Vì TreeSet/TreeMap phải so sánh để xếp phần tử vào cây. Nó cast phần tử sang Comparable bên trong; Product không implement thì lỗi. Có hai cách:

// Cách 1: thứ tự tự nhiên
public record Product(String sku, String name, BigDecimal price) implements Comparable<Product> {
    public int compareTo(Product o) { return sku.compareTo(o.sku); }
}

// Cách 2: truyền Comparator (linh hoạt hơn)
Set<Product> byPrice = new TreeSet<>(
        Comparator.comparing(Product::price).thenComparing(Product::sku));

Lưu ý quan trọng: TreeSet coi compare == 0 là trùng, không dùng equals. Nếu chỉ so theo price, hai sản phẩm cùng giá sẽ mất một cái. Vì vậy luôn thêm tie-breaker (thenComparing(sku)) để compare nhất quán với equals.

Ba câu dưới đây gom gần hết.

Câu 1: ArrayList và LinkedList khác nhau gì?

🇻🇳 Tiếng Việt:

ArrayList dùng mảng động: get theo index O(1), thêm cuối amortized O(1), thêm/xóa giữa O(n) do dịch mảng. LinkedList là danh sách liên kết đôi: thêm/xóa ở đầu cuối O(1) nhưng get theo index O(n), mỗi node tốn thêm bộ nhớ và không thân thiện cache. Thực tế em gần như luôn dùng ArrayList, cần queue/stack thì dùng ArrayDeque.

🇬🇧 English:

ArrayList is backed by a dynamic array: indexed get is O(1), appending is amortized O(1), inserting or removing in the middle is O(n) because of shifting. LinkedList is a doubly linked list: adding or removing at the ends is O(1), but indexed access is O(n), and each node costs extra memory and hurts cache locality. In practice I almost always use ArrayList, and ArrayDeque for queues or stacks.

Câu 2: HashMap, LinkedHashMap, TreeMap?

🇻🇳 Tiếng Việt:

HashMap O(1) trung bình, không đảm bảo thứ tự. LinkedHashMap thêm một linked list nên giữ thứ tự thêm vào hoặc thứ tự truy cập, dùng làm LRU cache. TreeMap là red-black tree, O(log n), key luôn được sắp xếp và có các thao tác range như subMap, floorKey; key phải Comparable hoặc có Comparator.

🇬🇧 English:

HashMap gives average O(1) with no ordering. LinkedHashMap adds a linked list to keep insertion or access order, which is handy for an LRU cache. TreeMap is a red-black tree with O(log n) operations, keys always sorted, and range operations like subMap or floorKey; keys must be Comparable or have a Comparator.

Câu 3: Chọn collection thế nào?

🇻🇳 Tiếng Việt:

Em hỏi dữ liệu cần gì: tra theo key thì Map, không trùng thì Set, lấy đầu/cuối thì Deque, ưu tiên thì PriorityQueue, còn lại List. Sau đó chọn implementation theo nhu cầu thứ tự và độ phức tạp, khai báo bằng interface, và trả ra ngoài bằng collection immutable như List.of hoặc List.copyOf.

🇬🇧 English:

I ask what the data needs: lookup by key means Map, uniqueness means Set, head or tail access means Deque, priority means PriorityQueue, otherwise List. Then I pick the implementation by ordering needs and complexity, declare variables by interface, and return immutable collections such as List.of or List.copyOf.

Cách nhớ ngắn gọn

• Key → Map; unique → Set; đầu/cuối → Deque; ưu tiên → PriorityQueue; còn lại → List.
• Hash = nhanh không thứ tự; Linked = giữ thứ tự; Tree = sắp xếp + range.
• Mặc định ArrayList, quên LinkedList.
• List.of immutable thật, Arrays.asList chỉ cố định kích thước.