Cấu trúc dữ liệu và Giải thuật Bài 26: Mảng xoay vòng (Circular Array) và phép toán Modulo.

Trong thế giới bộ nhớ tuyến tính, mảng tĩnh có một ranh giới vật lý cứng ngắc: Vị trí cuối cùng N - 1. Khi bạn liên tục thêm và xóa dữ liệu (như cơ chế Hàng đợi - Queue), các phần tử trôi dần về phía cuối mảng. Đến một lúc nào đó, dù phía đầu mảng (vị trí 0, 1, 2) đã trống trơn do dữ liệu cũ bị xóa, bạn vẫn không thể nhét thêm phần tử mới vào cuối vì đã chạm mép N - 1.

Để tái sử dụng không gian trống mà không phải dịch chuyển toàn bộ mảng (chi phí đắt đỏ $O(n)$), các kỹ sư uốn cong mảng thẳng thành một vòng tròn bất tận. Đó là cấu trúc Mảng xoay vòng (Circular Array).

1. Bản chất của Mảng xoay vòng

Không có "bộ nhớ hình tròn" nào tồn tại trong kiến trúc phần cứng. RAM vẫn là một dải băng dài thẳng tắp. Mảng xoay vòng hoàn toàn là một ảo giác toán học do lập trình viên tạo ra để "lừa" hệ thống.

Thay vì quản lý mảng bằng một con trỏ chạy thẳng, chúng ta quy ước: Phần tử liền sau vị trí cuối cùng N - 1 chính là vị trí 0.

Để thực hiện bước nhảy này mà không cần dùng đến các câu lệnh if (index == N) { index = 0 } rườm rà và dễ gây lỗi rẽ nhánh (branching) cho CPU, chúng ta sử dụng một công cụ toán học tối thượng: Phép chia lấy dư (Modulo %).

2. Công cụ kiểm soát vòng lặp: Toán tử Modulo

Toán tử % trả về phần dư của một phép chia. Khi bạn lấy bất kỳ một số nguyên nào đem chia lấy dư cho N (kích thước mảng), kết quả luôn luôn được khóa chặt trong khoảng từ 0 đến N - 1.

Cho mảng có kích thước N = 5:

• 0 % 5 = 0

• 4 % 5 = 4 (Vẫn nằm trong mảng)

• Điểm bùng phát: 5 % 5 = 0. Ngay khi chỉ mục vượt quá giới hạn, phép toán Modulo bẻ cong không gian, ném nó quay trở lại vạch xuất phát.

• 6 % 5 = 1

Công thức điều hướng cơ bản:

Giả sử bạn đang đứng ở vị trí current, mảng có kích thước N.

1. Tiến lên 1 bước:

   next = (current + 1) % N

2. Lùi lại 1 bước:

   prev = (current - 1 + N) % N

   (Lưu ý: Chúng ta phải cộng thêm N trước khi lấy Modulo để tránh việc current - 1 tạo ra số âm. Trong các ngôn ngữ như Golang hay C++, phép % trên số âm có thể trả về số âm, làm sập chương trình).

3. Mã nguồn minh họa: Bộ đệm vòng (Ring Buffer) đơn giản

Hãy xem cách chúng ta duy trì một luồng dữ liệu chạy liên tục không bao giờ gây tràn bộ nhớ (Buffer Overflow) bằng Golang.

Go

package main

import "fmt"

func main() {
    // Mảng tĩnh kích thước N = 5
    const N = 5
    buffer := [N]int{}
    
    // Giả lập luồng dữ liệu (Stream) ghi 8 phần tử liên tục vào mảng 5 ô nhớ
    streamData := []int{10, 20, 30, 40, 50, 60, 70, 80}
    
    writeIndex := 0
    
    for _, value := range streamData {
        // Ghi dữ liệu vào vị trí hiện tại
        buffer[writeIndex] = value
        
        fmt.Printf("Đã ghi %d vào vị trí %d -> Trạng thái mảng: %v\n", value, writeIndex, buffer)
        
        // Cập nhật vị trí tiếp theo bằng Modulo
        writeIndex = (writeIndex + 1) % N
    }
}

Mô phỏng bộ nhớ:

• Ghi 5 số đầu: Mảng đầy [10, 20, 30, 40, 50]. writeIndex nhảy về 0.

• Ghi số 60: Đè lên vị trí 0 $\rightarrow$ [60, 20, 30, 40, 50]. writeIndex nhảy lên 1.

• Ghi số 70, 80: Đè tiếp $\rightarrow$ [60, 70, 80, 40, 50].

  Hệ thống cứ thế chạy mãi mãi trong đúng 5 ô nhớ mà không cần cấp phát thêm một Byte RAM nào.

4. Ứng dụng ở tầng Kiến trúc Hệ thống & Phần cứng

Phép toán nhỏ bé này đang âm thầm gánh vác tải trọng của những hệ thống quy mô lớn nhất thế giới, cũng như những thiết bị vi điều khiển nhỏ bé nhất:

• Bộ cân bằng tải (Round-Robin Load Balancing): Khi bạn có 3 server backend chạy Nginx hoặc HAProxy, hệ thống cần chia đều các request từ người dùng. Bằng cách dùng mảng lưu IP của 3 server và công thức (currentIndex + 1) % 3, các request được lần lượt gửi đến Server 0 $\rightarrow$ Server 1 $\rightarrow$ Server 2 $\rightarrow$ Server 0, đảm bảo tải trọng phân bổ đều đặn tuyệt đối trong thời gian $O(1)$.

• Hệ thống Message Queue (Kafka / RabbitMQ): Cấu trúc Ring Buffer được dùng làm bộ đệm để xử lý các luồng sự kiện (Event-driven) liên tục. Khi người tiêu thụ (Consumer) chậm hơn người sản xuất (Producer), dữ liệu mới tạm thời vòng lại ghi đè lên dữ liệu quá cũ đã được xác nhận, giúp tối ưu hóa không gian lưu trữ cực độ.

• Thu thập dữ liệu IoT (Cảm biến nhúng ESP32 / STM32): Khi bạn lập trình vi điều khiển để đọc tín hiệu từ trạm thời tiết (nhiệt độ, độ ẩm) mỗi giây, RAM của thiết bị chỉ có vài chục KB. Bạn không thể mảng động append liên tục. Ring Buffer với kích thước tĩnh (ví dụ lưu đúng 60 giây gần nhất) là cách duy nhất để hệ thống hoạt động ổn định xuyên suốt nhiều tháng trời mà không cạn kiệt bộ nhớ.

Hiểu về sự linh hoạt của chỉ mục, chúng ta đã sẵn sàng đối mặt với những bài toán trinh thám dữ liệu thực sự. Ở bài học tiếp theo, chúng ta sẽ xem xét cách toán học và các phép toán thao tác Bit (Bitwise) có thể giúp bạn tìm ra một hồ sơ bị mất tích giữa hàng triệu hồ sơ chỉ trong nháy mắt.