Bộ sưu tập (Collections)

Định nghĩa

Bộ sưu tập (Collections) trong C# là các cấu trúc dữ liệu dùng để lưu trữ, tổ chức và quản lý các nhóm đối tượng liên quan. Thư viện .NET Base Class Library cung cấp các bộ sưu tập trong không gian tên System.Collections.Generic, mang lại các phiên bản an toàn kiểu (Type-Safe) và generic của các cấu trúc dữ liệu kinh điển.

using System.Collections.Generic;

List<int> numbers = [1, 2, 3, 4, 5]; // Collection expression (C# 12)
Dictionary<string, int> ages = new() { ["Alice"] = 30, ["Bob"] = 25 };
HashSet<int> unique = [1, 2, 3];

Khái niệm cốt lõi

Mảng (Arrays)

Mảng có kích thước cố định (Fixed-Size), chỉ mục bắt đầu từ 0 (Zero-Indexed), và được lưu trữ trong bộ nhớ liên tục (Contiguous Memory). Chúng là kiểu bộ sưu tập cơ bản nhất trong C#.

// Declaration and initialization
int[] nums = new int[5];           // [0, 0, 0, 0, 0]
int[] primes = [2, 3, 5, 7, 11];  // Collection expression (C# 12)
string[] names = ["Alice", "Bob"];

// Multi-dimensional arrays
int[,] grid = new int[3, 4];           // 3 rows, 4 columns
int[,] matrix = { { 1, 2 }, { 3, 4 } };

// Jagged arrays (array of arrays)
int[][] jagged = new int[3][];
jagged[0] = [1, 2];
jagged[1] = [3, 4, 5];
jagged[2] = [6];

mẹo

Sử dụng mảng khi kích thước được biết tại thời điểm tạo và không thay đổi. Chúng cung cấp hiệu suất tốt nhất nhờ vào cách bố trí bộ nhớ liên tục.

List<T>

Một mảng động (Dynamic Array) tự động thay đổi kích thước. Đây là bộ sưu tập được sử dụng phổ biến nhất trong C#.

List<int> list = [3, 1, 4, 1, 5];

list.Add(9);                    // Append to end
list.AddRange([2, 6, 5]);      // Add multiple
list.Insert(0, 99);             // Insert at index
list.Remove(1);                 // Remove first occurrence of 1
list.RemoveAt(0);               // Remove by index
list.Sort();                    // Sort in place

bool has = list.Contains(4);            // O(n) search
int? found = list.Find(x => x > 3);     // First match
List<int> all = list.FindAll(x => x > 2); // All matches

int count = list.Count;     // Actual number of elements
int cap = list.Capacity;    // Allocated internal array size

cảnh báo

Count trả về số lượng phần tử. Capacity trả về kích thước của mảng nội bộ. Capacity >= Count luôn đúng.

Dictionary<TKey, TValue>

Lưu trữ cặp khóa-giá trị (Key-Value Pairs) với độ phức tạp tìm kiếm trung bình O(1) theo khóa. Khóa phải là duy nhất.

var scores = new Dictionary<string, int>
{
    ["Alice"] = 95,
    ["Bob"] = 87
};

// Add and retrieve
scores["Charlie"] = 72;
int aliceScore = scores["Alice"];        // 95 (throws if key missing)

// Safe retrieval
if (scores.TryGetValue("Bob", out int bobScore))
{
    Console.WriteLine(bobScore); // 87
}

// Check existence
bool hasKey = scores.ContainsKey("Alice");
bool hasVal = scores.ContainsValue(87); // O(n)

// Iteration
foreach (KeyValuePair<string, int> kvp in scores)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}

HashSet<T>

Lưu trữ các phần tử duy nhất (Unique Elements) với độ phức tạp tìm kiếm trung bình O(1). Hỗ trợ các phép toán tập hợp (Set Operations).

HashSet<int> setA = [1, 2, 3, 4, 5];
HashSet<int> setB = [4, 5, 6, 7, 8];

setA.Add(6);                         // Add (ignored if exists)
setA.UnionWith(setB);                // A = A U B
setA.IntersectWith(setB);            // A = A ^ B
setA.ExceptWith(setB);               // A = A - B
bool subset = setA.IsSubsetOf(setB); // Is A a subset of B?
bool overlap = setA.Overlaps(setB);  // Any common elements?

Queue<T>

Cấu trúc dữ liệu FIFO (Vào trước - Ra trước / First-In, First-Out).

var queue = new Queue<string>();

queue.Enqueue("first");   // Add to back
queue.Enqueue("second");

string front = queue.Peek();          // View front without removing: "first"
string dequeued = queue.Dequeue();    // Remove and return front: "first"

// Safe dequeue
if (queue.TryDequeue(out string? item))
{
    Console.WriteLine(item); // "second"
}

Stack<T>

Cấu trúc dữ liệu LIFO (Vào sau - Ra trước / Last-In, First-Out).

var stack = new Stack<int>();

