Hash table

Bài Big-O nói Dictionary.ContainsKey chỉ tốn một bước, dù dictionary có một triệu key. Tìm trong List<T> thì phải so từng phần tử. Dictionary nhanh hơn vì bên trong nó là một hash table.

Khái niệm

🗳️ Hash table (bảng băm): một array các ô (bucket), mỗi key được xếp vào đúng một ô để khi tìm chỉ cần xem ô đó.

🎲 Hàm băm (hash function): hàm biến một key thành một con số, dùng con số đó để chọn ô chứa key.

🚧 Va chạm (collision): hai key khác nhau được hàm băm đưa vào cùng một ô.

Dictionary<TKey, TValue> và HashSet<T> của .NET đều là hash table.

Ví dụ

Một bản Dictionary tối giản lưu tồn kho theo tên, dùng hàm băm rất đơn giản là độ dài tên chia lấy dư cho số ô:

var stock = new MiniDictionary();
stock.Set("Bút bi", 120);
stock.Set("Vở", 0);
stock.Set("Balo", 8);
Console.WriteLine(stock.Get("Vở"));   // 0

class Entry
{
    public string Key { get; }
    public int Value { get; set; }

    public Entry(string key, int value)
    {
        Key = key;
        Value = value;
    }
}

class MiniDictionary
{
    private readonly List<Entry>[] _buckets =
        new List<Entry>[4];

    public MiniDictionary()
    {
        for (int i = 0; i < _buckets.Length; i++)
        {
            _buckets[i] = new List<Entry>();
        }
    }

    public int BucketOf(string key)
    {
        return key.Length % _buckets.Length;
    }

    public void Set(string key, int value)
    {
        List<Entry> bucket = _buckets[BucketOf(key)];
        foreach (Entry e in bucket)
        {
            if (e.Key == key)
            {
                e.Value = value;
                return;
            }
        }
        bucket.Add(new Entry(key, value));
    }

    public int Get(string key)
    {
        foreach (Entry e in _buckets[BucketOf(key)])
        {
            if (e.Key == key)
            {
                return e.Value;
            }
        }
        throw new KeyNotFoundException(key);
    }
}

new List<Entry>[4] là array 4 ô, mỗi ô là một list các cặp key-value. Constructor tạo sẵn list rỗng cho từng ô.
BucketOf là hàm băm: "Vở" dài 2 ký tự, 2 % 4 bằng 2, nên nằm ở ô 2.
Set và Get chỉ duyệt đúng một ô. Mỗi ô chỉ có vài phần tử nên gần như là O(1).
Không có key thì ném KeyNotFoundException, giống lỗi ở bài Dictionary của khoá C# Core.

▶ Mô phỏng: Ba lần Set rồi Get

var stock = new MiniDictionary();
stock.Set("Bút bi", 120);
stock.Set("Vở", 0);
stock.Set("Balo", 8);
Console.WriteLine(stock.Get("Vở"));

// MiniDictionary (rút gọn)
public int BucketOf(string key)
{
    return key.Length % _buckets.Length;
}

public void Set(string key, int value)
{
    List<Entry> bucket = _buckets[BucketOf(key)];
    foreach (Entry e in bucket)
    {
        if (e.Key == key)
        {
            e.Value = value;
            return;
        }
    }
    bucket.Add(new Entry(key, value));
}

public int Get(string key)
{
    foreach (Entry e in _buckets[BucketOf(key)])
    {
        if (e.Key == key)
        {
            return e.Value;
        }
    }
    throw new KeyNotFoundException(key);
}

Xem từng bước

BucketOf("Bút bi"): key dài 6 ký tự, 6 % 4 = 2, nên chỉ cần xem ô 2.
Chưa có "Bút bi": thêm cặp "Bút bi" → 120 vào ô 2.
BucketOf("Vở"): key dài 2 ký tự, 2 % 4 = 2, nên chỉ cần xem ô 2.
So key thứ 1 trong ô 2: "Bút bi" khác "Vở", xem tiếp.
Chưa có "Vở": thêm vào cuối ô 2. Ô này đã có "Bút bi": hai key khác nhau cùng một ô là va chạm, tìm sau này phải so nhiều key hơn.
BucketOf("Balo"): key dài 4 ký tự, 4 % 4 = 0, nên chỉ cần xem ô 0.
Chưa có "Balo": thêm cặp "Balo" → 8 vào ô 0.
BucketOf("Vở"): key dài 2 ký tự, 2 % 4 = 2, nên chỉ cần xem ô 2.
So key thứ 1 trong ô 2: "Bút bi" khác "Vở", xem tiếp.
So key thứ 2 trong ô 2: đúng là "Vở".
Thấy "Vở" ở ô 2, trả về 0. Chỉ xem một ô nên gần như O(1).

