Hashtable in a nutshell - Phần 1

Tổng quan

Hashtable là một cấu trúc dữ liệu quan trọng và được sử dụng rộng rãi trong các ứng dụng và các bài toán lập trình.
Một số ví dụ về ứng dụng của hash table như sau:

  • Hash indexed trong database.
  • Xây dựng từ điển.
  • Spell correction
  • Trong router
  • Trong các compiler/editor và nhiều ứng dụng khác.

Hiện nay đa phần các ngôn ngữ lập trình hiện đại đều đã cài đặt sẵn hash table như C++, Java, Ruby, Rust, v.v...
Trong bài viết này mình sẽ giới thiệu với các bạn về cơ chế hoạt động của hash table, làm thế nào để xây dựng một hash table.
Mình cũng sẽ giới thiệu các kiến thức xoay quanh như re-hash, pre-hashing, hash function, rolling adt, chi phí tìm kiếm trong một hash table.

Dictionary

  • Trước khi giải thích về hash table, mình sẽ giới thiệu về bài toán dictionary, một abstract data type (kiểu dữ liệu trừu tượng). Dù ngày nay thì khái niệm này không còn phổ thông nữa, nhưng qua đó sẽ dễ dàng hơn để giải thích cho bạn về hash table ở phía sau. Dictionary là một tập hợp các item, bên trong mỗi item là một key và value. Một Dictionary sẽ có 3 thao tác chính.
  • Insert(item): Thêm cặp giá trị (k, v) vào dictionary. Cho phép overwrite lại v nếu đã tồn tại key k từ trước.
  • Search(key): Cho trước 1 key k, lấy ra giá trị v nếu cặp (k, v) đã được insert vào dictionary.
  • Delete(key): Xóa cặp giá trị (key, value) ra khỏi dictionary.

Những bài toán dạng dictionary này tương đối phổ biến trong thực tế và ứng dụng. Ví dụ, có một hàm f(x), trong đó x là một từ tiếng Anh, và f(x) trả về ý nghĩa của từ đó, hoặc từ tiếng Pháp tương đương.

Có rất nhiều cách để giải quyết bài toán dictionary. Trong cuốn "The art of computer programming" volumn 3, chương 6, tác giả D.Knuth có trình bài về vấn đề này, "how to find a data that has been stored with a given identification" và cũng có đưa ra một số giải pháp để giải quyết. Các phương pháp thường hay gặp đó là red-black tree, AVL tree, skip list và hash table.
Mỗi phương pháp sẽ có những ưu/nhược điểm riêng về tốc độ thực thi và không gian bộ nhớ đối với 3 phép toán cơ bản đã trình bày ở trên.
So sánh các cấu trúc dữ liệu này, mình sẽ dành một bài viết khác. Tuy nhiên đối với phép toán Search (tìm kiếm 1 value với 1 key cho trước) thì AVL Tree, red-black tree có độ phức tạp là O(log n). Tuy nhiên O(log n) vẫn là lớn đối với một vài bài toán có tập data lớn. Trong rất nhiều ứng dụng, việc tìm kiếm là rất quan trọng và chiếm nhiều tài nguyên. Vậy có cách nào tối ưu tốc độ hơn nữa không? Thì câu trả lời là hash table được sử dụng để giải quyết bài toán tìm kiếm mà độ chi phí cần chỉ là O(1).

Ý tưởng ban đầu

Đầu tiên, mình muốn nói về một phương pháp đơn giản nhất để cài đặt cấu trúc dữ liệu cho dictionary, đó là dùng một direct access table, nói đơn giản thì đó chính là 1 array.
(Để ngắn gọn, mình gọi mỗi một cặp (key, value) là một item).

Ý tưởng của phương pháp này là lưu trữ các item trong một mảng, đánh index bởi key. Tức là key cũng chính là index của array.

key value
0 null
1 null
2 value1
3 null
4 value2
5 value3
6 null

Trong ví dụ trên, mình đã lưu một tập hợp có 3 item { (2, value1), (4, value2), (5, value3) } vào trong một mảng có size bằng 7.
Các slot còn trống thì data sẽ là null.
Vậy dùng cách này sẽ phát sinh hai vấn đề.
Vấn đề 1: Chỉ dùng được cho trường hợp key là một số nguyên dương. Vậy nếu key là 1 string/object/ hay 1 kiểu dữ liệu nào khác thì sao?
Vấn đề 2: Phải dùng một bộ nhớ khá lớn để lưu trữ!
Để giải 2 vấn đề này chúng ta đi tiếp vào phần tiếp theo!

pre-hashing và hash function

