C# Day 5: Collections

Sau Generics, ngày 5 tập trung vào Collections trong C#.

Mục tiêu không chỉ là nhớ syntax, mà phải biết chọn đúng collection theo use case.

Các type chính:

T[]
List<T>
Dictionary<TKey, TValue>
HashSet<T>
Queue<T>
Stack<T>
IEnumerable<T>
ICollection<T>
IList<T>
IReadOnlyCollection<T>
IReadOnlyList<T>

Mental model:

Array
→ fixed size

List<T>
→ ordered dynamic sequence

Dictionary<TKey, TValue>
→ lookup theo key

HashSet<T>
→ unique values

Queue<T>
→ FIFO

Stack<T>
→ LIFO

IEnumerable<T>
→ có thể enumerate bằng foreach

---

1. Array

Array có kích thước cố định.

int[] numbers = new int[3];

numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;

Hoặc:

int[] numbers = { 10, 20, 30 };

Truy cập theo index:

Console.WriteLine(numbers[1]);

Mental model:

Array
→ fixed-size sequence
→ index access

Dùng array khi:

• size cố định hoặc đã biết rõ
• cần cấu trúc đơn giản
• API yêu cầu array
• không cần Add/Remove linh hoạt

---

2. List<T>

List<T> là collection có thứ tự và kích thước động.

var users = new List<string>();

users.Add("David");
users.Add("Vu");

Truy cập:

Console.WriteLine(users[0]);

Remove:

users.Remove("David");

Mental model:

List<T>
→ dynamic array-like collection
→ ordered
→ index-based

Count vs Capacity

Count
→ số item hiện có

Capacity
→ sức chứa của internal storage hiện tại

Khi vượt capacity, List<T> có thể cần cấp storage lớn hơn và copy dữ liệu.

Dynamic size không có nghĩa resize hoàn toàn miễn phí.

---

3. Lookup trong List<T>

Ví dụ:

var user = users.FirstOrDefault(
    x => x.Id == userId
);

Về bản chất thường phải scan các phần tử.

List search
→ thường O(n)

Nếu use case chính là lookup theo Id, Dictionary có thể phù hợp hơn.

---

4. Dictionary<TKey, TValue>

Dictionary lưu dữ liệu theo:

key → value

Ví dụ:

var usersById =
    new Dictionary<Guid, User>();

Thêm:

usersById.Add(user.Id, user);

Hoặc:

usersById[user.Id] = user;

Lookup:

User user = usersById[userId];

Mental model:

Dictionary<TKey, TValue>
→ lookup table theo key

Average lookup thường gần:

O(1)

TryGetValue

Thường nên dùng:

if (usersById.TryGetValue(
    userId,
    out var user))
{
    Console.WriteLine(user.Name);
}

Mental model:

TryGetValue
→ lookup + kiểm tra tồn tại

Duplicate key

usersById.Add(id, user1);
usersById.Add(id, user2);

lần thứ hai sẽ lỗi vì key đã tồn tại.

Nhưng:

usersById[id] = user2;

sẽ thay value của key đó.

---

5. HashSet<T>

HashSet<T> tập trung vào unique values.

var roles = new HashSet<string>();

roles.Add("Admin");
roles.Add("Merchant");
roles.Add("Admin");

Set chỉ chứa một "Admin".

Mental model:

HashSet<T>
→ set
→ không duplicate theo equality semantics

Ví dụ kiểm tra đã xử lý ID chưa:

var processedIds =
    new HashSet<Guid>();

if (!processedIds.Add(id))
{
    Console.WriteLine("Already processed");
}

Add trả:

true
→ item mới

false
→ item đã tồn tại

Use cases:

• deduplication
• membership check
• processed IDs
• permissions
• tags unique

---

6. Dictionary vs HashSet

Dictionary<TKey, TValue>
→ key + value

HashSet<T>
→ unique value

Ví dụ:

Dictionary<Guid, User>

khi cần:

userId → User

Còn:

HashSet<Guid>

khi chỉ cần:

ID này đã tồn tại chưa?

---

7. Queue<T>

Queue hoạt động theo:

FIFO
First In, First Out

Ví dụ:

var queue = new Queue<string>();

queue.Enqueue("A");
queue.Enqueue("B");
queue.Enqueue("C");

var item = queue.Dequeue();

item là:

A

Use cases:

• job processing
• request processing
• BFS
• workflow theo thứ tự đến

Lưu ý:

Queue<T> trong memory
≠
message broker

