Cấu Trúc Dữ Liệu Mà Mọi Lập Trình Viên ASP.NET Nên Biết

Đứng trước một API chậm, phản xạ của nhiều người là đổi List<T> thành Dictionary. Thực tế, phần lớn thời gian bị mất ở chỗ khác: một vòng lặp gọi database 200 lần, một payload 4 MB, hoặc một chuỗi được cộng dồn trong vòng lặp. Cấu trúc dữ liệu vẫn quan trọng, nhưng theo nghĩa khác — chọn đúng để không tạo ra vấn đề, chứ không phải để cứu một kiến trúc đang sai.

Bài này là những gì bạn thực sự dùng khi viết ASP.NET Core: chi phí thật của từng collection trong BCL, khi nào cần Span<T>, khi nào FrozenDictionary, và cách đo thay vì đoán.

Cập nhật 2026

  • FrozenDictionary và FrozenSet (namespace System.Collections.Frozen) đã ổn định từ .NET 8: tối ưu cho đọc, trả giá ở khâu tạo. Đây là lựa chọn đúng cho bảng tra cứu dựng một lần.
  • Dictionary<TKey,TValue>.GetAlternateLookup<TAlternate>() từ .NET 9 cho phép tra cứu bằng ReadOnlySpan<char> mà không cấp phát string.
  • PriorityQueue<TElement,TPriority> có từ .NET 6 nhưng vẫn ít được dùng; nó không đảm bảo thứ tự FIFO cho các phần tử cùng priority.
  • Collection expression ([a, b, ..rest]) và CollectionsMarshal.AsSpan giúp giảm cấp phát mà không phải viết lại vòng lặp.

Big-O mà không cần thuật toán phỏng vấn

Big-O nói về tốc độ tăng, không nói về tốc độ tuyệt đối. Ba điều thực dụng hơn ký hiệu:

  • Hằng số và cache locality thắng trong tập nhỏ. Duyệt 8 phần tử trong một mảng liền kề thường nhanh hơn 8 lần băm. Với n < ~10, vòng lặp tuyến tính là lựa chọn hợp lý, không phải tối ưu non.
  • Cấp phát là chi phí ẩn. Mỗi lần ToList(), Select().ToArray() hay cộng chuỗi tạo object mới trên heap. Trong ASP.NET Core, Gen0 GC rẻ nhưng không miễn phí; ở mức vài chục nghìn request/giây, số allocation quyết định throughput nhiều hơn một hằng số Big-O.
  • Amortized không phải mọi lần. List.Add là O(1) trung bình, nhưng lần mở rộng là O(n). Nếu biết trước số phần tử, truyền capacity để tránh 3–4 lần copy.

Đo bằng BenchmarkDotNet 0.15.8 với [MemoryDiagnoser], chạy Release, trên dữ liệu giống production. Đoán cấu trúc dữ liệu mà không đo là cách phổ biến nhất để tối ưu nhầm chỗ.

Bảng chọn nhanh

Cấu trúc Chi phí điển hình Dùng khi
T[], Span<T> Truy cập O(1), không cấp phát Kích thước cố định, xử lý buffer, parsing
List<T> Truy cập O(1), add cuối O(1) amortized, xóa giữa O(n) Tập có thứ tự, thêm ở cuối, duyệt toàn bộ
Dictionary<TKey,TValue> O(1) trung bình Tra cứu theo khóa, cập nhật thường xuyên
HashSet<T> O(1) trung bình Kiểm tra tồn tại, khử trùng lặp
FrozenDictionary Đọc nhanh hơn Dictionary, tạo đắt Bảng tra cứu chỉ đọc, dựng một lần
SortedDictionary O(log n) mọi thao tác Cần duyệt theo thứ tự khóa, dữ liệu nhỏ
Queue, Stack O(1) hai đầu FIFO/LIFO, buffer, undo
PriorityQueue Enqueue/Dequeue O(log n) Lịch chạy theo độ ưu tiên

Nếu bảng này chỉ nhớ được một dòng: mặc định là List<T> cho tập có thứ tự, Dictionary khi tra theo khóa, HashSet khi chỉ hỏi “có hay không”. Mọi thứ khác là tối ưu có điều kiện.

Array, Span và Memory

Span<T> là view trên bộ nhớ liên tục — có thể là array, stack, hoặc native memory — không cấp phát, có slicing O(1). Nó là ref struct, nghĩa là chỉ sống trên stack: không capture trong lambda, không dùng trong async, không làm field của class.

