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

TL;DR: Array lưu các phần tử liên tiếp trong bộ nhớ: kích thước cố định, truy cập O(1), không boxing (không phải bọc số vào object). ArrayList tự mở rộng bằng cách sao chép mảng nền sang mảng lớn hơn khi đầy, và mỗi phần tử là một object bọc ngoài (wrapper) nên chiếm nhiều RAM hơn. Junior dev hay dùng ngay ArrayList<Integer> vì quen tay, nhưng với 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 khác biệt này giúp bạn chọn đúng cấu trúc cho từng bài toán.

Một junior viết code xử lý 10 triệu bản ghi, dùng ngay ArrayList<Integer> vì quen tay. Deploy xong thì nhận alert OOMKilled: container 512 MB bị kill vì hết bộ nhớ. Nhìn lại, int[] cho cùng dữ liệu chỉ cần khoảng 40 MB, còn ArrayList<Integer> ngốn khoảng 234 MB. Cộng thêm chi phí phụ của JVM và khoảng trống GC cần để dọn dẹp, ngần ấy là đủ chạm trầ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, ArrayList và List.of(), để bạn biết khi nào chọn cái nào trong code thật.

1. Hình dung: 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 rồi mua cái vừa vặn. Không mở rộng được, nhưng không lãng phí chỗ chứa. Giá rẻ, dùng ngay.

ArrayList giống chính sách "mua tủ nhỏ, khi đầy thì mua tủ to hơn và chuyển đồ sang". Cách này linh hoạt hơn vì không cần biết trước sẽ chứa bao nhiêu. Nhưng mỗi lần chuyển tủ rất tốn công (sao chép toàn bộ), và lúc nào cũng 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

Khác biệt quan trọng giữa Arrays.asList() và List.of(): Arrays.asList() trả về list cho thay phần tử (gọi set) nhưng không cho add/remove vì size cố định. List.of() bất biến hoàn toàn: cả size lẫn phần tử đều không đổi được.

3. Memory footprint: vì sao gần 6 lần

Con số 6x đến từ đâu? Biết rõ thì mới biết khi nào nó đáng lo.

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 tham chiếu (compressed OOPs, tức con trỏ nén 4 byte khi heap dưới 32 GB): 10M × 4 byte = 40 MB.
• 10M object bọc (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ỷ.

ArrayList với 10M phần tử:

• Mảng nền giống array boxed: khoảng 200 MB.
• Bản thân object ArrayList: 24 byte (header + trường size + trường modCount + tham chiếu đến mảng nền).
• Phần capacity chừa trống trung bình ~17% (xem ArrayList.grow()): 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 cache locality ở Module 1 đã chỉ ra LinkedList còn tệ hơn: mỗi phần tử thêm một Node object 24 byte, đưa tổng lên 400 MB (10x). ArrayList đứng giữa: vẫn tốn vì boxing nhưng không có Node.

Array nguyên thuỷ không chỉ tiết kiệm RAM mà còn thân thiện với cache hơn: prefetcher (bộ phận CPU đọc trước dữ liệu) chạy tốt khi dữ liệu nằm liền nhau, không bị boxing rải khắp heap. Muốn xem vì sao và cách viết code tận dụng điều đó, đọc Code thân thiện với cache.

Thử ngẫmcontainer của bạn giới hạn heap 512 MB. Theo bảng trên, cấu trúc nào trong bốn cái là ranh giới sống chết cho 10 triệu phần tử?

4. Capacity và size: bẫy tưởng hiển nhiên nhất

Người học hay nhầm size với capacity bên trong. Đây là nguồn gốc của nhiều lỗi truy cập ngoài biên khó hiểu. (Nếu chưa quen việc đi qua mảng bằng chỉ số 0 .. size-1 trong vòng lặp, ôn lại ở For và danh sách.)

-- Khởi tạo `ArrayList` 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ố ô trống sẵn có trong mảng nền, và chỉ quyết định khi nào mảng phải nở thêm. Size là số phần tử đã thật sự được add. get(index) kiểm tra index >= size rồi ném lỗi, không quan tâm đến capacity.

Bài ArrayList.grow() phân tích chi tiết cơ chế nở 1.5 lần và vì sao capacity tồn tại độc lập với size.

5. Iterator fail-fast và lỗi concurrent modification

Một cái bẫy hay gặp với ArrayList: xoá 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)

Vì sao lỗi xảy ra? ArrayList có bộ đếm modCount, tăng mỗi khi cấu trúc list thay đổi (add, remove, clear). Lúc được tạo, iterator chụp lại giá trị đó vào expectedModCount. Mỗi lần gọi next(), iterator so modCount hiện tại với expectedModCount; nếu khác nhau, nó ném lỗi ngay.

Cơ chế này gọi là fail-fast: báo lỗi sớm, thay vì để iterator chạy tiếp trên dữ liệu đã bị đổi và cho kết quả sai. Bài ArrayList.grow() cũng nhắc modCount khi nói về subList(), cùng một cơ chế.