RabbitMQ, Azure Service Bus, Kafka là bài toán khác.

---

8. Stack<T>

Stack hoạt động theo:

LIFO
Last In, First Out

Ví dụ:

var stack = new Stack<string>();

stack.Push("A");
stack.Push("B");
stack.Push("C");

var item = stack.Pop();

item là:

C

Use cases:

• undo
• backtracking
• DFS
• navigation history
• expression parsing

---

9. Peek

Queue và Stack đều có Peek().

queue.Peek();
stack.Peek();

Mental model:

Peek
→ xem item tiếp theo

Dequeue / Pop
→ lấy và remove

---

10. IEnumerable<T>

IEnumerable<T> đại diện cho một sequence có thể được enumerate.

IEnumerable<User> users;

Có thể:

foreach (var user in users)
{
    Console.WriteLine(user.Name);
}

Mental model:

IEnumerable<T>
→ "Tôi có thể enumerate các T"

Nó không đảm bảo rằng:

• có Add
• có Remove
• có index
• Count là O(1)
• dữ liệu đã nằm trong memory
• query đã execute

List<T> implement IEnumerable<T>, nhưng IEnumerable<T> không có nghĩa là List<T>.

---

11. ICollection<T>

ICollection<T> thêm các collection operation:

Count
Add
Remove
Contains
Clear

Mental model:

IEnumerable<T>
→ enumerate

ICollection<T>
→ enumerate + collection operations

---

12. IList<T>

IList<T> thêm list semantics và index access.

IList<User> users;

Có thể:

var first = users[0];

Mental model:

IList<T>
→ ICollection<T>
+ positional/index access

Simplified hierarchy:

IEnumerable<T>
      ↑
ICollection<T>
      ↑
IList<T>

---

13. Read-only Collection Interfaces

Nếu caller chỉ cần enumerate và Count:

IReadOnlyCollection<User>

Nếu caller cần thêm index access:

IReadOnlyList<User>

Ví dụ:

private readonly List<User> _users = new();

public IReadOnlyList<User> Users
    => _users;

Mental model:

IReadOnlyList<T>
→ read-only collection API surface

Nhưng:

read-only collection
≠
deep immutable objects

Nếu User.Name có setter:

Users[0].Name = "Changed";

vẫn có thể hợp lệ.

---

14. Equality và Hashing

Dictionary<TKey, TValue> và HashSet<T> phụ thuộc vào equality/hash semantics.

Conceptual flow:

key/value
↓
GetHashCode()
↓
candidate bucket
↓
Equals()
↓
same / different

Rule quan trọng:

Nếu a.Equals(b) == true
→ a và b phải có cùng hash code

Nhưng:

same hash
≠
chắc chắn Equals == true

Hai object khác nhau có thể bị hash collision.

---

15. Mutable Dictionary Key có thể gây Bug

Ví dụ:

public class UserKey
{
    public string Email { get; set; }
}

Giả sử equality/hash phụ thuộc vào Email.

var key = new UserKey
{
    Email = "a@test.com"
};

dictionary[key] = user;

Sau đó:

key.Email = "b@test.com";

Hash/equality có thể thay đổi trong khi dictionary đã lưu key dựa trên trạng thái cũ.

Kết quả:

object vẫn ở dictionary
nhưng lookup có thể thất bại

Rule:

Key của hash-based collection nên có equality/hash ổn định trong thời gian tồn tại trong collection.

---

16. String Comparer

Ví dụ:

var emails =
    new HashSet<string>(
        StringComparer.OrdinalIgnoreCase
    );

emails.Add("test@example.com");
emails.Add("TEST@example.com");

Hai chuỗi được xem là cùng value theo comparer đó.

Tương tự với Dictionary:

var users =
    new Dictionary<string, User>(
        StringComparer.OrdinalIgnoreCase
    );

---

17. Big-O Mental Model

Big-O mô tả chi phí operation tăng như thế nào khi dữ liệu tăng.

O(1)
→ gần constant-time

O(n)
→ tăng tuyến tính theo số item

Bảng mental model:

Đây là mental model để reasoning, không phải benchmark tuyệt đối.

---

18. List vs Dictionary

Ví dụ:

List<User> users;

Lookup:

users.FirstOrDefault(
    x => x.Id == userId
);

thường:

O(n)

Nếu:

Dictionary<Guid, User> usersById;

lookup:

usersById.TryGetValue(
    userId,
    out var user
);

average gần:

O(1)

Nhưng Dictionary có trade-off:

