Cấu trúc dữ liệu và Giải thuật Bài 11: Bản chất của Mảng tĩnh: Khai báo, cấp phát bộ nhớ liên tục.

Mọi hệ thống phần mềm phức tạp đều được xây dựng từ những viên gạch nền tảng nhất, và trong thế giới Cấu trúc dữ liệu, viên gạch đầu tiên và quan trọng nhất chính là Mảng tĩnh (Static Array). Dù bạn đang quản lý hàng triệu luồng dữ liệu hay lập trình một con chip vi điều khiển bé bằng móng tay, hiểu thấu đáo về mảng tĩnh là bắt buộc.

1. Mảng tĩnh là gì?

Mảng tĩnh là một cấu trúc dữ liệu lưu trữ một tập hợp các phần tử có cùng kiểu dữ liệu (ví dụ: toàn số nguyên, toàn ký tự) và được xếp cạnh nhau liên tiếp trong bộ nhớ vật lý (RAM).

Chữ "Tĩnh" (Static) mang hai ý nghĩa cốt lõi:

1. Kích thước cố định: Ngay tại thời điểm khai báo (lúc biên dịch chương trình), bạn phải báo cho máy tính biết chính xác mảng này chứa được bao nhiêu phần tử. Một khi đã khởi tạo, kích thước này bị "đóng băng" trọn đời. Bạn không thể nhét thêm phần tử thứ 6 vào một mảng kích thước 5.

2. Cấp phát một lần: Bộ nhớ được hệ điều hành "khoanh vùng" một lần duy nhất tạo thành một khối liền khối.

2. Bí mật tốc độ $O(1)$: Cấp phát bộ nhớ liên tục

Nhớ lại Bài 2 về RAM Model, sức mạnh thực sự của mảng tĩnh nằm ở cơ chế Cấp phát bộ nhớ liên tục (Contiguous Memory Allocation).

Hãy xem đoạn mã C++ sau — ngôn ngữ thể hiện bản chất bộ nhớ rõ nét nhất:

C++

int scores[5] = {10, 20, 30, 40, 50};

Kiểu int trong C++ thường chiếm 4 Bytes. Khi dòng code này chạy, hệ điều hành sẽ làm một phép toán đơn giản: $5 \times 4 = 20$ Bytes. Sau đó, nó tìm trong RAM một dải 20 Bytes còn trống nằm liền kề nhau và cấp phát cho biến scores.

Giả sử ô nhớ đầu tiên (scores[0]) bắt đầu tại địa chỉ 1000. Cấu trúc trong RAM sẽ trông như thế này:

• scores[0]: Địa chỉ 1000 $\rightarrow$ 1003 (chứa giá trị 10)

• scores[1]: Địa chỉ 1004 $\rightarrow$ 1007 (chứa giá trị 20)

• scores[2]: Địa chỉ 1008 $\rightarrow$ 1011 (chứa giá trị 30)

• scores[3]: Địa chỉ 1012 $\rightarrow$ 1015 (chứa giá trị 40)

• scores[4]: Địa chỉ 1016 $\rightarrow$ 1019 (chứa giá trị 50)

Khi bạn muốn lấy phần tử scores[3], máy tính không hề duyệt từ phần tử 0 đến 3. Nó dùng công thức toán học nội tại (Pointer Arithmetic):

Địa chỉ đích = Địa chỉ bắt đầu + (Chỉ mục $\times$ Kích thước 1 phần tử)

$\rightarrow 1000 + (3 \times 4) = 1012$.

Nhờ tính toán trực tiếp được địa chỉ đích, việc truy xuất bất kỳ phần tử nào trong mảng tĩnh chỉ mất thời gian $O(1)$.

3. Ảo giác Mảng trong các ngôn ngữ bậc cao

Một kỹ sư backend cần cực kỳ tỉnh táo khi định nghĩa "Mảng" trong các ngôn ngữ lập trình khác nhau, vì không phải "Mảng" nào cũng là Mảng tĩnh.

• Golang & C/C++: Hỗ trợ mảng tĩnh thực sự. Trong Go, [5]int là mảng tĩnh (kích thước là một phần của kiểu dữ liệu), trong khi []int lại là Slice (Mảng động).

• PHP: Kiểu array() mà bạn thường dùng (như $arr = [1, 2, 3]) không phải là mảng tĩnh. Dưới mảng PHP là một cấu trúc dữ liệu cực kỳ phức tạp gọi là Ordered Hash Table (Bảng băm có thứ tự). Nó cho phép bạn trộn lẫn kiểu dữ liệu ($arr = [1, "string", true]) và tự động co giãn kích thước. Tiện lợi, nhưng tốn nhiều RAM hơn và mất đi đặc tính Spatial Locality (cục bộ không gian) thuần túy của mảng vật lý.

• JavaScript: Tương tự PHP, mảng trong JS bản chất là các Object được thiết kế lại, hoạt động như Hash Map hoặc Dynamic Array tùy vào engine của trình duyệt (như V8).

Khi bạn lập trình nhúng cho vi điều khiển (như STM32, ESP32) với bộ nhớ RAM cực kỳ hạn hẹp, việc sử dụng các cấu trúc mảng động hoặc Hash Map gần như là tự sát. Mảng tĩnh bằng C/C++ là lựa chọn duy nhất để kiểm soát chính xác từng Byte bộ nhớ.

4. Trúng độc đắc và Đánh đổi

Ưu điểm tuyệt đối:

1. Truy xuất cực nhanh: Nhờ $O(1)$ indexing.

2. Thân thiện với Cache: Do bộ nhớ nằm liền kề, CPU có thể bốc cả một cụm mảng tĩnh lên CPU Cache (L1/L2) trong một lần đọc, loại bỏ hoàn toàn tình trạng Cache Miss.

Hạn chế "chí mạng":

1. Lãng phí hoặc Tràn bộ nhớ (Overflow): Nếu bạn khai báo mảng 1000 phần tử nhưng chỉ dùng 10, bạn lãng phí 990 ô nhớ (RAM bị chiếm dụng vô ích). Ngược lại, nếu dữ liệu bất ngờ tăng lên 1001, chương trình sẽ crash hoặc ghi đè dữ liệu rác (Buffer Overflow) vì mảng không thể tự phình to.

2. Chi phí chèn/xóa cực đắt: Nếu muốn nhét một người mới vào giữa một hàng ghế đã ngồi kín, bạn phải yêu cầu tất cả những người từ vị trí đó trở về sau lùi lại một ghế. Trong bộ nhớ cũng vậy.

Sự bất tiện trong việc thêm, sửa, xóa chính là bài toán thực tế mà bạn phải giải quyết hàng ngày. Ở bài học tiếp theo, chúng ta sẽ bắt tay vào việc thao tác dữ liệu trên mảng và phân tích chi phí đắt đỏ của việc dịch chuyển bộ nhớ.