Array vs ArrayList — Khi nào primitive thắng wrapper

TL;DR: Array lưu trữ liên tiếp trong bộ nhớ — kích thước cố định, truy cập O(1), không boxing. ArrayList (danh sách động) tự mở rộng bằng cách sao chép backing array khi đầy, mỗi phần tử là một object wrapper chiếm nhiều RAM hơn. Junior dev thường reach ngay ArrayList<Integer> vì quen tay, nhưng cho 10 triệu phần tử thì int[] tốn ~40 MB còn ArrayList<Integer> tốn ~234 MB — gần 6 lần. Hiểu sự khác biệt giúp chọn đúng cấu trúc cho từng bài toán.

Junior dev viết code xử lý 10 triệu bản ghi — reach ngay ArrayList<Integer> vì quen tay. Build xong, deploy, rồi nhận alert OOMKilled: container bị kill vì vượt memory limit 512 MB. Nhìn lại: array số nguyên nguyên thuỷ cho cùng dữ liệu chỉ cần khoảng 40 MB; ArrayList<Integer> ngốn khoảng 234 MB — gấp gần 6 lần — cộng thêm GC pressure liên tục vì 10 triệu object Integer trên heap. Trong container 512 MB, ngần ấy heap cộng overhead JVM và khoảng trống GC cần để copy là đủ để chạm OOMKilled (chọn LinkedList<Integer> còn tệ hơn — gần 400 MB).

Bài này phân biệt array nguyên thuỷ, array boxed, danh sách động, danh sách bất biến — biết khi nào pick gì cho production.

1. Analogy — Tủ lạnh

Array nguyên thuỷ giống tủ lạnh mua đúng kích thước: bạn đo trước cần chứa bao nhiêu, mua cái vừa vặn. Không mở rộng được, nhưng không lãng phí kho chứa. Giá thành thấp, dùng ngay.

Danh sách động giống chính sách "mua tủ nhỏ, khi đầy thì mua tủ to hơn và chuyển đồ sang". Linh hoạt hơn — không cần biết trước sẽ chứa bao nhiêu. Nhưng mỗi lần chuyển tủ là một operation tốn kém (sao chép toàn bộ), và luôn có một khoảng trống dự phòng chưa dùng.

2. So sánh các cấu trúc — Chọn đúng cho đúng việc

Sự khác biệt quan trọng giữa Arrays.asList() và danh sách bất biến: Arrays.asList() trả về list có thể thay phần tử (gọi set), nhưng không thể add/remove (size cố định). Danh sách bất biến hoàn toàn immutable — cả size lẫn phần tử đều không thay đổi được.

3. Memory footprint — Tại sao gần 6 lần

Hiểu con số 6x xuất phát từ đâu để biết khi nào nó quan trọng.

graph TD
    A["Array nguyên thuỷ (10 triệu int)"]
    B["Array boxed (10 triệu Integer)"]
    C["Danh sách động (10 triệu Integer)"]
    D["Danh sách liên kết (10 triệu Integer)"]

    A --> |"~40 MB — 4 byte/phần tử"| E["1x baseline"]
    B --> |"~200 MB — 20 byte/phần tử"| F["5x"]
    C --> |"~234 MB — capacity slack ~17%"| G["~6x"]
    D --> |"~400 MB — Node overhead 24 byte"| H["10x"]

Array nguyên thuỷ (10 triệu phần tử):

• Header: 16 byte (object header 12 byte + array length 4 byte).
• Payload: 10M × 4 byte = 40 MB.
• Tổng: xấp xỉ 40 MB.

Array boxed (10 triệu phần tử):

• Header: 16 byte.
• 10M reference (compressed OOPs, heap dưới 32 GB): 10M × 4 byte = 40 MB.
• 10M object wrapper, mỗi cái 16 byte (12 byte header + 4 byte int value): 10M × 16 = 160 MB.
• Tổng: xấp xỉ 200 MB — gấp 5 lần array nguyên thuỷ.

Danh sách động với 10M phần tử:

• Tương đương array boxed backing: khoảng 200 MB.
• Object overhead: 24 byte (header + trường size + trường modCount + reference đến backing array).
• Capacity slack trung bình ~17% (bài 07 Module 1): thêm khoảng 34 MB dự phòng.
• Tổng: xấp xỉ 234 MB — gấp gần 6 lần array nguyên thuỷ.

Nhưng bài 04 Module 1 đã chỉ ra danh sách liên kết còn tệ hơn — mỗi phần tử thêm Node object 24 byte, đưa tổng lên 400 MB (10x). Danh sách động là giữa đường: boxing overhead giữ nguyên nhưng ít nhất không có Node overhead.