• dùng thêm memory
• cần key
• key phải có equality/hash phù hợp
• không phải use case nào cũng cần lookup table

---

19. Đừng Optimize Quá Sớm

Nếu collection có 5 phần tử và lookup một lần, dùng Dictionary chỉ vì O(1) chưa chắc tốt hơn về design.

Hãy cân nhắc:

• số lượng dữ liệu
• frequency của operation
• readability
• correctness
• memory
• profile thực tế

Big-O là công cụ reasoning, không phải lý do duy nhất.

---

20. Production Use Cases

UI list

List<UserDto>

Repeated lookup theo ID

Dictionary<Guid, User>

Unique event IDs

HashSet<Guid>

FIFO jobs

Queue<Job>

Undo history

Stack<Command>

---

21. API Design — Expose Capability Tối Thiểu

Không phải lúc nào cũng nên expose:

public List<User> Users { get; }

Caller có thể:

service.Users.Clear();

Nếu không muốn caller mutate:

public IReadOnlyList<User> Users
    => _users;

Mental model:

Expose capability tối thiểu mà caller cần

Nếu method chỉ cần enumerate:

public void PrintUsers(
    IEnumerable<User> users)
{
    foreach (var user in users)
    {
        Console.WriteLine(user.Name);
    }
}

Không nhất thiết phải yêu cầu List<User>.

---

22. Common Mistake — Dùng List cho Lookup Lặp Lại

Ví dụ:

foreach (var order in orders)
{
    var user = users.FirstOrDefault(
        x => x.Id == order.UserId
    );
}

Nếu orders và users đều lớn, đây là repeated scan.

Có thể build lookup:

var usersById =
    users.ToDictionary(
        x => x.Id
    );

Sau đó:

foreach (var order in orders)
{
    if (usersById.TryGetValue(
        order.UserId,
        out var user))
    {
        // use user
    }
}

Mental model:

Build lookup once
→ repeated O(1)-average key lookup

---

23. Common Mistake — Modify khi đang foreach

Ví dụ:

foreach (var user in users)
{
    users.Remove(user);
}

Nhiều collection sẽ throw:

InvalidOperationException

vì collection bị thay đổi trong lúc enumerator đang hoạt động.

Thường nên:

• collect item cần remove rồi remove sau
• iterate bằng index theo cách phù hợp
• tạo collection mới
• dùng API phù hợp

---

24. Common Mistake — Nghĩ IEnumerable<T> luôn nằm trong Memory

Không đúng.

IEnumerable<T> chỉ nói rằng sequence có thể được enumerate.

Nguồn có thể là:

• List<T>
• array
• iterator
• lazy sequence
• query result

Deferred execution sẽ học kỹ hơn khi tới LINQ.

---

25. Common Mistake — Gọi Count() mà không hiểu Source

Với:

IEnumerable<T>

Count() có thể phải enumerate source tùy implementation.

Trong khi:

ICollection<T>.Count

là property của collection.

Không nên mặc định mọi IEnumerable<T> đều có cheap count.

---

26. Collection Expression trong C# hiện đại

Ví dụ:

int[] numbers = [1, 2, 3];

Hoặc:

List<string> names =
[
    "David",
    "Vu"
];

Đây là syntax convenience.

Nó không thay đổi bản chất của data structure.

---

27. Thread Safety

Các collection thông thường như:

List<T>
Dictionary<TKey, TValue>
HashSet<T>

không nên mặc định coi là thread-safe khi nhiều thread cùng mutate.

.NET có các type như:

ConcurrentDictionary<TKey, TValue>
ConcurrentQueue<T>

nhưng phần này để học trong Concurrency.

Mental note:

normal collection
≠
automatic thread safety

---

Bảng Chọn Collection Nhanh

---

Mental Model Ngày 5

Array
→ fixed size

List<T>
→ ordered dynamic sequence

Dictionary<TKey, TValue>
→ key → value lookup

HashSet<T>
→ unique set

Queue<T>
→ FIFO

Stack<T>
→ LIFO

IEnumerable<T>
→ enumerate capability

ICollection<T>
→ collection operations

IList<T>
→ index/list capability

IReadOnlyList<T>
→ expose read-only list API

Equality:

Dictionary / HashSet
→ hashing + equality

Performance:

List search
→ usually O(n)

Dictionary lookup
→ average O(1)

HashSet Contains
→ average O(1)

---

Câu Hỏi Ôn Tập

1. Khi nào dùng Array thay vì List<T>?

