Cấu trúc dữ liệu và Giải thuật Bài 13: Mảng động (Dynamic Array): Cơ chế tự động mở rộng kích thước (Resizing).

Ở bài học trước, chúng ta đã thấy Mảng tĩnh (Static Array) có một điểm yếu chí mạng: Kích thước bị "đóng băng" vĩnh viễn lúc biên dịch. Trong thế giới thực, bạn hiếm khi biết trước một bài viết có bao nhiêu comment, hay một giỏ hàng sẽ có bao nhiêu sản phẩm.

Để giải quyết vấn đề này, các ngôn ngữ lập trình hiện đại đã tạo ra Mảng động (Dynamic Array). Nó được gọi bằng nhiều cái tên: Slice trong Golang, ArrayList trong Java, std::vector trong C++, hay đơn giản là Array trong JavaScript và Python. Vậy phép màu nào giúp chúng tự động co giãn được?

1. Mảng động không phải là phép thuật

Điều đầu tiên bạn cần khắc cốt ghi tâm: Ở tầng vật lý của RAM, không tồn tại cái gọi là bộ nhớ tự động co giãn.

Mảng động bản chất chỉ là một lớp bọc thông minh (Wrapper) bao quanh một Mảng tĩnh. Khi bạn làm việc với một Slice trong Golang, bạn đang giao tiếp với một cấu trúc dữ liệu (struct) chứa đúng 3 thông tin:

1. Con trỏ (Pointer): Trỏ tới địa chỉ ô nhớ đầu tiên của mảng tĩnh thực sự nằm bên dưới RAM.

2. Length (Kích thước thực tế - $n$): Số lượng phần tử bạn đang thực sự sử dụng.

3. Capacity (Sức chứa tối đa): Kích thước của cái mảng tĩnh đang nằm bên dưới.

Chừng nào Length < Capacity, thao tác thêm phần tử (append) chỉ tốn $O(1)$ thời gian, y hệt như mảng tĩnh. Nhưng chuyện gì sẽ xảy ra khi Length == Capacity? Đó là lúc cơ chế Resizing (Mở rộng kích thước) được kích hoạt.

2. Cơ chế Resizing: "Chuyển nhà" trong bộ nhớ

Hãy tưởng tượng bạn thuê một căn phòng trọ chứa được tối đa 3 người (Capacity = 3). Khi người thứ 4 muốn chuyển vào, bạn không thể đập tường của hàng xóm để nới rộng phòng ra được (vì ô nhớ bên cạnh có thể đã bị biến khác chiếm dụng).

Cách duy nhất là: Chuyển nhà. Hệ thống sẽ thực hiện 4 bước sau một cách hoàn toàn tự động (ngầm):

1. Cấp phát: Hệ điều hành tìm một dải RAM mới, rộng rãi hơn. Thường là gấp đôi kích thước cũ (Capacity mới = 6).

2. Copy: Sao chép từng người (từng phần tử) từ nhà cũ sang nhà mới. Bước này ngốn thời gian $O(n)$.

3. Chèn: Đưa phần tử mới (người thứ 4) vào vị trí tiếp theo trong nhà mới.

4. Giải phóng: Phá bỏ nhà cũ (Giải phóng bộ nhớ / Garbage Collection thu hồi).

3. Tại sao lại tăng gấp đôi (x2) mà không phải tăng thêm 1?

Đây là một câu hỏi phỏng vấn kinh điển. Tại sao khi mảng đầy, hệ thống không chỉ cấp phát thêm 1 ô nhớ, mà lại hào phóng cấp hẳn gấp đôi số lượng hiện tại?

• Nếu tăng thêm 1 ô mỗi lần đầy: Để thêm $n$ phần tử, hệ thống sẽ phải "chuyển nhà" $n$ lần. Lần 1 copy 1 phần tử, lần 2 copy 2 phần tử... Tổng số phép copy sẽ là $1 + 2 + 3 + ... + n = O(n^2)$. Thao tác append trở thành một thảm họa hiệu năng.

• Nếu tăng gấp đôi (x2): Bằng việc nhân đôi kích thước, các lần "chuyển nhà" sẽ thưa thớt dần. Áp dụng lại Amortized Analysis (Phân tích khấu hao - Bài 8), chi phí khổng lồ $O(n)$ của những lần copy hiếm hoi sẽ được chia đều cho vô số lần chèn $O(1)$ trước đó. Về mặt toán học, chi phí trung bình cho mỗi lần chèn lại trở về mức hoàn hảo: $O(1)$ Khấu hao (Amortized).

Góc nhìn hệ thống: Trong Golang, thuật toán tăng kích thước Slice không bám cứng vào x2. Khi mảng còn nhỏ (dưới 1024 phần tử), nó nhân đôi (x2). Nhưng khi mảng đã quá khổng lồ, nó chỉ tăng thêm khoảng 25% mỗi lần (x1.25) để tránh việc cấp phát thừa thãi một lượng RAM khổng lồ nhưng không dùng tới.

4. Bài học thực chiến: Pre-allocation (Cấp phát trước)

Sự tiện lợi của Mảng động khiến nhiều lập trình viên sinh lười. Hãy xem đoạn code Golang tồi tệ nhưng rất phổ biến sau:

Go

// BAD CODE: Khai báo slice rỗng với Capacity = 0
var data []int 
for i := 0; i < 10000; i++ {
    data = append(data, i) 
}

Trong vòng lặp này, vì Capacity ban đầu bằng 0, mảng sẽ liên tục bị đầy. Nó phải thực hiện thao tác "chuyển nhà" (cấp phát RAM mới, copy dữ liệu, hủy RAM cũ) khoảng 14 lần trước khi đạt đủ sức chứa cho 10,000 phần tử. Rất tốn CPU và tạo ra nhiều "rác" (Garbage) trong bộ nhớ.

Cách kỹ sư tối ưu:

Nếu bạn đã lường trước (hoặc ước lượng được) số lượng phần tử tối đa, hãy chỉ định sẵn Capacity ngay từ lúc khởi tạo.

Go

// GOOD CODE: Khai báo slice với Length = 0, Capacity = 10000
data := make([]int, 0, 10000)
for i := 0; i < 10000; i++ {
    data = append(data, i) 
}

Lúc này, vòng lặp chạy một mạch 10,000 lần mà không phải trải qua bất kỳ một lần "chuyển nhà" nào. Tốc độ thực thi được cải thiện đáng kể, CPU không bị phân tâm bởi việc cấp phát bộ nhớ.

Như vậy, Mảng động đã giải quyết được bài toán kích thước linh hoạt, nhưng nó vẫn không thể khắc phục được điểm yếu cố hữu của Mảng: Thao tác chèn hoặc xóa ở giữa mảng vẫn tốn $O(n)$ thời gian do phải dịch chuyển dữ liệu.

Thế giới Cấu trúc dữ liệu chưa dừng lại ở dữ liệu 1 chiều. Trước khi chuyển sang các kỹ thuật tối ưu mảng, chúng ta hãy nâng cấp tư duy không gian với loại mảng phức tạp hơn: Mảng đa chiều (Ma trận).