HashSet, LinkedHashMap, TreeMap, PriorityQueue: LRU cache và top sản phẩm bán chạy

Đúng vậy. Bài này đi qua 4 cấu trúc, mỗi cái gắn với một tính năng của shop-backend: lọc trùng, cache sản phẩm, bảng giá theo khoảng, top bán chạy. HashMap đã mổ ở bài 1.4.

1. Bài toán

• Cache 1.000 Product được xem gần nhất, đầy thì bỏ cái lâu không ai xem (LRU).
• Phí ship theo mốc tổng tiền: < 200k: 30k; 200k–500k: 15k; ≥ 500k: miễn phí.
• Top 10 sản phẩm bán chạy trong 2 triệu dòng OrderLine.

2. Vấn đề với cách làm ngây thơ

// LRU bằng HashMap + List thứ tự: mỗi lần get phải list.remove(p) → O(n)
// Phí ship bằng if-else: thêm mốc là sửa code, dễ sai biên
// Top 10: sort cả 2 triệu → O(n log n), tốn bộ nhớ cho cả list đã sort

3. Giải pháp

• HashSet = HashMap<E, Object>, value là một object hằng PRESENT. add(e) = map.put(e, PRESENT) == null.
• LinkedHashMap = HashMap + linked list đôi nối các entry. Chế độ accessOrder = true đưa entry vừa get xuống cuối; override removeEldestEntry → LRU cache.
• TreeMap = red-black tree (cây BST tự cân bằng), O(log n), có floorKey, ceilingKey, headMap, subMap.
• PriorityQueue = binary heap trên mảng. Top-k dùng min-heap kích thước k: O(n log k).

4. Code từng bước

Bước 1: LRU cache sản phẩm bằng LinkedHashMap

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LruCache(int maxSize) {
        super(16, 0.75f, true);              // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;             // gọi sau mỗi put: true → xóa entry đầu (lâu nhất)
    }
}

@Service
class ProductService {
    private final Map<String, Product> cache =
            Collections.synchronizedMap(new LruCache<>(1000));   // LinkedHashMap không thread-safe

    Product find(String sku) {
        return cache.computeIfAbsent(sku, repo::findBySkuOrThrow);
    }
}

Bước 2: Phí ship theo mốc bằng TreeMap

private static final NavigableMap<BigDecimal, BigDecimal> SHIPPING = new TreeMap<>(Map.of(
        BigDecimal.ZERO,             new BigDecimal("30000"),
        new BigDecimal("200000"),    new BigDecimal("15000"),
        new BigDecimal("500000"),    BigDecimal.ZERO));

BigDecimal shippingFee(BigDecimal total) {
    return SHIPPING.floorEntry(total).getValue();   // mốc lớn nhất ≤ total, O(log n)
}
// shippingFee(350000) → floor = 200000 → 15000

Bước 3: Top 10 bán chạy bằng PriorityQueue

List<Map.Entry<String, Long>> top(Map<String, Long> soldBySku, int k) {
    PriorityQueue<Map.Entry<String, Long>> heap =
            new PriorityQueue<>(Map.Entry.comparingByValue());   // min-heap theo số lượng
    for (var e : soldBySku.entrySet()) {
        heap.offer(e);
        if (heap.size() > k) heap.poll();                       // bỏ cái nhỏ nhất
    }
    List<Map.Entry<String, Long>> result = new ArrayList<>(heap);
    result.sort(Map.Entry.<String, Long>comparingByValue().reversed());
    return result;
}

Bước 4: Test: curl localhost:8080/products/top?k=10; gọi GET /products/P01 2 lần, log chỉ có 1 câu SQL.

5. Cách hoạt động

LinkedHashMap (accessOrder = true, max 3):
 bucket table như HashMap  +  danh sách đôi theo thứ tự truy cập
 head ⇄ P1 ⇄ P2 ⇄ P3 ⇄ tail
 get(P1)  → head ⇄ P2 ⇄ P3 ⇄ P1 ⇄ tail          (P1 xuống cuối)
 put(P4)  → head ⇄ P3 ⇄ P1 ⇄ P4 ⇄ tail          (removeEldestEntry → xóa P2)

TreeMap (red-black tree, phí ship):
             [200000]  (đen)
            /        \
      [0] (đỏ)     [500000] (đỏ)
 floorEntry(350000): 350000 > 200000 → sang phải → 500000 > 350000 → hết → trả 200000
 Cân bằng: đường dài nhất ≤ 2 × đường ngắn nhất → chiều cao O(log n)

PriorityQueue (min-heap trên mảng, k = 4):
 index:   0   1   2   3
        [ 5 | 9 | 7 | 12 ]         cha(i) = (i-1)/2, con = 2i+1, 2i+2
             5
           /   \
          9     7
         /
        12
 offer(8): đặt cuối, "sift up" so với cha → O(log k)
 poll():   lấy gốc (5), đưa phần tử cuối lên gốc, "sift down" → O(log k)

6. So sánh

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

• LRU tự viết bằng LinkedHashMap hợp cho cache nhỏ, một instance. Cần TTL, thống kê, nhiều thread: dùng Caffeine; nhiều instance: Redis.
• TreeMap khi cần thứ tự hoặc range; chỉ tra theo key thì HashMap nhanh hơn.
• PriorityQueue: đừng duyệt bằng for-each rồi mong có thứ tự, chỉ poll() mới trả đúng thứ tự.
• Đa luồng: ConcurrentHashMap, ConcurrentSkipListMap, PriorityBlockingQueue; xem concurrent collections.

Cách của bạn cũng ra đúng kết quả, chỉ tốn hơn. So sánh:

Ý tưởng: min-heap giữ k ứng viên tốt nhất hiện tại, gốc là người yếu nhất trong top. Phần tử mới chỉ cần so với gốc: nhỏ hơn thì bỏ, lớn hơn thì thay gốc. Nên gốc min-heap chính là "ngưỡng vào top".

k = 3, dữ liệu: 5 1 9 3 7 8
heap sau mỗi bước (gốc trước):
 [5] → [1,5] → [1,5,9] → [3,5,9] (bỏ 1) → [5,7,9] (bỏ 3) → [7,8,9] (bỏ 5)
top 3 = 9, 8, 7

Thêm: với 2 triệu dòng nằm trong DB thì đừng kéo lên Java; SELECT sku, SUM(qty) ... GROUP BY sku ORDER BY 2 DESC LIMIT 10 là đủ. Heap hợp khi dữ liệu đến từ stream/Kafka hoặc đã ở trong bộ nhớ.

Không cần thuộc từng ca xoay. Cần hiểu vì sao phải cân bằng:

BST thường, chèn giá đã sắp: 100, 200, 300, 400
 100
   \
   200
     \
     300            → thành linked list, tìm O(n)
       \
       400

Red-black tree cùng dữ liệu:
       200(B)
      /    \
  100(B)  300(B)
             \
            400(R)  → chiều cao luôn O(log n)

Các quy tắc chính (đủ để trả lời):

• Mỗi node đỏ hoặc đen, gốc đen.
• Node đỏ không có con đỏ.
• Mọi đường từ một node xuống lá có cùng số node đen.

Hệ quả: đường dài nhất ≤ 2 lần đường ngắn nhất. Khi chèn/xóa làm vỡ quy tắc, cây đổi màu và xoay (rotate) cục bộ, chỉ O(log n) bước. So với AVL: AVL cân bằng chặt hơn (tra nhanh hơn chút), red-black xoay ít hơn khi ghi. Java dùng red-black cho cả TreeMap và bucket treeify của HashMap.

Đúng, quy luật rất gọn: mỗi Set bọc Map tương ứng, phần tử là key, value là PRESENT.

HashSet        → HashMap
LinkedHashSet  → LinkedHashMap  (thứ tự thêm vào; không có accessOrder)
TreeSet        → TreeMap        (NavigableSet: first, floor, ceiling, headSet...)

// rút gọn từ JDK
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();
    public boolean add(E e)      { return map.put(e, PRESENT) == null; }
    public boolean contains(Object o) { return map.containsKey(o); }
}

Vì thế mọi luật của Map áp dụng y nguyên cho Set: HashSet cần equals/hashCode đúng, TreeSet cần Comparable/Comparator và coi compare == 0 là trùng. Ví dụ dùng TreeSet: lịch giao hàng còn trống, slots.ceiling(now) trả slot sớm nhất từ bây giờ.

Ba câu, mỗi câu kèm ví dụ trong dự án.

Câu 1: HashSet hoạt động thế nào? TreeMap thì sao?

🇻🇳 Tiếng Việt:

HashSet bọc một HashMap, phần tử là key, value là một object hằng dùng chung; add trả true khi put trả về null. Vì vậy nó dựa vào equals và hashCode. TreeMap là red-black tree, cây nhị phân tự cân bằng, mọi thao tác O(log n), key luôn có thứ tự và hỗ trợ floorKey, ceilingKey, subMap. Em dùng TreeMap cho bảng phí ship theo mốc tiền, tra bằng floorEntry.

🇬🇧 English:

HashSet wraps a HashMap: elements are keys and the value is a shared constant; add returns true when put returns null. So it relies on equals and hashCode. TreeMap is a red-black tree, a self-balancing binary search tree with O(log n) operations, sorted keys, and navigation methods like floorKey, ceilingKey and subMap. I used it for shipping fee tiers, looked up with floorEntry.

Câu 2: Cài LRU cache thế nào?

🇻🇳 Tiếng Việt:

Cách gọn nhất trong Java là extends LinkedHashMap với accessOrder = true, để mỗi lần get entry được đưa xuống cuối, và override removeEldestEntry trả về true khi size vượt giới hạn. Get và put đều O(1). Nó không thread-safe nên phải bọc lại; production em dùng Caffeine hoặc Redis. Tự cài từ đầu thì dùng HashMap cộng doubly linked list.

🇬🇧 English:

The simplest Java way is to extend LinkedHashMap with accessOrder set to true, so every get moves the entry to the tail, and override removeEldestEntry to return true when the size exceeds the limit. Both get and put are O(1). It is not thread-safe, so it must be wrapped; in production I use Caffeine or Redis. From scratch, it is a HashMap plus a doubly linked list.

Câu 3: Tìm top-k phần tử lớn nhất?

🇻🇳 Tiếng Việt:

Dùng PriorityQueue làm min-heap giới hạn k phần tử. Duyệt dữ liệu, offer từng phần tử, nếu size vượt k thì poll bỏ phần tử nhỏ nhất. Cuối cùng heap chứa k phần tử lớn nhất. Độ phức tạp O(n log k), bộ nhớ O(k), chạy được trên dữ liệu stream. PriorityQueue là binary heap trên mảng, offer và poll O(log n), peek O(1).

🇬🇧 English:

Use a PriorityQueue as a min-heap capped at k elements. Offer each element and, when the size exceeds k, poll to drop the smallest. At the end the heap holds the k largest. That is O(n log k) time and O(k) memory, and it works on streaming data. PriorityQueue is a binary heap backed by an array, with O(log n) offer and poll and O(1) peek.

Cách nhớ ngắn gọn

• Set = Map bọc lại, value là PRESENT.
• LinkedHashMap + accessOrder + removeEldestEntry = LRU.
• TreeMap = red-black, O(log n), floor/ceiling/subMap.
• Top-k lớn nhất = min-heap cỡ k, O(n log k).