Java Collections Deep Dive: Internals & Performance – Từ Lý Thuyết Đến Thực Tế

Bài viết dành cho Java Developer từ 1-2 năm kinh nghiệm, muốn hiểu thật sâu bên trong các collection và tránh những bug hiệu năng khó chịu.

Mục lục

Vì sao cần đào sâu vào Collections?
Ba tình huống thực tế – Chọn sai collection là “bom nổ chậm”
Hiểu sâu về List – ArrayList, LinkedList, ArrayDeque
Hiểu sâu về Map – HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap,…
Set – Đơn giản nhưng vẫn có “cao thủ” EnumSet
Queue & PriorityQueue – Hàng đợi và đống nhị phân
Benchmark thực chiến với JMH – Không tin lý thuyết suông
8 Anti‑pattern kinh điển khi dùng Collections
Decision Tree – Cây quyết định chọn collection
Gỡ rối phỏng vấn – Những câu hỏi thường gặp
Checklist thành thạo
Phụ lục: Memory Footprint – Tốn bao nhiêu RAM?

Vì sao cần đào sâu vào Collections?

Bạn đã biết chọn ArrayList khi cần danh sách, HashMap khi cần ánh xạ key‑value. Nhưng khi đi phỏng vấn Senior hay gặp bug hiệu năng “ma quái”, những câu hỏi kiểu “Tại sao ArrayList.get(i) là O(1) còn LinkedList.get(i) lại O(n)”, “HashMap xử lý collision thế nào từ Java 8”, “Khác biệt giữa ConcurrentHashMap và Collections.synchronizedMap ra sao?” sẽ xuất hiện. Bài viết này lấp đầy khoảng trống đó: không chỉ lý thuyết, mà còn có benchmark thực tế bằng JMH (Java Microbenchmark Harness) để bạn tự kiểm chứng.

Ba tình huống thực tế – Chọn sai collection là “bom nổ chậm”

Tình huống 1: App chạy càng ngày càng chậm

// ❌ Code của junior – 1 tuần đầu ngon lành, sau đó bò như rùa
public class TransactionProcessor {
    private List<String> processedIds = new LinkedList<>();  // ← thủ phạm

    public void process(Transaction tx) {
        if (processedIds.contains(tx.getId())) {  // O(n) trên LinkedList
            return;
        }
        processedIds.add(tx.getId());
        // xử lý...
    }
}

Sau 1 tuần processedIds có 100.000 phần tử. Mỗi lần contains() duyệt toàn bộ danh sách, độ phức tạp O(n). Với 100.000 phần tử, mỗi transaction mất ~100.000 phép so sánh → throughput giảm thảm hại.

Senior fix – dùng HashSet với contains() O(1):

private Set<String> processedIds = new HashSet<>();
public void process(Transaction tx) {
    if (!processedIds.add(tx.getId())) { // add() trả về false nếu đã tồn tại
        return;
    }
    // xử lý...
}

Throughput tăng cả nghìn lần.

Tình huống 2: Multi‑thread crash với NullPointerException bí ẩn

// ❌ HashMap không thread‑safe
private Map<String, User> cache = new HashMap<>();
// Nhiều thread put() cùng lúc → cấu trúc bên trong bị hỏng → NPE ngẫu nhiên

Fix: dùng ConcurrentHashMap – vừa thread‑safe vừa hiệu năng cao nhờ khóa phân đoạn / CAS.

private Map<String, User> cache = new ConcurrentHashMap<>();

Tình huống 3: Memory đầy nhưng không OutOfMemory – Memory leak

// ❌ Map giữ tất cả session vĩnh viễn
private Map<String, UserSession> sessions = new HashMap<>();

Mỗi session không bao giờ bị xóa → memory leak. Fix dùng một LinkedHashMap với access‑order và kích thước tối đa (LRU cache tự viết trong 10 dòng):

Map<String, UserSession> sessions = Collections.synchronizedMap(
    new LinkedHashMap<>(1000, 0.75f, true) {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, UserSession> eldest) {
            return size() > 1000;
        }
    }
);