// File: Parsing/OrderCodeParser.cs
public static bool TryParseOrderCode(ReadOnlySpan<char> input, out int orderId)
{
    orderId = 0;
    if (!input.StartsWith("ORD-", StringComparison.Ordinal))
        return false;

    // Không cấp phát string trung gian
    return int.TryParse(input[4..], out orderId);
}

// Gọi từ một string có sẵn
if (TryParseOrderCode("ORD-1042".AsSpan(), out var id)) { /* ... */ }

Khi cần giữ dữ liệu qua await, dùng Memory<T>/ReadOnlyMemory<T> rồi lấy span bên trong method đồng bộ. Với buffer lớn và ngắn hạn, ArrayPool<byte>.Shared tránh áp lực lên Large Object Heap (ngưỡng 85 KB), nhưng phải trả lại trong finally — quên Return là rò rỉ từ từ.

CollectionsMarshal.AsSpan(list) cho phép duyệt List<T> như mảng, bỏ bounds check từng phần tử. Chỉ dùng khi không thêm/xóa trong lúc duyệt; API này là advanced và không bảo vệ bạn khỏi thay đổi cấu trúc.

Dictionary, HashSet và các biến thể

Dictionary<TKey,TValue> là bảng băm: tra cứu trung bình O(1), nhưng phụ thuộc vào GetHashCode và Equals của khóa. Với string, comparer mặc định là ordinal — đúng cho path, header, ID. Nếu cần so sánh không phân biệt hoa thường, truyền StringComparer.OrdinalIgnoreCase ngay từ constructor; đổi comparer sau khi đã có dữ liệu là lỗi.

// Đúng: comparer cố định từ đầu
var headers = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);

// Sai: khóa là object mutable, hash đổi sau khi insert
// Dictionary<OrderKey, int> với OrderKey có setter trên field tham gia hash

Ba biến thể dễ chọn sai:

  • SortedDictionary dùng cây đỏ-đen: O(log n) cho mọi thao tác, duyệt theo thứ tự khóa. Nếu bạn chỉ cần sắp xếp một lần khi trả kết quả, sort cuối bằng OrderBy rẻ hơn.
  • SortedList lưu trong mảng nên tra cứu O(log n) nhưng chèn O(n). Tốt cho tập rất nhỏ, dựng một lần.
  • ConcurrentDictionary an toàn khi nhiều thread đọc/ghi. Nhưng GetOrAdd(key, factory) có thể chạy factory nhiều lần cho cùng key; nếu factory đắt hoặc có side effect, bọc bằng Lazy<T> hoặc dùng overload nhận tham số.
// Factory có thể chạy hơn một lần -> dùng Lazy để đảm bảo một lần
private readonly ConcurrentDictionary<int, Lazy<Customer>> _cache = new();

public Customer Get(int id) =>
    _cache.GetOrAdd(id, k => new Lazy<Customer>(
        () => LoadFromDb(k), LazyThreadSafetyMode.ExecutionAndPublication)).Value;

Còn GetAlternateLookup giải quyết một trường hợp rất cụ thể: bạn có Dictionary<string, T> và chỉ có ReadOnlySpan<char> từ parser. Trước .NET 9, bạn phải span.ToString() — một allocation cho mỗi lần tra. Bây giờ:

var lookup = dict.GetAlternateLookup<ReadOnlySpan<char>>();
if (lookup.TryGetValue(headerName.AsSpan(), out var value)) { /* ... */ }

Chỉ đọc, chia sẻ: FrozenDictionary và ImmutableArray

FrozenDictionary hy sinh thời gian và bộ nhớ lúc tạo để có đường đọc nhanh nhất có thể — hash code được tính sẵn, layout tối ưu cho probe. Với bảng vài nghìn phần tử đọc hàng triệu lần, đây là lựa chọn rõ ràng. Với bảng 20 phần tử, khác biệt không đáng công.

Điều quan trọng: không dựng lại FrozenDictionary mỗi request. Nó là dữ liệu cấu hình, không phải cache động. Nếu dữ liệu thay đổi, dựng một snapshot mới và đổi tham chiếu một lần.

ImmutableArray<T> là struct bọc một mảng; copy là copy tham chiếu, nên chia sẻ snapshot rất rẻ. Kết hợp cả hai cho ra mẫu “read-mostly”: một object bất biến chứa toàn bộ trạng thái, được thay nguyên khối.

