Cấu trúc dữ liệu

Mặc dù cú pháp của ngôn ngữ Go rất đơn giản nhưng nó tích hợp sẵn nhiều cấu trúc dữ liệu cốt lõi mạnh mẽ. Những cấu trúc dữ liệu này là các khối xây dựng cơ bản của chương trình Go, việc hiểu sâu nguyên lý triển khai của chúng sẽ giúp viết code hiệu quả hơn. Bài viết này sẽ giới thiệu một vài cấu trúc dữ liệu thường dùng nhất trong Go và cách triển khai底层 của chúng.

Cấu trúc dữ liệu cơ bản

slice Slice

Slice là cấu trúc dữ liệu thường dùng nhất trong ngôn ngữ Go, là sự trừ tượng và đóng gói của mảng. Các đặc điểm chính:

• Kích thước động: Độ dài của slice có thể tăng trưởng động
• Ngữ nghĩa tham chiếu: Khi truyền slice chỉ sao chép cấu trúc, không sao chép mảng底层
• Cơ chế mở rộng: Khi dung lượng không đủ sẽ tự động mở rộng

Slice được biểu diễn bởi cấu trúc slice trong runtime, bao gồm con trỏ trỏ đến mảng底层, độ dài và dung lượng ba trường.

string Chuỗi

String là một trong những kiểu dữ liệu cơ bản nhất trong Go, các đặc điểm chính:

• Không thể thay đổi: String một khi được tạo thì không thể sửa đổi
• Mã hóa UTF-8: Thường biểu diễn văn bản mã hóa UTF-8
• An toàn với giá trị零: Giá trị零 của string là chuỗi rỗng "", không phải nil

String được biểu diễn bởi cấu trúc stringStruct trong runtime, bao gồm con trỏ trỏ đến mảng byte và độ dài.

Cấu trúc dữ liệu container

map Bảng ánh xạ

map là container键值对 tích hợp sẵn trong ngôn ngữ Go, được triển khai bằng bảng băm ở底层. Các đặc điểm chính:

• Triển khai bảng băm: Định vị phần tử nhanh chóng thông qua hàm băm
• Tự động mở rộng: Khi hệ số tải quá cao sẽ tự động mở rộng
• Không an toàn đồng thời: Đọc ghi đồng thời cần cơ chế đồng bộ bổ sung

map được biểu diễn bởi cấu trúc hmap trong runtime, bao gồm mảng bucket, hạt giống băm, số đếm phần tử và các trường khác.

syncmap Ánh xạ đồng thời

sync.Map là ánh xạ an toàn đồng thời được cung cấp bởi thư viện chuẩn, phù hợp cho các tình huống đọc nhiều ghi ít. Các đặc điểm chính:

• Phân tách đọc ghi: Sử dụng hai map read và dirty để triển khai phân tách đọc ghi
• Thao tác nguyên tử: read map sử dụng thao tác nguyên tử, không cần khóa
• Di chuyển dần dần: Khi đếm miss đạt ngưỡng sẽ nâng dirty thành read

sync.Map thông qua cách đổi không gian lấy thời gian, trong các tình huống cụ thể cung cấp hiệu suất tốt hơn so với map + mutex.

Cấu trúc dữ liệu đồng thời

channel Kênh

channel là đại diện tiêu biểu cho tư tưởng CSP của ngôn ngữ Go, được dùng cho giao tiếp giữa các goroutine. Các đặc điểm chính:

• Giao tiếp goroutine: Truyền dữ liệu giữa các goroutine thông qua channel
• Cơ chế đồng bộ: channel không đệm có thể dùng cho đồng bộ goroutine
• Hàng đợi có khóa:底层 là hàng đợi vòng có khóa

channel được biểu diễn bởi cấu trúc hchan trong runtime, bao gồm bộ đệm vòng, hàng đợi chờ và các trường khác.

select Đa路复用

select có thể监听 trạng thái của nhiều channel cùng lúc, triển khai đa路复用. Các đặc điểm chính:

• Không chặn: Có thể kiểm tra nhiều channel có sẵn hay không một cách không chặn
• Lựa chọn ngẫu nhiên: Khi nhiều channel cùng sẵn sàng sẽ chọn ngẫu nhiên một cái để thực thi
• Kiểm soát超时: Kết hợp với time.After để triển khai cơ chế超时

select được biểu diễn bởi cấu trúc scase cho mỗi nhánh trong runtime, thông qua cơ chế轮询 để kiểm tra trạng thái channel.

Gợi ý học tập

Đề xuất học theo thứ tự sau:

1. Trước hết học slice Slice và string Chuỗi, hiểu cấu trúc dữ liệu cơ bản
2. Sau đó học map Bảng ánh xạ, hiểu cách triển khai bảng băm
3. Rồi học channel Kênh, hiểu cơ chế giao tiếp goroutine
4. Tiếp theo học select Đa路复用, nắm vững kỹ thuật đa路复用
5. Cuối cùng học syncmap Ánh xạ đồng thời, hiểu cách triển khai an toàn đồng thời