Hoặc dùng thư viện Caffeine cho production.

Bạn đã thấy đấy, những bug trên đều bắt nguồn từ việc chọn sai collection. Để tránh chúng, ta phải hiểu rõ bên trong từng loại.

Hiểu sâu về List – ArrayList, LinkedList, ArrayDeque

ArrayList – Mảng tự động mở rộng

Bên trong ArrayList là một mảng Object[] elementData liên tục trong bộ nhớ.

Bố cục bộ nhớ (contiguous):
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│ A│ B│ C│ D│ E│ ?│ ?│ ?│ ?│ ?│   capacity = 10
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
              ↑
            size = 5

Các thao tác cơ bản:

get(i) / set(i, val): truy cập trực tiếp phần tử thứ i trong mảng → O(1).
add(val) ở cuối: elementData[size++] = val → amortized O(1) (thỉnh thoảng phải resize).
add(0, val): phải dịch tất cả các phần tử sang phải 1 vị trí bằng System.arraycopy → O(n).
remove(0): dịch trái toàn bộ → O(n).
contains(val): duyệt tuần tự → O(n).

Tại sao amortized O(1)?
Khi mảng đầy, ArrayList tạo mảng mới có dung lượng 1.5 lần hiện tại (oldCapacity + oldCapacity >> 1), rồi copy toàn bộ dữ liệu cũ sang. Chi phí copy là O(n), nhưng xảy ra rất hiếm (số lần resize log(n) khi thêm n phần tử), tính trung bình mỗi lần thêm là O(1) – gọi là amortized constant time.
Nếu biết trước kích thước, hãy khởi tạo với new ArrayList<>(dự_đoán) để tránh hàng loạt lần resize.

Khi nào dùng ArrayList?

Default cho mọi List<T>.
Ứng dụng đọc nhiều, truy cập ngẫu nhiên.
Thêm/xóa chủ yếu ở cuối.
Biết được dung lượng xấp xỉ.

LinkedList – Danh sách liên kết đôi

Mỗi phần tử là một Node chứa 3 tham chiếu: prev, item, next.

prev ←─ Node ─→ next ←─ Node ─→ next ←─ Node ─→ null
        item            item            item

Đặc điểm:

get(i): duyệt từ đầu hoặc cuối (tùy vị trí gần đâu hơn) → O(n).
addFirst(val) / addLast(val): O(1) nhưng tốn bộ nhớ hơn ArrayList gấp ~3 lần vì mỗi node chứa 3 tham chiếu + overhead của object.
Không có lợi thế về cache locality: các node nằm rải rác trong bộ nhớ, CPU cache prefetch kém hiệu quả.
Trong thực tế, ngay cả thêm/xóa ở giữa danh sách, ArrayList thường nhanh hơn LinkedList với tập dữ liệu vừa và nhỏ nhờ cache locality.

Khi nào dùng LinkedList?

Hàng đợi hai đầu? Nên dùng ArrayDeque.
Chỉ khi cần thêm/xóa liên tục ở một vị trí xác định qua Iterator (hiếm).
Thực tế, 95% trường hợp bạn nên chọn ArrayList.

ArrayDeque – Hàng đợi hai đầu dùng mảng vòng

Thay vì shift, ArrayDeque dùng mảng vòng với hai con trỏ head và tail:

[A, B, C, _, _, _, X, Y]
          ↑        ↑
        tail     head

addFirst() / addLast(), removeFirst() / removeLast(), peekFirst() / peekLast() đều O(1).
Không hỗ trợ truy cập ngẫu nhiên get(i) – đó là chủ đích thiết kế để đảm bảo tốc độ hai đầu.
Dùng thay cho Stack (lớp cũ, synchronized) và LinkedList cho Queue.

Deque<Integer> stack = new ArrayDeque<>(); // Stack LIFO
stack.push(1); stack.pop();

Deque<Integer> queue = new ArrayDeque<>(); // Queue FIFO
queue.offer(1); queue.poll();

So sánh tổng quát