// File: Catalog/CatalogSnapshot.cs
public sealed class CatalogSnapshot
{
    public required FrozenDictionary<int, ProductDto> ById { get; init; }
    public required FrozenDictionary<string, int[]> IdsByCategory { get; init; }
    public required ImmutableArray<ProductDto> Featured { get; init; }
}

// File: Catalog/CatalogCache.cs
public sealed class CatalogCache(AppDb db)
{
    private volatile CatalogSnapshot _snapshot = Empty();

    public CatalogSnapshot Current => _snapshot;

    public async Task RebuildAsync(CancellationToken ct)
    {
        var products = await db.Products.AsNoTracking()
            .Select(p => new ProductDto(p.Id, p.Name, p.CategorySlug, p.Price, p.IsFeatured))
            .ToListAsync(ct);

        var next = new CatalogSnapshot
        {
            ById = products.ToFrozenDictionary(p => p.Id),
            IdsByCategory = products
                .GroupBy(p => p.CategorySlug)
                .ToFrozenDictionary(g => g.Key, g => g.Select(p => p.Id).ToArray()),
            Featured = [.. products.Where(p => p.IsFeatured)]
        };

        _snapshot = next;   // một phép gán tham chiếu, reader thấy snapshot nhất quán
    }

    private static CatalogSnapshot Empty() => new()
    {
        ById = FrozenDictionary<int, ProductDto>.Empty,
        IdsByCategory = FrozenDictionary<string, int[]>.Empty,
        Featured = []
    };
}

Điểm thiết kế đáng chú ý: ba field riêng lẻ sẽ cho phép reader thấy trạng thái nửa cũ nửa mới. Một object snapshot bất biến loại bỏ hoàn toàn khả năng đó, và không cần lock ở đường đọc.

Đừng nhầm ImmutableArray với “miễn phí”. Mỗi lần sửa tạo mảng mới; nó dành cho dữ liệu đọc nhiều, ghi rất ít. Với dữ liệu ghi thường xuyên, ConcurrentDictionary hoặc lock là lựa chọn đúng.

Queue, Stack và hàng đợi có backpressure

var queue = new Queue<OrderEvent>();
queue.Enqueue(new OrderEvent(1));

// PriorityQueue: phần tử priority thấp ra trước
var jobs = new PriorityQueue<string, int>();
jobs.Enqueue("reindex", priority: 5);
jobs.Enqueue("send-receipt", priority: 1);
while (jobs.TryDequeue(out var job, out _)) Console.WriteLine(job);

Queue<T> không giới hạn là một rủi ro vận hành: producer nhanh hơn consumer thì bộ nhớ tăng đến khi OOM. Trong ASP.NET Core, dùng Channel<T> (System.Threading.Channels) với BoundedChannelOptions và FullMode = BoundedChannelFullMode.Wait để có backpressure thật, thay vì BlockingCollection chặn thread.

String: nơi allocation tập trung nhiều nhất

Cộng chuỗi trong vòng lặp tạo một string mới mỗi lần, chi phí O(n²) và rác GC. StringBuilder với capacity ước lượng là cách sửa rẻ nhất:

// Sai
var sb = "";
foreach (var tag in tags) sb += tag + ",";

// Đúng
var sb = new StringBuilder(capacity: tags.Count * 8);
foreach (var tag in tags) sb.Append(tag).Append(',');
var result = sb.ToString();

Với format chuỗi có culture cố định, string.Create nhận IFormatProvider tránh allocation trung gian và tránh phụ thuộc culture hiện tại:

var price = string.Create(CultureInfo.InvariantCulture, $"{amount:C2}");

Khi cần tìm một trong nhiều ký tự, SearchValues<char> (.NET 8) cho phép JIT tối ưu IndexOfAny trên span:

private static readonly SearchValues<char> Separators = SearchValues.Create(",;\t");

var index = text.AsSpan().IndexOfAny(Separators);

Ví dụ thật: tra cứu trong request path

Một middleware phân giải tenant theo host thường bị viết như sau: mỗi request duyệt một List<Tenant> 300 phần tử, so sánh chuỗi, rồi parse lại cấu hình. Với 2.000 request/giây, đó là 600.000 phép so sánh chuỗi mỗi giây cho một việc có thể làm bằng một lần băm.

// File: Tenancy/TenantResolver.cs
public sealed class TenantResolver
{
    private readonly FrozenDictionary<string, Tenant> _exact;
    private readonly ImmutableArray<Tenant> _wildcards;