Bài 04 Module 1 (cache locality) đã giải thích thêm: array nguyên thuỷ không chỉ tiết kiệm RAM mà còn cache-friendly hơn — prefetcher hoạt động tốt khi data liền kề, không bị boxing phân tán.

4. Capacity vs size — Bẫy tưởng obvious nhất

Người học hay nhầm size với internal capacity. Đây là nguồn gốc của nhiều lỗi truy cập ngoài biên khó hiểu.

-- Khởi tạo danh sách động với capacity = 100
L <- new DynamicList(capacity=100)

print L.size()      -- 0: chưa add phần tử nào
-- L.get(50)       -- LỖI: Index 50 vượt quá size=0
                   -- capacity là 100 nhưng size = 0

-- Phải add trước:
for i <- 0 đến 99:
    L.add(i)

print L.size()      -- 100
print L.get(50)     -- 50: OK

Time: O(n) để fill Space: O(n)

Capacity là số slot sẵn sàng trong backing array — chỉ ảnh hưởng đến khi nào grow xảy ra. Size là số phần tử thực sự đã được add. get(index) kiểm tra index >= size và ném lỗi — không quan tâm đến capacity.

Bài 07 Module 1 (Case Study ArrayList.grow()) đã phân tích chi tiết cơ chế grow 1.5x và tại sao capacity tồn tại độc lập với size.

5. Iterator fail-fast — Lỗi concurrent modification

Một pitfall hay gặp khi làm việc với danh sách động: xóa phần tử trong lúc đang duyệt.

-- BUG: thay đổi danh sách trong khi đang duyệt
numbers <- DynamicList chứa [1, -2, 3, -4, 5]

for each x trong numbers:
    if x < 0:
        numbers.remove(x)   -- ConcurrentModificationException!

Time: O(n) Space: O(1)

Tại sao xảy ra? Danh sách động dùng bộ đếm modCount — tăng mỗi khi có thay đổi cấu trúc (add, remove, clear). Iterator snapshot giá trị expectedModCount khi được tạo. Mỗi lần gọi next(), iterator so sánh modCount hiện tại với expectedModCount — nếu khác nhau, ném lỗi ngay lập tức.

Cơ chế này là fail-fast: phát hiện bug sớm thay vì để iterator đi trên dữ liệu đã bị thay đổi và cho kết quả sai. Bài 07 Module 1 đã đề cập modCount trong context subList() — cùng mechanism.

-- CORRECT cách 1: dùng Iterator.remove() — cập nhật cả modCount lẫn expectedModCount
it <- numbers.iterator()
while it.hasNext():
    x <- it.next()
    if x < 0:
        it.remove()    -- an toàn: đồng bộ modCount

-- CORRECT cách 2: removeIf() — gọn hơn
numbers.removeIf(x -> x < 0)
-- Kết quả: [1, 3, 5]

Time: O(n) Space: O(1)

removeIf() gọn hơn và hiệu quả hơn: nó dùng iterator bên trong, thực hiện một lần duyệt duy nhất, và chỉ tăng modCount một lần ở cuối — không phải mỗi lần remove.

6. Pitfall tổng hợp

Pitfall 1 — Array nguyên thuỷ bọc trong Arrays.asList() trả về danh sách kích thước 1:

-- BUG: truyền nguyên cả mảng int vào asList
arr <- [1, 2, 3]   -- array nguyên thuỷ