stack.Push(1);   // Add to top
stack.Push(2);
stack.Push(3);

int top = stack.Peek();       // View top without removing: 3
int popped = stack.Pop();     // Remove and return top: 3

// Safe pop
if (stack.TryPop(out int item))
{
    Console.WriteLine(item); // 2
}

Bộ sưu tập Non-Generic (Cũ)

Không gian tên System.Collections cung cấp các bộ sưu tập non-generic lưu trữ phần tử dưới dạng object. Ưu tiên sử dụng các phiên bản generic trong System.Collections.Generic để đảm bảo an toàn kiểu và tránh chi phí boxing/unboxing.

Queue và Stack (Non-Generic)

using System.Collections; // non-generic namespace

// Non-generic Queue — stores object, requires casting
Queue queue = new Queue();
queue.Enqueue(42);
int val = (int)queue.Dequeue(); // explicit cast needed

// Non-generic Stack — stores object, requires casting
Stack stack = new Stack();
stack.Push(99);
int top = (int)stack.Pop(); // explicit cast needed

cảnh báo

Luôn ưu tiên Queue<T> và Stack<T> hơn các phiên bản non-generic tương ứng. Các phiên bản non-generic lưu trữ object, gây ra boxing cho các kiểu giá trị và yêu cầu ép kiểu tại thời điểm chạy có thể thất bại.

Hashtable

Một bộ sưu tập khóa-giá trị non-generic dựa trên mã băm (Hash Code) của khóa. Không có tương đương generic trong không gian tên này — sử dụng Dictionary<TKey, TValue> thay thế.

using System.Collections;

Hashtable hashTable = new Hashtable();
hashTable.Add("key1", 174);
hashTable.Remove("key1");
bool hasKey = hashTable.ContainsKey("key1");
bool hasVal = hashTable.ContainsValue(174);

ICollection keys = hashTable.Keys;
ICollection values = hashTable.Values;

Tính năng	Hashtable	Dictionary<TKey, TValue>
Không gian tên	System.Collections	System.Collections.Generic
An toàn kiểu	Không (lưu trữ object)	Kiểm tra đầy đủ tại thời điểm biên dịch
Boxing	Có, cho kiểu giá trị	Không
Khóa null	Cho phép một khóa null duy nhất	Ném ArgumentNullException
Thay thế hiện đại	Sử dụng Dictionary<TKey, TValue>	Được khuyến nghị

LinkedList<T>

Một danh sách liên kết đôi (Doubly-Linked List) mà mỗi nút giữ tham chiếu đến nút trước và nút tiếp theo. Chèn và xóa hiệu quả tại các vị trí đã biết.

var linked = new LinkedList<string>();

LinkedListNode<string> node1 = linked.AddFirst("A");
LinkedListNode<string> node2 = linked.AddLast("B");
linked.AddBefore(node2, "AB");
linked.AddAfter(node1, "A2");

linked.Remove("AB");              // Remove by value
linked.Remove(linked.First);      // Remove node reference

LinkedListNode<string>? found = linked.Find("A2"); // Find first occurrence

ReadOnlyCollection<T> và ImmutableList<T>

using System.Collections.ObjectModel;
using System.Collections.Immutable;

// ReadOnlyCollection — wrapper, prevents modification via the wrapper
List<int> source = [1, 2, 3];
ReadOnlyCollection<int> readOnly = source.AsReadOnly();

// ImmutableList — truly immutable, creates new instances on "modification"
ImmutableList<int> imm = ImmutableList.Create(1, 2, 3);
ImmutableList<int> added = imm.Add(4); // new list, imm unchanged

Ví dụ mã

Biểu thức bộ sưu tập (Collection Expressions - C# 12)

// Inline initialization
int[] arr = [1, 2, 3];
List<string> names = ["Alice", "Bob"];
Span<int> span = [10, 20, 30];

// Spread operator
int[] a = [1, 2];
int[] b = [3, 4];
int[] combined = [..a, ..b]; // [1, 2, 3, 4]

Duyệt và chỉnh sửa an toàn

// WRONG: modifying during foreach throws InvalidOperationException
// foreach (var item in list) { list.Remove(item); } // EXCEPTION

// Option 1: iterate backward
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] < 0) list.RemoveAt(i);
}

// Option 2: use RemoveAll
list.RemoveAll(x => x < 0);

// Option 3: create a new filtered list
List<int> filtered = list.Where(x => x >= 0).ToList();

Khi nào sử dụng — Ma trận quyết định

