Có nhẽ khái niệm này cũng không thật xa lạ gì với những bạn hữu Engineer và bản thân mình sau hai năm đầu đi làm việc và lần trước nhất nghe về khái niệm này cũng hiểu một cách rất là mơ hồ . Yeah và dĩ nhiên không để nỗi đau thêm dài (thật ra mình tò mò là chính) nên tôi cũng tìm hiểu về kiểu cách thao tác của Hash Table và san sẻ với ae để sở hữu cái nhìn sâu sát hơn về Hash Table để ứng dụng vào công việc của mình một cách hiệu quả nhất
Trước tiên tôi cũng xin giảng giải ngắn gọn: Hash Table là một tập các cặp key-value không theo trật tự, và mỗi key là duy nhất (unique). Hash table thường được sử dụng để triển khai tài liệu dạng collection có cấu trúc như Map, Set … Và có thể dễ nhận thấy trong các tiếng nói lập trình phổ quát như Java, C++, Python, Go. Hash table thông thường sẽ sở hữu các hoạt động sinh hoạt cơ bản gồm có: tìm kiếm, thêm và xoá. Array hay Linked List sẽ không còn thể đạt được những điểm sau:
- Tìm kiếm trong một mảng không có trật tự trong trường hợp xấu nhất sẽ tốn một lượng thời kì tuyến tính với độ dài của mảng đó
- Trong một mảng có trật tự thì việc tìm kiếm sẽ rất nhanh nếu tất cả chúng ta dùng thuật toán tìm kiếm nhị phân (Binary Search) nhưng đánh đổi lại và việc tất cả chúng ta thêm một thành phần vào mảng lại không hiệu quả
- Với trường hợp của linked list thì trái lại việc thêm/xoá một thành phần khá đơn giản nhưng việc tìm kiếm cũng tốn thời kì giống như trường hợp của mảng không có trật tự
Và dựa trên đặc tính đó, hash table sử dụng một chuỗi các Linked List để xử lý vấn đề đụng độ tài liệu. Chàng trai Hash Table là đúc rút từ những điểm mạnh của Array và Linked List Cách hoạt động của Hash Table sẽ gồm có 2 bước:
- Key sẽ tiến hành chuyển đổi thành chỉ mục (index) dạng số bằng phương pháp sử dụng hàm băm
- Chỉ mục này sẽ quyết định Linked List nào sẽ chứa cặp key-value tương ứng
Để dễ hình dung hơn tất cả chúng ta cùng xem 1 ví dụ đơn giản sau. Tất cả chúng ta sẽ sở hữu cấu trúc tài liệu chứa đến 1000 records với khoá là một số integer tình cờ. Và để phân bổ data một cách đồng đều, tất cả chúng ta sẽ dùng nhiều short list. Với tất cả những record có khoá kết thúc bằng 000 sẽ thuộc 1 list VD: 1000, 2000, 3000 …. tất cả những record có khoá kết thúc bằng 001 sẽ thuộc 1 list khác VD: 1001, 2001 … và cứ tiếp tục như vậy tất cả chúng ta có 1000 list Theo phong cách chia như trên. Và có thể triển khai dưới mặt coding như sau:
var table = new LinkedList[1000]
Ở đây LinkedList trình diễn cho list các cặp key-value có liên kết với nhau. Việc tất cả chúng ta thêm một record key-value gồm có 2 bước:
- Tất cả chúng ta trích xuất 3 chữ số cuối của key hash = key % 1000
- Sau đó tất cả chúng ta thêm cặp key-value này vào table[hash]
hash = key % 1000 table[hash].AddFirst(key, value)
Hành động trên luôn tốn một lượng thời kì không đổi. Và việc tất cả chúng ta tìm kiếm sẽ như sau
value = table[key%1000].Find(key)
Bởi vì các khoá của một cặp key-value là tình cờ nên ta có thể xem số lượng record trong mỗi list là gần như nhau. Và vì tất cả chúng ta có 1000 list và nhiều nhất là 1000 record thế nên sẽ rất ít record trong một list table[key%1000] và dĩ nhiên việc tìm kiếm sẽ rất nhanh. Ae có thể thấy Time Complexity (mức độ phức tạp nhìn nhận và đánh giá theo thời kì) của việc tìm kiếm và thêm mới là O(1). Cũng giống với cách hoạt động trên thì việc xoá cũng tốn một khoản thời kì không đổi
Thông qua ví dụ trên tất cả chúng ta cũng thấy việc Hash Table phối hợp cả Array và Linked List để lưu trữ tài liệu thế nào. Trong bài tiếp theo tất cả chúng ta sẽ đi sâu hơn để tìm hiểu các ví dụ mang tính thực tế hơn về Hash Table và khái niệm Amortized Constant Time Performance
Mình xin cảm ơn các bạn đã dành thời kì đọc bài san sẻ này và mong nhận được feedback cũng như những san sẻ đóng góp của bạn hữu. Chúc bạn hữu một chiếc tết vui vẻ bên gia đình và nhớ giữ gìn sức khoẻ trong thời khắc COVID vẫn vẫn đang còn phức tạp Happy New Year!!!
