Tìm kiếm bằng Hash (Hash-based Lookup) là gì? Giải thích dễ hiểu kèm demo trực quan

Điểm mạnh lớn nhất: thời gian truy cập trung bình O(1).

Hash Table hoạt động thế nào?

Hash Table gồm:

• Hàm băm (hash function): chuyển key → index.
• Buckets (ô chứa): các ô chứa danh sách các phần tử.
• Collision (va chạm): hai key khác nhau cho ra cùng index.

Để xử lý collision, ta có 2 nhóm chính: open addressing & chaining.
Trong bài này, ta dùng chaining: mỗi bucket chứa một danh sách (linked list).

Ưu điểm

• Trung bình O(1) cho insert, search, delete.
• Không cần dữ liệu phải sắp xếp.
• Rất mạnh cho các bài toán lookup, caching, indexing.

Nhược điểm

• Không duy trì thứ tự các phần tử.
• Trong trường hợp hash xấu → có thể O(n).

Ví dụ minh hoạ

Hash Table size = 5

Key "cat" → hash = 12 → index = 12 % 5 = 2
Key "dog" → hash = 22 → index = 2 → collision → đưa vào chain
Key "lion" → hash = 31 → index = 1

Demo Hash Table – Hash-based Lookup (Chaining)

Demo dưới đây cho phép bạn:

• Nhập key → xem hash → xem index.
• Thêm key vào Hash Table.
• Tìm kiếm → highlight bucket và node trong chain.
• Quan sát collision khi nhiều key rơi vào cùng bucket.

Phân tích đoạn code demo

1. Hàm băm

function simpleHash(str) {
    var hash = 0;
    for (var i = 0; i < str.length; i++) {
        hash += str.charCodeAt(i);
    }
    return hash;
}

2. Chèn key vào bucket

hashTable[index].push(key);

3. Tìm kiếm

for (var i = 0; i < chain.length; i++) {
    if (chain[i] === key) return i;
}

Kết luận

Hash-based Lookup là một trong những kỹ thuật mạnh nhất để tìm kiếm nhanh trong cấu trúc dữ liệu.
Demo trên cho thấy rõ cách hash function ánh xạ key → bucket → chain, và collision được xử lý như thế nào.

Đây chính là nền tảng của Map, Dictionary, Object trong các ngôn ngữ hiện đại.