Nhu cầu	Sử dụng	Tìm kiếm	Chèn/Xóa
Dữ liệu kích thước cố định, truy cập theo chỉ mục	T[] (mảng)	O(1)	N/A
Danh sách động, thêm/xóa thường xuyên ở cuối	List<T>	O(1) chỉ mục / O(n) tìm kiếm	O(1) thêm cuối / O(n) ở giữa
Tìm kiếm khóa-giá trị	Dictionary<TKey, TValue>	O(1) theo khóa	O(1) phân tách
Phần tử duy nhất, phép toán tập hợp	HashSet<T>	O(1)	O(1) phân tách
Xử lý FIFO (hàng đợi tác vụ)	Queue<T>	O(1) đầu/cuối	O(1) enqueue/dequeue
Xử lý LIFO (undo/redo, phân tích cú pháp)	Stack<T>	O(1) đỉnh	O(1) push/pop
Chèn/xóa thường xuyên ở giữa	LinkedList<T>	O(n)	O(1) tại nút đã biết
API công khai chỉ đọc	ReadOnlyCollection<T>	O(1) chỉ mục	N/A
Bất biến thực sự, chia sẻ an toàn luồng	ImmutableList<T>	O(1) chỉ mục	O(n) trả về mới

Lỗi thường gặp

1. Chỉnh sửa bộ sưu tập trong foreach — Ném InvalidOperationException. Sử dụng vòng lặp for (duyệt ngược), RemoveAll, hoặc LINQ để tạo bộ sưu tập mới.

2. Sử dụng Count vs Any() — list.Count > 0 truy cập thuộc tính Count (nhanh cho List<T> nhưng không cho IEnumerable<T> vì sẽ kích hoạt liệt kê toàn bộ). Ưu tiên list.Any() từ LINQ cho IEnumerable<T> chung.

3. Xung đột khóa Dictionary — Add ném ArgumentException nếu khóa đã tồn tại. Sử dụng bộ chỉ mục dict[key] = value để ghi đè, hoặc TryAdd để thử chèn an toàn.

4. Xóa từ List<T> trong vòng lặp xuôi — Việc xóa dịch chuyển các phần tử còn lại sang trái, gây bỏ sót phần tử tiếp theo. Duyệt ngược hoặc sử dụng RemoveAll.

5. Sử dụng List<T> cho chèn thường xuyên ở giữa — List<T> được hỗ trợ bởi mảng, nên chèn ở giữa có độ phức tạp O(n). Sử dụng LinkedList<T> cho mẫu này.

Điểm chính cần nhớ

• Mảng (Arrays) có kích thước cố định và nhanh nhất cho truy cập theo chỉ mục
• List<T> là lựa chọn mặc định cho bộ sưu tập động
• Dictionary<TKey, TValue> cung cấp tìm kiếm theo khóa O(1)
• HashSet<T> đảm bảo tính duy nhất và hỗ trợ phép toán tập hợp
• Luôn duyệt ngược hoặc sử dụng RemoveAll khi xóa phần tử trong lúc duyệt
• Sử dụng Count cho bộ sưu tập triển khai ICollection<T>, Any() cho IEnumerable<T>
• Biểu thức bộ sưu tập (Collection Expressions) ([...]) cung cấp cú pháp khởi tạo gọn gàng trong C# 12+

Câu hỏi phỏng vấn

H: Sự khác biệt giữa mảng và List<T> là gì? Đ: Mảng có kích thước cố định được xác định tại thời điểm tạo và không thể tăng hay giảm. List<T> là một mảng động tự động thay đổi kích thước mảng nội bộ khi vượt quá sức chứa. Mảng cung cấp hiệu suất tốt hơn một chút cho các tình huống kích thước cố định; List<T> cung cấp sự linh hoạt với Add, Remove, Insert và các phương thức khác.

H: Sự khác biệt giữa Dictionary<TKey, TValue> và HashSet<T> là gì? Đ: Dictionary lưu trữ các cặp khóa-giá trị và truy xuất giá trị theo khóa. HashSet chỉ lưu trữ các khóa duy nhất (không có giá trị). Cả hai đều sử dụng tìm kiếm dựa trên băm (độ phức tạp trung bình O(1)). Sử dụng Dictionary khi cần liên kết dữ liệu với khóa; sử dụng HashSet khi chỉ cần kiểm tra thành viên.

H: Độ phức tạp thời gian của tìm kiếm Dictionary là gì? Đ: Trung bình O(1) cho TryGetValue, ContainsKey và truy cập bộ chỉ mục. Trường hợp xấu nhất O(n) nếu có nhiều va chạm băm (Hash Collisions), nhưng .NET sử dụng thuật toán băm tốt và chiến lược thay đổi kích thước để giữ va chạm ở mức tối thiểu.

H: Làm thế nào để duyệt và chỉnh sửa bộ sưu tập an toàn cùng lúc? Đ: Duyệt ngược bằng vòng lặp for (để dịch chuyển chỉ mục không gây bỏ sót), sử dụng RemoveAll để xóa có điều kiện, hoặc xây dựng bộ sưu tập đã lọc mới bằng LINQ. Không bao giờ chỉnh sửa bộ sưu tập trong vòng lặp foreach.

Tài liệu tham khảo

• Tour of C# — Collections
• C# Programming Guide — Collections
• W3Schools C# Collections
• Programiz C# Collections