Khác biệt giữa SortedList và SortedDictionary trong C#

Tóm tắt nhanh

Chi tiết triển khai

SortedList - Sorted Array

• Hai mảng song song: keys[] và values[].
• Luôn giữ sorted theo key.
• Binary search cho lookup.
• Insert/Remove: shift elements → O(n).
• Compact memory, cache-friendly.

SortedDictionary - Red-Black Tree

• Cây nhị phân cân bằng (self-balancing BST).
• Mỗi node: Key, Value, Left, Right, Color (Red/Black).
• Insert/Delete/Update: O(log n) guaranteed.
• Không hỗ trợ index-based access.

Ví dụ Benchmark

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Benchmark 
{
    static void Main() 
    {
        const int N = 100000;
        var keys = Enumerable.Range(0, N).OrderBy(_ => Guid.NewGuid()).ToArray();
        
        // 1. Insert
        var sl = new SortedList();
        var sd = new SortedDictionary();
        
        var sw = Stopwatch.StartNew();
        foreach (var k in keys) sl.Add(k, k.ToString());
        Console.WriteLine($"SortedList Add: {sw.ElapsedMilliseconds} ms");
        
        sw.Restart();
        foreach (var k in keys) sd.Add(k, k.ToString());
        Console.WriteLine($"SortedDictionary Add: {sw.ElapsedMilliseconds} ms");
        
        // 2. Lookup
        var lookups = Enumerable.Range(0, N).OrderBy(_ => Guid.NewGuid()).Take(10000).ToArray();
        
        sw.Restart();
        foreach (var k in lookups) _ = sl[k];
        Console.WriteLine($"SortedList Lookup: {sw.ElapsedMilliseconds} ms");
        
        sw.Restart();
        foreach (var k in lookups) _ = sd[k];
        Console.WriteLine($"SortedDictionary Lookup: {sw.ElapsedMilliseconds} ms");
        
        // 3. Index Access (chỉ SortedList)
        sw.Restart();
        for (int i = 0; i < 10000; i++) _ = sl.Values[i];
        Console.WriteLine($"SortedList Index Access: {sw.ElapsedMilliseconds} ms");
        
        // 4. Memory
        Console.WriteLine($"SortedList Memory: ~{GC.GetTotalMemory(false) / 1024} KB");
    }
}

Kết quả điển hình (N=100k)

SortedList Add: 1250 ms      ← O(n²) do shift array!
SortedDictionary Add: 45 ms  ← O(n log n)
SortedList Lookup: 12 ms
SortedDictionary Lookup: 15 ms
SortedList Index Access: 1 ms

Khi nào dùng SortedList?

• Dữ liệu khá tĩnh (load once, read many).
• Cần truy cập bằng index (GetKeyAt, GetValueAt, indexer).
• Collection nhỏ đến trung bình (< 1000-5000 items).
• Ưu tiên bộ nhớ thấp, cache locality.
• Duyệt tuần tự theo thứ tự key (foreach nhanh).

Khi nào dùng SortedDictionary?

• Dữ liệu thay đổi thường xuyên (insert/delete nhiều).
• Collection lớn (> 5000 items).
• Không cần index-based access.
• Cần hiệu năng O(log n) guaranteed cho mọi operation.

Immutable Alternatives (.NET 6+)

using System.Collections.Immutable;

// ImmutableSortedDictionary - thread-safe, persistent data structure
var immutable = ImmutableSortedDictionary.CreateBuilder();
for (int i = 0; i < 1000; i++) immutable.Add(i, i.ToString());
var dict = immutable.ToImmutable();

// Lookup
var value = dict[500]; // O(log n)

// "Mutation" - trả về instance mới, chia sẻ structure (structural sharing)
var dict2 = dict.SetItem(500, "new value"); 
// dict không thay đổi, dict2 là bản mới

Frozen Collections (.NET 8+)

using System.Collections.Frozen;

// Tối ưu cho read-heavy, tạo một lần đọc nhiều
var frozen = keys.ToFrozenDictionary(k => k, k => k.ToString());
// Lookup cực nhanh, nhưng tạo chậm hơn

Tóm tắt quyết định