Thao tác	ArrayList	LinkedList	ArrayDeque
`get(i)` ngẫu nhiên	O(1)	O(n)	❌
`add(val)` cuối	O(1) amortized	O(1)	O(1)
`addFirst(val)`	O(n)	O(1)	O(1)
`removeFirst()`	O(n)	O(1)	O(1)
`contains(val)`	O(n)	O(n)	O(n)
Bộ nhớ	Thấp	Cao (~3x)	Thấp
Cache locality	Tuyệt vời	Kém	Tuyệt vời

Nhớ: Dùng ArrayList làm mặc định, ArrayDeque cho Stack/Queue, hạn chế tối đa LinkedList.

Hiểu sâu về Map – HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap,…

HashMap – Bảng băm với cây dự phòng (từ Java 8)

Bên trong HashMap là một mảng các bucket; mỗi bucket chứa một linked list hoặc cây đỏ-đen (Red‑Black tree) khi xung đột nhiều.

table = [
  bucket 0 → Node(k1,v1) → Node(k2,v2)  (collision chain)
  bucket 1 → null
  bucket 2 → Node(k3,v3)
  bucket 3 → TreeNode(...)              (red‑black tree khi chain > 8)
  ...
]

Hash và bucket index:
Mã băm của key được trộn thêm một lần để phân tán tốt hơn:

static final int hash(Object key) {
    int h = key.hashCode();
    return h ^ (h >>> 16);  // XOR nửa cao với nửa thấp
}
int index = hash & (capacity - 1);   // capacity luôn lũy thừa 2

Việc dùng & (capacity - 1) thay cho % capacity giúp tính nhanh hơn. Để phép & hiệu quả, capacity phải là lũy thừa của 2.

Quá trình put() (đơn giản hóa):

Tính hash và bucket index.
Nếu bucket rỗng → đặt node mới vào.
Nếu bucket đã có node:
- Duyệt linked list để tìm key trùng (theo equals).
- Nếu tìm thấy → cập nhật value.
- Nếu không → thêm vào cuối chain. Nếu chiều dài chain vượt quá TREEIFY_THRESHOLD (8), chuyển toàn bộ chain thành cây đỏ-đen.
Sau khi thêm, nếu size > capacity * loadFactor (mặc định 0.75) → resize: tăng gấp đôi capacity và rehash toàn bộ entry. Chi phí O(n).

Bí mật ngưỡng 8 và 6:

Khi chain dài ≥ 8, bucket được treeify (chuyển thành cây) để tránh worst‑case O(n).
Khi chain ngắn ≤ 6, bucket được untreeify về linked list để tiết kiệm bộ nhớ và tránh dao động.
Giá trị 8 được chọn dựa trên xác suất Poisson: với hàm băm tốt, xác suất chain dài 8 là cực nhỏ (khoảng 0.00000006). Khi nó xảy ra, thường là do tấn công hoặc hashCode tồi.

Java 8 cải tiến gì?

Treeify: giảm worst‑case từ O(n) xuống O(log n) cho mỗi thao tác.
Hàm hash cải tiến: h ^ (h >>> 16) giúp trộn các bit cao (vốn bị bỏ qua nếu capacity nhỏ) vào các bit thấp – bucket phân phối đều hơn.

Mẹo khởi tạo dung lượng:
Để tránh resize, bạn có thể tính new HashMap<>(expectedSize / 0.75f + 1). Ví dụ muốn chứa 1000 phần tử: new HashMap<>(1334).

LinkedHashMap – Thứ tự chèn hoặc thứ tự truy cập (LRU)

Kế thừa HashMap, bổ sung danh sách liên kết đôi duy trì thứ tự các entry.