Pre-hashing

  • Chúng ta mong muốn mỗi key có thể là bất kỳ loại object nào chứ không chỉ là một integer, nên chúng ta cần 1 hàm pre-hashing để convert từ 1 kiểu object/ string/ v.v.. sang số nguyên không âm.
  • Ta định nghĩa hàm Pre-hashing như sau: Là một function p: K -> I để biến đổi từ object bất kỳ sang một số nguyên 32/64 bit.
  • Nếu K là số nguyên, thì bài toán đơn giản.
  • Nếu K là một string, vậy ta có thể dùng hàm như sau: $$PrehashString('abc') == 97 * (256*2) + 98 * (256*1) + 99$$
  • Nếu K là một object. Có thể dùng nhiều cách. Ví dụ, trả về địa chỉ vật lý trong vùng nhớ của object ( Không có hai item bất kỳ nằm cùng một nơi trong memory). Một cách khác đó là mỗi object đều được biểu diễn dưới dạng một dãy các bit nhị phân. Việc cần làm chỉ đơn giản là cắt nhỏ dãy bit ra, rồi mix lại với nhau để ra được một số nguyên.
  • Vậy tới đây, ta đã giải được vấn đề 1 ở trên.

Hash function

(Động từ "hash" có nghĩa là cắt nhỏ ra thành nhiều mảnh, sau đó mix lại với nhau. Đây là 1 từ có nguồn gốc từ tiếng Pháp cổ, "hachet")

  • Mục đích của 1 hàm hash function h này là giảm không gian key (integer) xuống một kích thước hợp lý (ta gọi là m), m cũng sẽ là kích thước của table mà chúng ta sử dụng. Đồng nghĩa với việc chúng ta sẽ làm giảm kích thước của "direct access table" đã nhắc tới ở trên. Các bạn có thể xem hình dưới đây để hiểu hơn cách làm của hash function. alt text Ở đây, ta insert 2 cặp item (k1, value1) và (k2, value2) vào bảng. Hàm h(k1) tính ra vị trí của key k1 là 1, nên value1 sẽ nằm tương ứng với index 1. Hàm h(k2) = 0, nên value2 sẽ nằm tương ứng với index bằng 0.
  • Với m xấp xỉ với n. Có thể là m = n/2 hay n/3, v.v... Chúng ta sẽ tính m ở các phần sau.
  • Như vậy chúng ta thấy có thể xảy ra tình huống với hai key khác nhau ki != kj, nhưng hàm hash function có thể trả về cùng một kết quá, tức là h(ki) = h(kj) , khi đó hai item tuy có giá trị key khác nhau, nhưng sẽ cùng nằm chung một nơi, do kết quả của hàm hash function là như nhau. Tình huống này gọi là collision. Để giải quyết vấn đề này chúng ta có 2 cách.

Giải quyết Colission

Chaining

  • Chaining là kỹ thuật sử dụng một linklist để chứa các phần tử colliding trong mỗi slot của hash table. alt text Trong hình trên, ta insert 3 cặp item (k1, value1), (k2, value2), và (k4, value4) vào bảng. Tuy nhiên h(k1) = h(k4) = 1, nên ta sẽ dùng một link list để lưu trữ 2 cặp item (k1, value1) và (k4, value4).
  • Như vậy, trong tình huống tệ nhất, hàm hash h trả về một giá trị duy nhất với mọi giá trị ki bất kỳ, khi đó ta sẽ có một linklist có độ dài n, với n là tổng số phần tử được insert. Như vậy, thao tác tìm kiếm một phần tử bất kỳ sẽ có chi phí ϴ(n).
  • Giả sử có n item cần đặt vào hash table có m slot. Giả sử có một hàm hash function nào đó hoạt động tốt và phân phối đều các item này, như vậy mỗi slot sẽ chứa trung bình n/m phần tử. Ta gọi đây là load factor α . Khi đó chi phí tối đa để tìm được 1 phần tử sẽ là O(1 + n/m). (Cần 1 thao tác tính hash function và n/m số lần duyệt qua link list). Do m = ϴ(n) ở trên nên n/m sẽ xấp xỉ với ϴ(1), do đó O(1 + n/m) sẽ gần như là const.