Khi size cố định hoặc đã biết rõ và không cần add/remove linh hoạt.

2. List<T> có giữ thứ tự không?

Có.

3. Search trong List thường có complexity gì?

Thường O(n).

4. Dictionary dùng để làm gì?

Mapping unique key tới value để lookup theo key hiệu quả.

5. TryGetValue dùng để làm gì?

Vừa kiểm tra key tồn tại vừa lấy value.

6. HashSet<T> giải quyết bài toán gì?

Unique values và membership check.

7. Queue hoạt động theo nguyên tắc gì?

FIFO
First In, First Out

8. Stack hoạt động theo nguyên tắc gì?

LIFO
Last In, First Out

9. IEnumerable<T> có đảm bảo index không?

Không.

10. IEnumerable<T> có đảm bảo Add() không?

Không.

11. ICollection<T> thêm gì?

Các collection operation như Count, Add, Remove, Contains.

12. IList<T> thêm gì?

Index access và list semantics.

13. IReadOnlyList<T> có làm object bên trong immutable không?

Không.

14. Vì sao Dictionary cần GetHashCode() và Equals()?

Hash giúp tìm candidate bucket, equality xác định key thực sự có bằng nhau hay không.

15. Hai object cùng hash có chắc bằng nhau không?

Không. Có thể là hash collision.

16. Nếu Equals() là true thì hash code phải thế nào?

Phải giống nhau.

17. Vì sao mutable key nguy hiểm?

Mutation có thể thay đổi hash/equality sau khi key đã được insert.

18. HashSet.Contains() và List.Contains() khác gì về performance mental model?

HashSet
→ average O(1)

List
→ usually O(n)

19. Có nên luôn dùng Dictionary vì O(1) không?

Không. Phải cân nhắc use case, memory, readability và frequency lookup.

20. Vì sao method đôi khi nên nhận IEnumerable<T> thay vì List<T>?

Nếu method chỉ cần enumerate, yêu cầu List<T> sẽ bắt caller cung cấp nhiều capability hơn mức thực sự cần.

---

Bài Tập Ngày 5

Bài 1 — List

Tạo:

List<User>

và:

• add 5 users
• remove 1 user
• tìm user theo Id
• access theo index

Bài 2 — Dictionary

Từ:

List<User>

tạo:

Dictionary<Guid, User>

với User.Id làm key.

Lookup bằng:

TryGetValue

Bài 3 — HashSet

Cho dữ liệu:

1, 2, 2, 3, 3, 3, 4

dùng:

HashSet<int>

để còn:

1, 2, 3, 4

Sau đó giải thích vì sao duplicate bị loại.

Bài 4 — Queue

Process:

Job A
Job B
Job C

theo đúng FIFO.

Bài 5 — Stack

Dùng:

/home
/products
/products/1

để mô phỏng nút Back bằng Stack<string>.

Bài 6 — Equality Bug

Tạo custom dictionary key có mutable property.

Override:

Equals()
GetHashCode()

dựa trên property đó.

Insert vào Dictionary, sau đó mutate property và thử lookup lại.

Mục tiêu:

Hiểu vì sao hash-based key cần stable equality/hash

---

Production Exercise

Giả sử:

List<User> users;
List<Order> orders;

Mỗi order có:

Guid UserId;

Ban đầu:

foreach (var order in orders)
{
    var user = users.FirstOrDefault(
        x => x.Id == order.UserId
    );

    if (user is null)
    {
        continue;
    }

    Console.WriteLine(
        $"{order.Id} - {user.Name}"
    );
}

Refactor bằng:

Dictionary<Guid, User>

Sau đó tự giải thích trade-off:

+ repeated lookup nhanh hơn
+ intent "lookup by ID" rõ hơn

- thêm memory
- cần build dictionary
- key phải unique và stable

---

Key Takeaways

Không có collection tốt nhất.

Có collection phù hợp hơn với use case.

Nhớ:

Sequence
→ List<T>

Key lookup
→ Dictionary<TKey,TValue>

Uniqueness / membership
→ HashSet<T>

FIFO
→ Queue<T>

LIFO
→ Stack<T>

Enumeration abstraction
→ IEnumerable<T>

Và quan trọng nhất:

Data structure
→ ảnh hưởng trực tiếp tới
algorithm
performance
API design
correctness

Ngày tiếp theo:

Day 6
→ Delegates
→ Func
→ Action
→ Lambda
→ Events

Sau đó:

Day 7
→ LINQ