Insertion‑order (mặc định): thứ tự đúng như khi put.
Access‑order (new LinkedHashMap<>(16, 0.75f, true)): mỗi lần get hoặc put sẽ đẩy entry lên cuối danh sách – nền tảng của LRU Cache.

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;
    public LRUCache(int max) {
        super(max, 0.75f, true);
        this.maxSize = max;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

TreeMap – Cây đỏ-đen (Red‑Black Tree)

TreeMap cài đặt interface NavigableMap, sắp xếp key theo thứ tự tự nhiên hoặc Comparator.

Cấu trúc cây đỏ-đen:

Mỗi node có màu (đỏ/đen), thỏa các quy tắc: gốc đen, node đỏ không có con đỏ, mọi đường dẫn từ gốc đến lá có cùng số node đen.
Đảm bảo chiều cao tối đa ~2log₂(n) → các thao tác cơ bản O(log n).

So với AVL:
AVL cân bằng nghiêm ngặt hơn (chiều cao tối đa 1.44log₂(n)) nên tìm kiếm nhanh hơn một chút, nhưng chi phí xoay cao hơn trong thêm/xóa. Java chọn Red‑Black vì thêm/xóa diễn ra thường xuyên trong thực tế.

Ứng dụng đặc biệt – Truy vấn phạm vi (range query):

TreeMap<LocalDateTime, Transaction> txnByTime = new TreeMap<>();
// ... thêm transaction

NavigableMap<LocalDateTime, Transaction> recent =
    txnByTime.subMap(LocalDateTime.now().minusHours(1), LocalDateTime.now());
// Lấy tất cả giao dịch trong 1 giờ qua với O(log n)

HashMap không thể làm điều này – đó là lý do TreeMap tồn tại.

ConcurrentHashMap – An toàn đa luồng hiệu năng cao

Java 7 dùng Segment locking: chia map thành 16 segment, mỗi segment có khóa riêng, giúp các luồng truy cập vào các segment khác nhau không cản trở nhau.

Java 8+ bỏ segment, dùng cơ chế lock‑free tinh vi:

Đọc: luôn lock‑free (dùng volatile đọc).
Ghi vào bucket rỗng: sử dụng CAS (Compare‑And‑Swap) – không cần khóa.
Ghi vào bucket đã có node: synchronized chỉ trên node đầu tiên của bucket đó.
Resize: hợp tác (nhiều thread cùng giúp mở rộng), giảm thời gian dừng.

Những điểm cần lưu ý:

Không cho phép null key/value. Lý do: trong môi trường đa luồng, null gây nhập nhằng giữa “không có key” và “value là null”, vì giữa containsKey và get có thể bị thread khác can thiệp.
size() không phải ảnh chụp nguyên tử – chỉ là giá trị xấp xỉ. Dùng để giám sát thì được, không dùng để kiểm tra điều kiện đúng/sai.
Cung cấp nhiều thao tác nguyên tử: computeIfAbsent, merge, forEach, search…

So sánh với Collections.synchronizedMap:

	synchronizedMap	ConcurrentHashMap
Hạt nhỏ khóa	Toàn bộ map	Từng bucket / lock‑free
Đọc đồng thời	Chặn ghi	Lock‑free (cho phép ghi song song)
Ghi đồng thời	Tuần tự	Song song nếu khác bucket
An toàn khi duyệt	Cần synchronized block	Có (weakly consistent)
Throughput (16 thread)	~1×	~10‑50×

Luôn dùng ConcurrentHashMap cho multi‑thread, tránh synchronizedMap trong code mới.

Các Map đặc biệt đáng biết

Map	Đặc điểm
`EnumMap`	Key là enum, dùng mảng `ordinal()` → siêu nhanh, siêu tiết kiệm bộ nhớ.
`IdentityHashMap`	So sánh key bằng `==` thay vì `equals`, dùng trong serialization, proxy…
`WeakHashMap`	Entry tự động bị xóa khi key không còn được tham chiếu mạnh – cache tạm thời.

Set – Đơn giản nhưng vẫn có “cao thủ” EnumSet

Set thực chất là mặt nạ của Map (HashSet = HashMap với value dummy). Bảng tham khảo nhanh:

Set	Ứng dụng
`HashSet`	Mặc định, O(1)
`LinkedHashSet`	Giữ thứ tự chèn
`TreeSet`	Sắp xếp, O(log n)
`EnumSet`	Siêu nhanh cho key là enum
`ConcurrentHashMap.newKeySet()`	Thread‑safe Set

EnumSet đặc biệt đáng học: bên trong chỉ là một bitmap (64 bit long), cho phép các phép hợp, giao bằng toán tử bitwise.

Set<DayOfWeek> weekdays = EnumSet.range(DayOfWeek.MONDAY, DayOfWeek.FRIDAY);
EnumSet<DayOfWeek> weekend = EnumSet.complementOf(weekdays); // bitwise NOT

Với enum ≤ 64 giá trị, EnumSet dùng đúng 1 long, còn HashSet cần ít nhất 16 byte mỗi entry – tiết kiệm bộ nhớ gấp cả trăm lần.

Queue & PriorityQueue – Hàng đợi và đống nhị phân

PriorityQueue – Đống nhị phân (min‑heap mặc định)

Bên trong là mảng đại diện cho cây nhị phân gần đầy:

        1
      /   \
     3     2
    / \   / \
   5   4 7   6

Mảng: [1, 3, 2, 5, 4, 7, 6]
Cha của i: (i-1)/2, Con trái: 2*i+1, Con phải: 2*i+2

offer() (thêm): đặt vào cuối mảng rồi sift up – O(log n).
poll() (lấy nhỏ nhất): lấy gốc, đưa phần tử cuối lên rồi sift down – O(log n).
peek(): xem gốc O(1).
contains: quét tuyến tính O(n). Muốn tìm kiếm nhanh cần cấu trúc khác.

Ví dụ – Top K phần tử lớn nhất (dùng min‑heap kích thước K):

public List<Integer> topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll();
    }
    return new ArrayList<>(minHeap);  // K phần tử lớn nhất (không sắp xếp)
}
// O(n log k)