-- ĐÚNG 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

-- ĐÚNG 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() vừa gọn vừa nhanh hơn: nó dùng iterator bên trong, chỉ duyệt một lần, và chỉ tăng modCount một lần ở cuối thay vì mỗi lần remove.

Fail-fast chỉ là phát hiện cố hết sức khi nhiều thread cùng sửa list, nên đừng dựa vào nó để đảm bảo an toàn đa luồng.

6. Các bẫy hay gặp

Bẫy 1: bọc array nguyên thuỷ trong Arrays.asList() ra 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@... là toString của mảng int

-- ĐÚNG: dùng 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)

Vì int không thể làm kiểu generic, Arrays.asList(T... a) hiểu T = int[] và tạo ra danh sách chứa một phần tử kiểu int[], không phải danh sách Integer. Dùng Arrays.stream(arr).boxed().toList() để có danh sách đúng.

Bẫy 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ề lớp bọc trực tiếp quanh mảng gốc, không phải ArrayList. Mảng có kích thước cố định nên add/remove không được. Nếu cần danh sách nở được: new ArrayList<>(Arrays.asList(1, 2, 3)).

Bẫy 3: List.of() khác Collections.unmodifiableList():

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

-- Collections.unmodifiableList() chỉ bọc ngoài — sửa qua tham chiếu gốc vẫn được
mutable <- new ArrayList(List.of(1, 2, 3))
wrapped <- Collections.unmodifiableList(mutable)
mutable.add(4)             -- OK: sửa qua tham chiếu gốc
print wrapped.size()       -- 4: wrapped cũng đổi theo!

List.of() bất biến thật: không có tham chiếu nào tới dữ liệu gốc để sửa. Collections.unmodifiableList() chỉ bọc ngoài, không sao chép, nên sửa qua tham chiếu gốc vẫn được và thay đổi hiện ra ở list đã bọc. Muốn đảm bảo bất biến thì nên chọn List.of().

Thử ngẫmcả ba bẫy trên đều bắt nguồn từ việc nhầm Arrays.asList()/List.of() với ArrayList thật. Khi nhận một list từ hàm khác, bạn làm sao biết nó sửa được hay không mà không cần thử .add() rồi bắt exception?

7. Dùng ở đâu trong thực tế: khi nào array nguyên thuỷ thắng

Vòng lặp nóng, code tính toán số: tài chính định lượng (tính rủi ro cho cả danh mục), vòng lặp trong ML (tích vô hướng, nhân ma trận), vật lý game (cập nhật vị trí 60 khung hình/giây) đều cần array nguyên thuỷ thay vì ArrayList. Lý do: không tốn chi phí boxing, dữ liệu xếp liền nhau, và prefetcher của phần cứng phát huy hết công suất. Khi đo bằng JMH, cộng 10M phần tử int[] thường nhanh hơn ArrayList<Integer> vài lần, phần chênh chủ yếu đến từ boxing (con số cụ thể tuỳ máy, nên tự đo).

Thiết kế API: trả về interface, không trả về lớp cụ thể:

-- SAI: lộ chi tiết cài đặt ra ngoài
function getNames() -> ArrayList:
    ...

-- ĐÚNG: bên gọi không cần biết là ArrayList, LinkedList hay ImmutableList
function getNames() -> List:
    ...

Trả về List thay vì ArrayList để sau này dễ đổi: bên trong có thể chuyển sang Collections.unmodifiableList(), List.of() hoặc bản tự cài mà không làm hỏng code bên gọi.

Stream API: IntStream tránh được boxing:

-- IntStream: không boxing, tổng hợp O(n) mà không cấp phát object
sum1 <- Arrays.stream(primitiveArr).sum()   -- IntStream

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

Arrays.stream(int[]) trả về IntStream, tức stream của int nguyên thuỷ, không boxing. Với các phép tổng hợp (sum, average, count) trên dữ liệu lớn, hãy dùng IntStream/LongStream/DoubleStream để tránh chi phí boxing đáng kể.

8. Đào sâu: tài liệu gốc

9. Tóm tắt

• Chọn cấu trúc theo lượng RAM: với 10 triệu phần tử, int[] ~40 MB, Integer[] ~200 MB, ArrayList<Integer> ~234 MB, LinkedList<Integer> ~400 MB.
• Gặp ArrayList lỗi ngoài biên thì nhớ capacity khác size: new ArrayList<>(100) vẫn có size = 0.
• Xoá phần tử khi đang duyệt thì dùng Iterator.remove() hoặc removeIf(), đừng gọi remove() trực tiếp trên list.
• Arrays.asList(int[]) ra list 1 phần tử; Arrays.asList(...) cho set nhưng không add/remove; List.of() bất biến thật, khác Collections.unmodifiableList() chỉ là lớp bọc.
• API công khai trả về List, không trả ArrayList; hot path số liệu thì dùng int[] hoặc IntStream để tránh boxing.

10. Tự kiểm tra

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