    public TenantResolver(IEnumerable<Tenant> tenants)
    {
        var list = tenants.ToList();
        _exact = list
            .Where(t => !t.HostPattern.Contains('*'))
            .ToFrozenDictionary(t => t.HostPattern, StringComparer.OrdinalIgnoreCase);
        _wildcards = [.. list.Where(t => t.HostPattern.Contains('*'))];
    }

    public Tenant? Resolve(string host)
    {
        if (_exact.TryGetValue(host, out var exact)) return exact;

        foreach (var t in _wildcards)
        {
            if (host.EndsWith(t.HostPattern.TrimStart('*'), StringComparison.OrdinalIgnoreCase))
                return t;
        }
        return null;
    }
}

Hai quyết định ở đây đều có lý do: FrozenDictionary vì bảng host chỉ đọc và tra mỗi request; wildcard giữ dạng danh sách nhỏ vì số lượng ít và logic so khớp phức tạp hơn. Nếu wildcard cũng lên tới hàng trăm, cần cấu trúc khác — nhưng đừng tối ưu trước khi số đo nói cần.

N+1 mới là thứ giết hiệu năng

Đây là lý do chính khiến việc đổi collection không cứu được API:

// Sai: 1 query + N query
var orders = await db.Orders.AsNoTracking().Take(200).ToListAsync(ct);
foreach (var o in orders)
    o.Customer = await db.Customers.FindAsync([o.CustomerId], ct);

// Đúng: 1 query, projection chỉ lấy cột cần
var rows = await db.Orders.AsNoTracking()
    .OrderByDescending(o => o.CreatedAt)
    .Take(200)
    .Select(o => new OrderRow(o.Id, o.Customer!.Name, o.Total, o.CreatedAt))
    .ToListAsync(ct);

Nếu buộc phải Include nhiều navigation, cân nhắc AsSplitQuery() để tránh cartesian explosion. Và nhớ rằng AsNoTracking() chỉ bỏ change tracker, không bỏ chi phí truy vấn.

Sai lầm thường gặp

  • Dùng List.Remove trong vòng lặp. Mỗi lần xóa là O(n) dịch phần tử; xóa nhiều phần tử nên dùng RemoveAll(predicate) hoặc lọc một lần.
  • Dựa vào thứ tự của Dictionary hay HashSet. Thứ tự hiện tại là chi tiết implementation, không phải hợp đồng.
  • Đặt object mutable làm key. Hash đổi sau khi insert thì entry coi như mất.
  • Dựng FrozenDictionary trong mỗi request. Chi phí tạo sẽ lớn hơn lợi ích đọc, và bạn vừa thêm allocation vào hot path.
  • Trả IEnumerable<T> từ repository. Người gọi có thể duyệt lại và trigger query lần hai; trả List<T> hoặc IReadOnlyList<T> để hợp đồng rõ ràng.

2027: không có gì đột phá, chỉ có thêm lựa chọn

.NET 11 (GA tháng 11/2026, STS) và C# 15 tập trung vào trải nghiệm viết code hơn là thay đổi BCL. FrozenDictionary vẫn là lựa chọn chính cho read-heavy lookup; Dictionary.GetAlternateLookup sẽ tiếp tục mở rộng. Việc cần làm vẫn là đo bằng BenchmarkDotNet và xử lý N+1 trước khi nghĩ tới cấu trúc dữ liệu exotic.

Checklist

  1. Tìm N+1 trước: bật logging SQL của EF Core và đếm số query cho một request điển hình.
  2. Với mỗi collection trong hot path, biết trước thao tác chiếm nhiều thời gian nhất (tra cứu, chèn, duyệt).
  3. Truyền capacity cho List<T> và StringBuilder khi biết kích thước.
  4. Dùng ReadOnlySpan<char> cho parsing; chỉ chuyển sang Memory<T> khi cần qua await.
  5. Snapshot bất biến + một phép gán tham chiếu cho dữ liệu read-mostly; không lock ở đường đọc.
  6. Đo bằng BenchmarkDotNet 0.15.8 ở Release trước và sau khi đổi.

Đi tiếp: Đo lường hiệu năng với BenchmarkDotNet để kiểm chứng mọi thay đổi ở trên. Tải dữ liệu liên quan trong EF Core đi sâu vào N+1 và Include. Khi đã có dữ liệu đúng, bài Cache in-memory vs cache phân tán là bước tiếp theo.