Tạo max‑heap với comparator ngược:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

BlockingQueue – Xương sống của Producer‑Consumer

Các hàng đợi chờ có sẵn trong java.util.concurrent:

ArrayBlockingQueue – kích thước cố định, dùng mảng.
LinkedBlockingQueue – tùy chọn giới hạn, dùng linked list.
SynchronousQueue – capacity 0, handoff trực tiếp.
DelayQueue – phần tử chỉ lấy được sau một khoảng trễ.

BlockingQueue<Task> queue = new LinkedBlockingQueue<>(100);
// Producer
queue.put(task);   // block nếu đầy
// Consumer
Task t = queue.take(); // block nếu rỗng

Đây chính là nền tảng của thread pool (ExecutorService).

Benchmark thực chiến với JMH – Không tin lý thuyết suông

Lý thuyết suông dễ đánh lừa. JMH (Java Microbenchmark Harness) là công cụ chuẩn để đo hiệu năng microbenchmark trong Java, xử lý các vấn đề như warmup JIT, dead‑code elimination, sai số đo lường.

Cài đặt JMH qua Maven

<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.37</version>
</dependency>
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.37</version>
    <scope>provided</scope>
</dependency>

Ví dụ benchmark: `ArrayList.get()` vs `LinkedList.get()`

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Warmup(iterations = 3, time = 1) // làm nóng JVM
@Measurement(iterations = 5, time = 1)
@Fork(1) // mỗi benchmark chạy trong JVM riêng
public class ListGetBenchmark {

    @Param({"1000", "10000", "100000"})
    private int size;

    private List<Integer> arrayList;
    private List<Integer> linkedList;
    private int randomIndex;

    @Setup
    public void setup() {
        arrayList = new ArrayList<>();
        linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }
        randomIndex = ThreadLocalRandom.current().nextInt(size);
    }

    @Benchmark
    public Integer arrayListGet() {
        return arrayList.get(randomIndex);
    }

    @Benchmark
    public Integer linkedListGet() {
        return linkedList.get(randomIndex);
    }
}

Kết quả tiêu biểu (ns/op):