Open addressing.

  • Với kỹ thuật open addressing, chúng ta sẽ không nhét các item vào một slot, mà sẽ cố gắng tìm slot còn đang trống để đặt item vào. Tất nhiên để làm được điều này, thì điều kiện cần là m > n, tức là số slot trong table phải lớn hơn số item sẽ được đặt vào table.

  • Thuật ngữ probe, có nghĩa là hàm hash function sẽ chỉ định vị trí còn trống để probe (thăm dò) cho key (với mục đích insert/search/delete).

  • Cụ thể, ta có hash function h(), với một key k bất kỳ, ta sẽ xét tập hợp các hàm h(k,0), h(k,1), h(k,2), ..., h(k, m-1):

    • insert: Tính h(k,i) cho tới khi tìm được một vị trí trống để insert item. Ví dụ: Ta cần insert các cặp item (k1, v1), (k2, v2), (k3, v3), (k4, v4) vào bảng có size m = 10. h(k1,0) = 2. Xét slot 2 trong bảng, còn trống nên ta đặt vào slot này cặp (k2, v2). h(k2,0) = 2. Xảy ra collision, ta tính tiếp h(k2,1), nếu không tìm được slot trống, ta lại tính tiếp h(k2,2) cho tới khi tìm được slot trống thì thôi. Do m > n nên chắc chắn quá trình này sẽ dừng ở một bước nào đó.
    • Search: Cho một key k2, để tìm được item có key bằng k2, ta tính lần lượt h(k2,0), h(k2,1), h(k2,2), ... cho tới khi tìm được thì thôi.
    • Delete: Thao tác delete sẽ phức tạp hơn 1 tí. Vẫn tiếp tục với ví dụ trên, nếu ta xóa cặp (k1,v1), lúc này slot 2 trong bảng sẽ empty. Tiếp theo ta thử tìm kiếm key k2, do h(k2,0) = 2, mà ở slot 2 là empty, vậy nếu theo thao tác search ở trên, kết quả tìm kiếm sẽ là không thấy! Dù thực ra cặp (k2,v2) đang nằm ở đâu đó trong bảng. Để giải quyết vấn đề này, khi xóa cặp (k1,v1) ta sẽ đặt một flag ở đây, ví dụ là DELETE. Đối với thao tác tìm kiếm, sẽ coi slot có cờ DELETE như là một empty slot, tương tự với thao tác search.
  • Có một số chiến lược khác nhau để tìm slot còn trống.

    • linear probing: h(k,i) = (h(k) + i) mod m
    • double hashing: h(k,i) = (h1(k) + i * h2(k)) mod m. (h1 và h2 là hai hàm hash khác nhau).

Một số hash function

  • Hàm hash đơn giản nhất là modulo:
    • h(k) = k mod m
  • Multiplication method:
    • h(k = [ (a * k) mod 2 ^ w] >> (w -r), với k có w bit, và m = 2 ^ r
  • Universe hash
    • H(k) = [(ak + b) mod p] mod m, với a và b là hai số random giữa 0 và p-1. Còn p là số nguyên tố sao cho p > |U| (Size của key-space)
  • Làm sao để biết một hàm hash là tốt hay dở? Rõ ràng, việc phân định một hàm hash dựa trên nhiều yếu tố, một yếu tố chính là xác suất xảy ra tình huống collision. Người ta quy ước, một hàm hash đủ tốt nếu xác suất xảy ra collision nhỏ hơn 1/m P ( h(ki) = h(kj), ki != kj) < 1/m Ngoài ra, hàm hash phải đủ nhanh, để thực thi phép tính h(k) chỉ trong O(1), do đó nên chúng ta thường thấy các hàm hash thường chỉ bao gồm các phép toán cơ bản như dịch bit, modulo v.v...

Rehash

  • Vậy tới đây, chúng ta đã sắp build được một hash table với hash function, chaining hoặc open addressing, còn thiếu yếu tố duy nhất đó chính là số m. Nếu chúng ta chọn m quá lớn sẽ xảy ra tình huống lãng phí bộ nhớ, còn nếu m quá nhỏ cũng ko tốt, vì xảy ra collision. Vấn đề đặt ra là phải tìm được số m vừa đủ, ko quá lớn, không quá nhỏ với n item sẽ được insert vào hash table. Cụ thể hơn, mình sẽ trình bày ở phần 2. Ngoài ra, ở phần tiếp theo, mình sẽ trình bày thêm về Amortization, giải thuật Karp-Rabin trong string matching, rolling ADT.

Xin cảm ơn

Lê Phong Vũ - 20-4-2018

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Lê Phong Vũ

4 bài viết.
60 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
23 2
Dẫn nhập Cây nhị phân là một cấu trúc dữ liệu hết sức quen thuộc với chúng ta. Có rất nhiều nghiên cứu và các thuật toán xoay quanh cấu trúc dữ liệ...
Lê Phong Vũ viết 4 tháng trước
23 2
White
23 27
Chuyện của tôi Vào đợt nghỉ lễ giỗ tổ HùngKing vừa rồi, mình có nhận được một mời phỏng vấn ở một công ty A nọ. Mặc dù thời điểm phỏng vấn không t...
Lê Phong Vũ viết 3 tháng trước
23 27
White
8 1
Trong (Link), mình đã giới thiệu tới các bạn về hashtable, và một số kiến thức xoay quanh. Trong phần tiếp theo này, mình xin trình bày tiếp tục về...
Lê Phong Vũ viết 4 tháng trước
8 1
Bài viết liên quan
White
23 2
Dẫn nhập Cây nhị phân là một cấu trúc dữ liệu hết sức quen thuộc với chúng ta. Có rất nhiều nghiên cứu và các thuật toán xoay quanh cấu trúc dữ liệ...
Lê Phong Vũ viết 4 tháng trước
23 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
4 bài viết.
60 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!