Hàm băm thật của .NET dùng mọi ký tự của key, nên các key rải đều ra các ô. Khi số phần tử quá nhiều so với số ô, Dictionary tự tăng số ô và xếp lại, giống List<T> gấp đôi array.

Thử ngay

In ra ô của từng sản phẩm:

var table = new MiniDictionary();
Console.WriteLine(table.BucketOf("Bút bi"));
Console.WriteLine(table.BucketOf("Vở"));
Console.WriteLine(table.BucketOf("Balo"));
Console.WriteLine(table.BucketOf("Thước"));
Console.WriteLine(table.BucketOf("Máy tính"));

Đoán trước khi chạy: ngoài "Bút bi" và "Vở", còn cặp nào rơi vào cùng một ô?

Xem kết quả

"Bút bi" (6 ký tự) và "Vở" (2 ký tự) cùng ở ô 2. "Balo" (4) và "Máy tính" (8) cùng ở ô 0.

Đó là va chạm: tìm trong ô này phải so từng key trong list của ô. Nếu mọi key rơi vào một ô, hash table chậm như duyệt list, O(n).

Lỗi hay gặp

Dùng object của class làm key. Bài Value type và reference type của khoá C# Core đã cho thấy hai object khác nhau thì không bằng nhau, dù dữ liệu giống hệt. Mặc định, Dictionary cũng băm và so key theo tham chiếu.

// SAI — tạo object mới thì không tìm lại được
var prices = new Dictionary<ProductCode, decimal>();
prices[new ProductCode { Sku = "PEN-01" }] = 5000m;
Console.WriteLine(prices.ContainsKey(
    new ProductCode { Sku = "PEN-01" }));   // False

class ProductCode
{
    public string Sku { get; set; } = "";
}

// ĐÚNG — dùng chính mã string làm key
var prices = new Dictionary<string, decimal>();
prices["PEN-01"] = 5000m;
Console.WriteLine(prices.ContainsKey("PEN-01")); // True

Muốn dùng class làm key thì class đó phải override hai method Equals và GetHashCode để so theo dữ liệu.

Tóm tắt

Hash table là array các ô. Hàm băm chọn ô cho từng key.
Tra, thêm, xoá theo key trung bình là O(1).
Va chạm là chuyện bình thường. Mọi key cùng một ô thì chậm thành O(n).
Key là object của class thì so theo tham chiếu, trừ khi class override Equals và GetHashCode.

Khái niệm

🗳️ Hash table (bảng băm): một array các ô (bucket), mỗi key được xếp vào đúng một ô để khi tìm chỉ cần xem ô đó.

🎲 Hàm băm (hash function): hàm biến một key thành một con số, dùng con số đó để chọn ô chứa key.

🚧 Va chạm (collision): hai key khác nhau được hàm băm đưa vào cùng một ô.

Dictionary<TKey, TValue> và HashSet<T> của .NET đều là hash table.

Ví dụ

Một bản Dictionary tối giản lưu tồn kho theo tên, dùng hàm băm rất đơn giản là độ dài tên chia lấy dư cho số ô:

var stock = new MiniDictionary();
stock.Set("Bút bi", 120);
stock.Set("Vở", 0);
stock.Set("Balo", 8);
Console.WriteLine(stock.Get("Vở"));   // 0

class Entry
{
    public string Key { get; }
    public int Value { get; set; }

    public Entry(string key, int value)
    {
        Key = key;
        Value = value;
    }
}

class MiniDictionary
{
    private readonly List<Entry>[] _buckets =
        new List<Entry>[4];

    public MiniDictionary()
    {
        for (int i = 0; i < _buckets.Length; i++)
        {
            _buckets[i] = new List<Entry>();
        }
    }

    public int BucketOf(string key)
    {
        return key.Length % _buckets.Length;
    }

    public void Set(string key, int value)
    {
        List<Entry> bucket = _buckets[BucketOf(key)];
        foreach (Entry e in bucket)
        {
            if (e.Key == key)
            {
                e.Value = value;
                return;
            }
        }
        bucket.Add(new Entry(key, value));
    }

    public int Get(string key)
    {
        foreach (Entry e in _buckets[BucketOf(key)])
        {
            if (e.Key == key)
            {
                return e.Value;
            }
        }
        throw new KeyNotFoundException(key);
    }
}