Benchmark           size     time
arrayListGet        1000      ~3 ns    (O(1) ổn định)
arrayListGet       10000      ~3 ns
arrayListGet      100000      ~3 ns
linkedListGet       1000    ~500 ns    (O(n) tăng dần)
linkedListGet      10000   ~5000 ns
linkedListGet     100000  ~50000 ns    → chậm hơn 17000 lần!

Benchmark so sánh throughput `ConcurrentHashMap` vs `synchronizedMap`

@Threads(8)
public class MapThroughputBenchmark {

    @Benchmark
    public Integer syncMapPut() { ... }      // ~5 triệu ops/s
    @Benchmark
    public Integer concurrentMapPut() { ... } // ~80 triệu ops/s
}

Con số biết nói: ConcurrentHashMap nhanh hơn gấp 16 lần khi 8 thread ghi liên tục.

Chạy benchmark: mvn clean package && java -jar target/benchmarks.jar -rf json
Kết quả JSON có thể trực quan hóa tại https://jmh.morethan.io

8 Anti‑pattern kinh điển khi dùng Collections

Dùng LinkedList cho random access
for (int i=0; i<list.size(); i++) list.get(i) → O(n²). Thay bằng for‑each hoặc ArrayList.
Dùng Stack hoặc Vector
Đây là các lớp cũ đồng bộ hóa mọi phương thức, hiệu năng kém. Dùng ArrayDeque cho Stack, ArrayList cho danh sách.
Dùng Hashtable thay vì ConcurrentHashMap
Hashtable khóa toàn bộ map, trong khi ConcurrentHashMap cho phép đọc/ghi song song.
Autoboxing trong vòng lặp nóng
List<Integer> list lưu Integer object (16 byte mỗi phần tử) thay vì int (4 byte). Với dữ liệu lớn, dùng thư viện primitive như Eclipse Collections hoặc fastutil.
Dùng key có thể thay đổi (mutable) cho HashMap/HashSet
Nếu hashCode() thay đổi sau khi put, bạn không thể tìm lại entry. Luôn dùng key immutable.
removeAll trên hai ArrayList lớn – O(n×m).
Chuyển list thứ hai thành HashSet rồi dùng removeIf(set::contains) → O(n).
Arrays.asList rồi gọi add
Arrays.asList trả về fixed‑size list → ném UnsupportedOperationException. Bọc nó trong new ArrayList<>(...).
List.of / Set.of (immutable collections) rồi mutate
Các collection này bất biến, gọi add/remove sẽ gây lỗi.

Decision Tree – Cây quyết định chọn collection

Cần lưu trữ ___?
│
├── Cặp key‑value?
│   ├── Đa luồng? → ConcurrentHashMap
│   ├── Cần sắp xếp? → TreeMap (đơn) / ConcurrentSkipListMap (đa)
│   ├── LRU cache? → LinkedHashMap access‑order / Caffeine
│   ├── Key là enum? → EnumMap
│   └── Mặc định → HashMap
│
├── Tập hợp không trùng (Set)?
│   ├── Đa luồng? → ConcurrentHashMap.newKeySet()
│   ├── Có thứ tự? → TreeSet
│   ├── Giữ thứ tự chèn? → LinkedHashSet
│   ├── Element là enum? → EnumSet
│   └── Mặc định → HashSet
│
├── Danh sách có thứ tự (List)?
│   ├── Truy cập ngẫu nhiên (get(i))? → ArrayList
│   ├── Stack/Queue? → ArrayDeque
│   ├── Producer‑consumer? → BlockingQueue
│   ├── Độ ưu tiên? → PriorityQueue
│   └── Mặc định → ArrayList
│
└── Trường hợp đặc biệt:
    ├── So sánh identity (`==`)? → IdentityHashMap
    ├── Tự xóa khi GC? → WeakHashMap
    ├── Kiểu nguyên thủy? → Mảng `int[]` hoặc fastutil
    └── Dữ liệu khổng lồ? → Thư viện chuyên dụng (Eclipse Collections, Roaring Bitmap,…)

Gỡ rối phỏng vấn – Những câu hỏi thường gặp