wrong <- Arrays.asList(arr)
print wrong.size()   -- 1: list chứa 1 phần tử là cả mảng arr!
print wrong.get(0)   -- [I@... toString của mảng int

-- CORRECT: stream boxing
correct <- Arrays.stream(arr).boxed().toList()
print correct.size()  -- 3
print correct.get(0)  -- 1

Time: O(n) để stream+box Space: O(n)

Generics bị type erasure — Arrays.asList(T... a) với T = int[] (vì int không phải generic type) tạo ra danh sách int[] kích thước 1, không phải danh sách Integer. Dùng Arrays.stream(arr).boxed().toList() để có danh sách đúng.

Pitfall 2 — Arrays.asList(...) không cho phép add/remove:

fixed <- Arrays.asList(1, 2, 3)
fixed.set(0, 99)   -- OK: thay phần tử được
fixed.add(4)       -- UnsupportedOperationException!
fixed.remove(0)    -- UnsupportedOperationException!

Arrays.asList() trả về wrapper trực tiếp quanh backing array — không phải danh sách động. Backing array có kích thước cố định nên add/remove không được. Nếu cần danh sách có thể grow: new ArrayList<>(Arrays.asList(1, 2, 3)).

Pitfall 3 — Danh sách bất biến khác Collections.unmodifiableList():

immutable <- List.of(1, 2, 3)
immutable.set(0, 99)   -- UnsupportedOperationException!
immutable.add(4)       -- UnsupportedOperationException!

-- Collections.unmodifiableList() chỉ wrap — modify qua reference gốc vẫn được
mutable <- new ArrayList(List.of(1, 2, 3))
wrapped <- Collections.unmodifiableList(mutable)
mutable.add(4)             -- OK: modify qua reference gốc
print wrapped.size()       -- 4: thay đổi luôn cả wrapped!

Danh sách bất biến là thực sự immutable — không có reference nào đến backing data cho phép modify. Collections.unmodifiableList() chỉ wrap, không copy — modify qua reference gốc vẫn được và phản ánh vào wrapped view. Prefer danh sách bất biến khi muốn đảm bảo immutability.

7. Applied to tech — Khi nào array nguyên thuỷ thực sự thắng

Hot loop, numerical code: Quant finance (risk calculation trên portfolio), ML inner loop (dot product, matrix multiply), game physics (position update 60fps) — tất cả đều cần array nguyên thuỷ thay vì danh sách động. Lý do: zero boxing overhead, cache-friendly layout, hardware prefetcher hoạt động tối đa. Thực đo JMH trên Java 21: sum 10M int[] khoảng 8ms, ArrayList<Integer> khoảng 25ms — chênh 3x chỉ vì boxing.

API design — trả về interface, không concrete class:

-- SAI: lộ implementation detail ra ngoài
function getNames() -> ArrayList:
    ...

-- ĐÚNG: caller không cần biết là ArrayList hay LinkedList hay ImmutableList
function getNames() -> List:
    ...

Trả về List thay vì ArrayList để future-proof: bên trong có thể đổi sang Collections.unmodifiableList(), List.of(), hoặc custom implementation mà không break caller.

System.arraycopy() — JVM intrinsic nhanh hơn manual loop:

-- System.arraycopy là JVM intrinsic -- compile trực tiếp thành memcpy-equivalent
-- Nhanh hơn vòng lặp for thủ công khoảng 2-5x cho array lớn
-- ArrayList.toArray() cũng dùng nó bên dưới

Stream API — IntStream tránh boxing:

-- IntStream: không boxing, aggregate O(n) không có object allocation
sum1 <- Arrays.stream(primitiveArr).sum()   -- IntStream

-- Stream<Integer>: boxing từng phần tử trước khi sum
-- Cần mapToInt() để về IntStream
sum2 <- boxedList.stream().mapToInt(x -> x).sum()

Arrays.stream(int[]) trả về IntStream — stream của primitive int, không boxing. Với aggregate operation (sum, average, count) trên data lớn, dùng IntStream/LongStream/DoubleStream để tránh boxing overhead đáng kể.

Nếu bạn đang học về generics và collections trong Java context, khóa Java Module 08 — Generics and Collections có phân tích sâu hơn về type erasure và wildcard liên quan đến danh sách động.

8. Deep Dive tài liệu gốc

9. Tóm tắt

• Array nguyên thuỷ dùng 4 byte/phần tử; array boxed dùng 20 byte/phần tử (reference + object); danh sách động thêm capacity slack — tổng gấp 5-6x array nguyên thuỷ.
• Capacity khác size: khởi tạo danh sách động với capacity=100 tạo capacity = 100 nhưng size = 0; truy cập index 50 ném lỗi dù capacity đủ.
• Arrays.asList(int[]) là bẫy: trả về danh sách kích thước 1 chứa cả mảng, không phải danh sách Integer. Dùng stream boxed để chuyển đúng.
• Arrays.asList(...) fixed-size: có thể set nhưng không add/remove — UnsupportedOperationException.
• Danh sách bất biến immutable hoàn toàn: cả size lẫn phần tử. Khác với Collections.unmodifiableList() chỉ wrap — modify qua reference gốc vẫn được.
• Iterator fail-fast: lỗi concurrent modification khi modify danh sách động trực tiếp trong iteration. Fix bằng Iterator.remove() hoặc removeIf().
• Return List, không ArrayList: public API nên khai báo interface — future-proof, không lộ implementation.
• Hot path: IntStream tránh boxing; System.arraycopy() là JVM intrinsic nhanh hơn manual loop.

10. Tự kiểm tra

Bài tiếp theo: Linked list — singly vs doubly