new List<Entry>[4] là array 4 ô, mỗi ô là một list các cặp key-value. Constructor tạo sẵn list rỗng cho từng ô.
BucketOf là hàm băm: "Vở" dài 2 ký tự, 2 % 4 bằng 2, nên nằm ở ô 2.
Set và Get chỉ duyệt đúng một ô. Mỗi ô chỉ có vài phần tử nên gần như là O(1).
Không có key thì ném KeyNotFoundException, giống lỗi ở bài Dictionary của khoá C# Core.

▶ Mô phỏng: Ba lần Set rồi Get

var stock = new MiniDictionary();
stock.Set("Bút bi", 120);
stock.Set("Vở", 0);
stock.Set("Balo", 8);
Console.WriteLine(stock.Get("Vở"));

// MiniDictionary (rút gọn)
public int BucketOf(string key)
{
    return key.Length % _buckets.Length;
}

public void Set(string key, int value)
{
    List<Entry> bucket = _buckets[BucketOf(key)];
    foreach (Entry e in bucket)
    {
        if (e.Key == key)
        {
            e.Value = value;
            return;
        }
    }
    bucket.Add(new Entry(key, value));
}

public int Get(string key)
{
    foreach (Entry e in _buckets[BucketOf(key)])
    {
        if (e.Key == key)
        {
            return e.Value;
        }
    }
    throw new KeyNotFoundException(key);
}

Xem từng bước

BucketOf("Bút bi"): key dài 6 ký tự, 6 % 4 = 2, nên chỉ cần xem ô 2.
Chưa có "Bút bi": thêm cặp "Bút bi" → 120 vào ô 2.
BucketOf("Vở"): key dài 2 ký tự, 2 % 4 = 2, nên chỉ cần xem ô 2.
So key thứ 1 trong ô 2: "Bút bi" khác "Vở", xem tiếp.
Chưa có "Vở": thêm vào cuối ô 2. Ô này đã có "Bút bi": hai key khác nhau cùng một ô là va chạm, tìm sau này phải so nhiều key hơn.
BucketOf("Balo"): key dài 4 ký tự, 4 % 4 = 0, nên chỉ cần xem ô 0.
Chưa có "Balo": thêm cặp "Balo" → 8 vào ô 0.
BucketOf("Vở"): key dài 2 ký tự, 2 % 4 = 2, nên chỉ cần xem ô 2.
So key thứ 1 trong ô 2: "Bút bi" khác "Vở", xem tiếp.
So key thứ 2 trong ô 2: đúng là "Vở".
Thấy "Vở" ở ô 2, trả về 0. Chỉ xem một ô nên gần như O(1).

Thử ngay

In ra ô của từng sản phẩm:

var table = new MiniDictionary();
Console.WriteLine(table.BucketOf("Bút bi"));
Console.WriteLine(table.BucketOf("Vở"));
Console.WriteLine(table.BucketOf("Balo"));
Console.WriteLine(table.BucketOf("Thước"));
Console.WriteLine(table.BucketOf("Máy tính"));

Đoán trước khi chạy: ngoài "Bút bi" và "Vở", còn cặp nào rơi vào cùng một ô?

Xem kết quả

"Bút bi" (6 ký tự) và "Vở" (2 ký tự) cùng ở ô 2. "Balo" (4) và "Máy tính" (8) cùng ở ô 0.

Đó là va chạm: tìm trong ô này phải so từng key trong list của ô. Nếu mọi key rơi vào một ô, hash table chậm như duyệt list, O(n).

Lỗi hay gặp

// SAI — tạo object mới thì không tìm lại được
var prices = new Dictionary<ProductCode, decimal>();
prices[new ProductCode { Sku = "PEN-01" }] = 5000m;
Console.WriteLine(prices.ContainsKey(
    new ProductCode { Sku = "PEN-01" }));   // False

class ProductCode
{
    public string Sku { get; set; } = "";
}

// ĐÚNG — dùng chính mã string làm key
var prices = new Dictionary<string, decimal>();
prices["PEN-01"] = 5000m;
Console.WriteLine(prices.ContainsKey("PEN-01")); // True

Muốn dùng class làm key thì class đó phải override hai method Equals và GetHashCode để so theo dữ liệu.

Tóm tắt

Hash table là array các ô. Hàm băm chọn ô cho từng key.
Tra, thêm, xoá theo key trung bình là O(1).
Va chạm là chuyện bình thường. Mọi key cùng một ô thì chậm thành O(n).
Key là object của class thì so theo tham chiếu, trừ khi class override Equals và GetHashCode.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận

Hash table

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận