Tìm hiểu khái niệm Hash Table

Phần này chắc không còn xa lạ gì nữa với các kỹ sư và chính bản thân mình sau 2 năm làm việc. Lần đầu tiên mình nghe về khái niệm này, thật sự không hiểu rõ. Vì thế, mình quyết định tìm hiểu về cách Hash Table hoạt động và chia sẻ kiến thức này với mọi người để có cái nhìn sâu sắc hơn về Hash Table và áp dụng hiệu quả vào công việc của mình.

Trước tiên, mình xin giải thích ngắn gọn: Hash Table là một tập hợp các cặp key-value không có thứ tự, trong đó mỗi key là duy nhất (unique). Hash Table thường được sử dụng để triển khai dữ liệu theo dạng collection như Map, Set,… Ví dụ các ngôn ngữ lập trình phổ biến như Java, C++, Python, Go. Hash Table thường có các hoạt động cơ bản như tìm kiếm, thêm và xóa. Array và Linked List không thể đạt được những ưu điểm sau:

  • Tìm kiếm trong một mảng không có thứ tự tốn thời gian tuyến tính theo độ dài của mảng trong trường hợp xấu nhất.
  • Trong một mảng có thứ tự, tìm kiếm nhanh hơn nếu sử dụng thuật toán tìm kiếm nhị phân (Binary Search), nhưng thêm một phần tử vào mảng không hiệu quả.
  • Linked List cho phép thêm/xóa phần tử dễ dàng, nhưng tìm kiếm tốn thời gian giống như trong mảng không có thứ tự.
Có Thể Bạn Quan Tâm :   Body pump là gì? Lưu ý gì khi tập luyện Body pump đúng cách?

Dựa trên những đặc tính đó, Hash Table sử dụng chuỗi các Linked List để giải quyết vấn đề đụng độ dữ liệu. Hash Table kết hợp các ưu điểm của Array và Linked List. Cách hoạt động cơ bản của Hash Table gồm 2 bước:

  1. Key được chuyển đổi thành chỉ mục (index) dạng số thông qua hàm băm.
  2. Chỉ mục này quyết định Linked List nào sẽ chứa cặp key-value tương ứng. (Thêm hình ảnh)

Để dễ hiểu, hãy xem một ví dụ đơn giản. Giả sử chúng ta có một cấu trúc dữ liệu chứa 1000 bản ghi với khóa là một số nguyên ngẫu nhiên. Chúng ta muốn phân bổ dữ liệu một cách đồng đều, nên sử dụng nhiều danh sách ngắn. Các bản ghi có khóa kết thúc bằng 000 được nhóm vào một danh sách ví dụ: 1000, 2000, 3000,… Các bản ghi có khóa kết thúc bằng 001 được nhóm vào danh sách khác ví dụ: 1001, 2001,… Và tiếp tục như vậy, chúng ta có 1000 danh sách theo cách phân chia trên. Dưới đây là cách triển khai bằng mã:

Có Thể Bạn Quan Tâm :   My Neighbor Alice (ALICE) là gì? Toàn tập về tiền điện tử ALICE

var table = new LinkedList[1000]

Ở đây, LinkedList đại diện cho danh sách các cặp key-value liên kết. Để thêm một cặp key-value vào table:

  1. Trích xuất 3 chữ số cuối của khóa: hash = key % 1000
  2. Thêm cặp key-value này vào table[hash]

hash = key % 1000 table[hash].AddFirst(key, value)

Quá trình này luôn mất một khoảng thời gian không đổi. Và việc tìm kiếm sẽ được thực hiện như sau:

Có Thể Bạn Quan Tâm :   Tương Sinh Tương Hợp Là Gì ? Ứng Dụng Ngũ Hành Tương Sinh Phong Thuỷ?

value = table[key % 1000].Find(key)

Vì khóa của một cặp key-value là ngẫu nhiên, số lượng bản ghi trong mỗi danh sách gần như nhau. Với 1000 danh sách và tối đa 1000 bản ghi, số lượng bản ghi trong một danh sách (table[key % 1000]) sẽ rất ít. Do đó, việc tìm kiếm sẽ rất nhanh. Thời gian tìm kiếm và thêm mới trong Hash Table có độ phức tạp như nhau và tương đối nhanh O(1). Tương tự, việc xóa mất một khoảng thời gian không đổi.

Từ ví dụ trên, chúng ta đã thấy cách Hash Table kết hợp Array và Linked List để lưu trữ dữ liệu. Trong bài tiếp theo, chúng ta sẽ đi sâu hơn và tìm hiểu các ví dụ thực tiễn hơn về Hash Table và khái niệm Amortized Constant Time Performance.

Mình xin cảm ơn mọi người đã dành thời gian đọc bài viết này. Mình mong nhận được phản hồi và đóng góp từ mọi người. Chúc mừng năm mới!!!

Back to top button