Tầng 1 – Kiến thức bề mặt

H: ArrayList.add(0, val) có độ phức tạp gì?

O(n), vì phải dịch tất cả phần tử sang phải một vị trí bằng System.arraycopy. Nhiều bạn nhầm là O(1) vì nghĩ “thêm vào danh sách” nhưng thực tế chỉ đúng với add(val) ở cuối.

H: HashSet và HashMap khác nhau thế nào?

HashSet được cài đặt bằng một HashMap với value không đổi (một object PRESENT). API khác nhưng hiệu năng giống hệt. HashSet có add/contains, HashMap có put/get.

Tầng 2 – Hiểu sâu

H: Java 8 cải tiến gì trong HashMap?

Hai điểm chính:

Khi chain dài >8, chuyển thành cây đỏ-đen để tránh O(n). Khi chain ngắn <6, trả về linked list.

Hàm băm mới h ^ (h >>> 16) trộn thêm các bit cao để phân tán tốt hơn với bảng dung lượng nhỏ. Lý do: chống tấn công collision có thể gây DoS.

H: Tại sao ConcurrentHashMap không cho phép null key/value?

Trong môi trường đa luồng, null dễ gây nhập nhằng giữa “không tồn tại” và “giá trị null”. Nó buộc lập trình viên phải xử lý rõ ràng hơn. Nếu cần biểu diễn “không có”, dùng Optional hoặc sentinel object.

Tầng 3 – Thiết kế kiến trúc

H: Thiết kế thread‑safe LRU cache cho 1 triệu entry, multi‑thread.

Level 1: synchronizedMap bọc LinkedHashMap – đơn giản nhưng lock toàn bộ, bottleneck.
Level 2: ConcurrentHashMap + danh sách LRU riêng – phức tạp, dễ race condition.
Level 3: Dùng Caffeine – hỗ trợ chính sách TinyLFU, lock‑free read, write coalescing, thống kê.
Trong hệ thống phân tán: Caffeine (L1) + Redis (L2).

Checklist thành thạo

Hiểu rõ memory layout của ArrayList và LinkedList, giải thích được O(1) vs O(n).
Vẽ được sơ đồ HashMap: hash → bucket → chain → tree. Giải thích resize.
Viết được range query bằng TreeMap.subMap().
Phân biệt lock strategy của ConcurrentHashMap (Java 8) và synchronizedMap.
Tự implement LRU cache < 15 dòng với LinkedHashMap.
Trả lời đúng 9/10 câu hỏi chọn collection.
Nhận diện và sửa được 8 anti‑pattern trên.
Tự chạy thành công một benchmark JMH.
Giải được bài Top‑K với PriorityQueue.
Ước lượng bộ nhớ của HashMap<String, Integer> 1M entry.

Phụ lục: Memory Footprint – Tốn bao nhiêu RAM?

Trên JVM 64‑bit với -XX:+UseCompressedOops (mặc định):

Object	Kích thước (bytes)
Object header	12
Tham chiếu (4 byte)	4
`Integer` object	12(hdr)+4(int)=16
`HashMap.Node`	khoảng 48 (hdr, hash, key ref, value ref, next ref)

Bộ nhớ cho 1 triệu entry:

Collection	Dung lượng xấp xỉ
`ArrayList<Integer>`	~20 MB (ref + boxed Integer)
`HashMap<Integer, Integer>`	~80 MB (Node + array)
`TreeMap`	~120 MB
`IntArrayList` (fastutil)	~4 MB → tiết kiệm 5‑20 lần!

Hiểu rõ chi phí bộ nhớ giúp bạn chọn collection đúng đắn hơn, đặc biệt khi làm việc với dữ liệu lớn.

Hy vọng qua bài viết này, bạn không chỉ biết “dùng gì” mà còn hiểu “tại sao” – sẵn sàng cho những pha phỏng vấn khó và những hệ thống thực tế đòi hỏi hiệu năng cao.

Java Collections Deep Dive: Internals & Performance – Từ Lý Thuyết Đến Thực Tế