Hashtable in a nutshell - Phần 2

Trong phần một, 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ề kỹ thuật table doubling. Ngoài ra, mình cũng sẽ trình bày về amortization, rolling hash và 1 số vấn đề liên quan. Mời các bạn cùng đọc.

Table doubling

Ý tưởng

Ý tưởng của table doubling đó là chúng ta sẽ bắt đầu với một số m đủ nhỏ. Lúc này trong hashtable vẫn chưa có phần tử nào, tức là n = 0. Ta lần lượt insert các item vào hashtable, nghĩa là n sẽ tăng dần lên. Khi n tăng tới một ngưỡng nào đó đủ lớn thì ta sẽ cần tăng kích thứơc của hashtable, tức là tăng m lên thành một số m' nào đó. Còn khi n giảm xuống thì chúng ta lại giảm kích thước của hashtable xuống. Khi m thay đổi thành m', thao tác này gọi là rehash. Có nghĩa là ta sẽ cấp phát một vùng nhớ mới cho hashtable, có kích thước là m', sau đó mang toàn bộ các item trong table cũ (có size là m) qua table mới. Thao tác này cũng cần tính lại hashfunction cho toàn bộ tập key để xác định vị trí mới. Vì khi m thay đổi thì tức là hashfunction đã thay đổi, lúc này vị trí của item trong table mới sẽ thay đổi với table cũ. Chi phí của một thao tác re-hash sẽ vào khoảng O(n + m), tức là bao gồm chi phí cấp phát một vùng nhớ mới, cộng chi phí duyệt qua toàn bộ table cũ, và chi phí tính lại hashfunction cho n item.
Tức là vào khoảng Θ(n+m) =Θ(n) nếu m=Θ(n).
Rồi, sơ qua ý tưởng là vậy, cụ thể hơn thì mình sẽ đi vào ví dụ dưới đây.

Ví dụ

  • Đầu tiên, mình bắt đầu với một số m vừa phải, giả sử m = 8, lúc này n = 0.
  • Bước tiếp theo, mình bắt đầu insert các item cho tới khi n = 7.
  • Tiếp theo, mình insert item thứ 8. Lúc này n = 8 = m, nên mình phải thực hiện thao tác re-hash đã nói ở trên. Lúc này, mình cần chọn một số m' phù hợp.
    • Giả sử mình chọn m' = m + 1. Như vậy bạn sẽ thấy cứ mỗi lần insert thêm một phần tử mới, mình lại cần thực hiện thao tác re-hash. Mà thao tác này như tính ở trên thì không rẻ tí nào -> Bad!
    • Một cách khác là chọn m' = m*2. Như vậy, mình sẽ chỉ phải thực hiện thao tác re-hash vào các thời điểm, n = 8, n = 16, n = 32, n = 64, n = 128. Vào những thời điểm này, thao tác insert sẽ tốn chi phí ~O(n), còn lại thì các thao tác insert sẽ tốn chi phí là O(1) mà thôi.
    • Do chúng ta chọn m' = m *2, nên kỹ thuật này được gọi là table doubling.
  • Vậy giờ nếu mình muốn xoá phần tử ra khỏi hashtable thì sao? Giả sử khi n = 9, lúc này, m = 16 (do vừa mới re-hash). Lúc này mình xoá một phần tử đi, n giảm xuống còn 8. Nếu lúc này mình thực hiện re-hash để giảm kích thước table xuống thì sẽ gặp một vấn đề như sau. Nếu n thay đổi liên tục từ 8 sang 9, từ 9 về 8, rồi lại từ 8 sang 9, thì thao tác re-hash sẽ thực hiện liên tục (trường hợp này rất dễ gặp trong thực tế đúng không?). Cho nên mình sẽ không thực hiện re-hash khi n giảm xuống 8, mà khi n = m/4 = 4. Lúc này nếu re-hash và m giảm xuống còn 8, thì n = 4 và vẫn còn dư các slot nếu thực hiện insert.

Vậy lúc nào thì nên re-hash

Thường thì yếu tố này sẽ tuỳ theo bạn chọn. Trong ví dụ trên, mình chọn n = 8 thì thực hiện re-hash, tuy nhiên thực tế, chúng ta sẽ dựa trên loadfactor ( alpha = n/m). Nếu giá trị này vượt một ngưỡng nào đó, ví dụ 0.6 hay 0.7 thì có thể thực hiện re-hash. Nói một cách đơn giản tức là hashtable đã bị full khoảng 3/4 slot.

Trick khi thực hiện re-hash

  • Phần này là do mình tình cờ phát hiện ra khi thảo luận với một đồng nghiệp. Khi chúng ta tăng size của table từ m lên m' thì chắc chắn phải thực hiện việc tính hashfunction cho toàn bộ tâp key. Tuy nhiên khi giảm size của table từ m xuống m' thì chi phí của việc tính hashfunction sẽ rẻ hơn khá nhiều.
  • Thật vậy, vì chúng ta chọn m' = m/2 (Trường hợp giảm size). Ngoài ra nếu bạn để ý tới các hàm hashfunction mà mình đã giới thiệu ở Phần 1, bạn sẽ thấy các hàm này phần lớn đều có 2 điểm chung, đó là phần đầu tiên sẽ tính ra một số int nào đó khá lớn, và phần sau đó là lấy modulo với m!
    • Ví dụ: ở hàm hash h(k = [ (a * k) mod 2 ^ w] >> (w -r), thì đoạn lấy (a k) mod 2 ^ w là như nhau với mọi số m. Chỉ có thao tác *>> (w-r)** là lấy r bit ngoài cùng bên phải, với m = 2^r. Do bản chất của m là các số luỹ thừa của 2, cho nên thao tác lấy modulo thực ra tương đương với việc lấy r bit bên phải ngoài cùng (m = 2 ^ r).
  • Cho nên khi m giảm xuống một số m' = m/2, tức là chúng ta chỉ cần lấy vị trí index tại table cũ, sau đó thực hiện dịch 1 bit qua bên phải (index = index >> 1), thì sẽ có vị trí index tại table mới.

Amortized

Tiếp theo, mình sẽ giải thích một chút về khái niệm Amortized. Khái niệm này có nghĩa là, một thao tác có chi phí là Amortized T(n) nếu k thao tác đó tốn tổng chi phí nhỏ hơn k * T(n).
Nguyên nhân nhắc tới khái niệm này là vì thao tác re-hash ở trên, sẽ khiến chi phí khi insert một item bị đội lên O(n) vào một số thời điểm nhất định. Tuy nhiên đối với các cấu trúc dữ liệu, điều chúng ta quan tâm là chi phí cho một số lần lớn các thao tác, chứ không phải là chi phí của từng thao tác riêng lẻ. Do đó, chúng ta có thể nói khi insert một item vào hashtable tốn chi phí là Amortized O(1). Bởi vì insert n item thì chỉ tốn tổng chi phí là nhỏ hơn O(n).

String matching

Phần tiếp theo, mình sẽ giới thiệu về một ứng dụng của hashtable trong việc giải bài toán string matching.

Bài toán

Cho hai string s và t, hỏi s có xuất hiện trong t hay không? (Mở rộng ra thành s xuất hiện ở những vị trí nào trong t).
Đây là một bài toán xuất hiện rất nhiều, và dĩ nhiên cũng có một số cách giải quyết, tốt hơn là phương pháp naive method. Ví dụ giải thuật KMP, hay là Rabin Karp. Trong đó, giải thuật Rabin Karp dựa trên một kỹ thuật trong hashtable đó, chính là rolling hash.

Naive method

Cách cơ bản nhất của bài toán string matching đó chính là duyệt từng substring của t và kiểm tra có bằng với s hay không.

any(s == t[i : i + len(s)] for i in range(len(t) − len(s)))

Mỗi lần so sánh sẽ cần chi phí là O(|s|). (Lưu ý: |s| là độ dài của chuỗi s, |t| là độ dài của chuỗi t).
Vậy tổng chi phí cho cả bài toán là O( (|t| - |s|) * |s|) -> O ( |t| * |s|)

Giải thuật Rabin Karp

Ý tưởng chính của giải thuật Rabin Karp, đó là tiết kiệm chi phí so sánh các string thông qua việc tính một hàm h(x). Nếu h(s) và h(t') bằng nhau, thì có nghĩa là có khả năng hai string s và t' là giống nhau, lúc này chúng ta mới check từng ký tự của s và t'. Còn nếu h(s) và h(t') khác nhau, thì chắc chắn là hai string s và t' là khác nhau. Và chi phí tính h(s) và h(t') là tương đối nhỏ.
Chi phí của các thao tác như sau:

  • Tính h(s) -> Cần O(|s|)
  • Duyệt qua toàn bộ substring của t, có độ dài bằng độ dài của s, tính h() cho các substring đó, và so sánh với h(s) đã tính ở trên -> Cần O( |t| * |s|)
  • Nếu một substring có giá trị hash bằng với h(s) thì thực hiện so sánh từng ký tự của substring đó với s -> Cần O(|s|) Lúc này mình sẽ cố gắng giảm thiểu chi phí ở bước 2, từ O(|t|* |s| ) xuống một giá trị nhỏ hơn, thông qua rolling hash.

Rolling hash

Giả sử cho một string x. Ta xét 3 thao tác sau:

  • r(): trả về giá trị hash function h(x) của string x.
  • r.append(c): add thêm ký tự c vào cuối string x.
  • r.skip(): remove ký tự đầu tiên của string x.

Nói một cách đơn giản thì Rolling hash là một hash function, cho phép tính giá trị hash một cách nhanh chóng, đặc biệt khi giá trị cần tính hash được thay đổi theo cách append() hay skip() như mô tả ở trên, thì hash function sẽ tính ra kết quả nhanh chóng dựa trên giá trị cũ.
Có nghĩa là chúng ta có giá trị h(x), nếu ta append thêm 1 ký tự mới vào x, hay skip ký tự đầu tiên của x, thì việc tính giá trị hash function của x (sau khi đã thay đổi) là rất nhanh chóng. Cụ thể thế nào thì ta xét ví dụ sau.

Ví dụ

Giả sử s = "kipalog", t = "youshouldkipalogformypostinkipalog".
Và hàm h() được định nghĩa như sau:
enter image description here
Trong đó a là hằng số, còn $c_{i}$ là các ký tự của chuỗi cần tính giá trị hash. Trong trường hợp để tránh hàm h() trả về giá trị quá lớn, chúng ta có thể lấy kết quả ở trên modulo với m.

  • Bước 1: Tính h(s) = h("kipalog") = 'k' * 10^6 + 'i' * 10^5 + 'p' * 10^4 + 'a' * 10^ 3 + 'l' * 10^2 + 'o' * 10^1 + g * 10^0.
  • Bước 2: Tính h() cho các chuỗi con có độ dài là 7 của chuỗi t.
    • Chuỗi "youshou": h("youshou") = 'y' * 10^6 + 'o' * 10^5 + 'u' * 10^4 + 's' * 10^ 3 + 'h' * 10^2 + 'o' * 10^1 + u * 10^0
    • Chuỗi "oushoul": h("oushoul") = 'o' * 10^6 + 'u' * 10^5 + 's' * 10^4 + 'h' * 10^ 3 + 'o' * 10^2 + 'u' * 10^1 + l * 10^0
    • Ok, phần tinh hoa nằm ở đây các bạn ạ. Vì để tiết kiệm chi phí, nên mình muốn tính giá trị h("oushoul") dựa trên giá trị h("youshou") vừa mới tính. Thì theo công thức định nghĩa hàm h() ở trên, mình sẽ có : h("oushoul") = (h("youshou") - 'y' * 10^ 6 ) * 10 + 'l' * 10^ 0.
    • Một cách tổng quát ta có: Nếu ta tính hashfunction của chuỗi $s_{i}$ chứa các ký tự từ $c_{0}$ tới $c_{i}$. Thì việc tính hash function của chuỗi $s_{i+1}$ chứa các ký tự từ $c_{1}$ tới $c_{i+1}$ được tính như sau: h($s_{i+1}$) = [ (h($s_{i}$) - $c_{0}$ * 10 ^ i ) ] * 10 + $c_{i+1}$ * 10^0.
    • Lần lượt theo cách này, ta tính giá trị hash function cho toàn bộ các chuỗi con còn lại của t. Lúc này thao tác tính h() chỉ tốn chi phí là O(1) mà thôi.
  • Bước 3: Lấy các giá trị h() đã tính ở bước 2 và so sánh với h(s) tính ở bước 1. Nếu bằng nhau thì tiến hành compare từng ký tự để ra được kết quả sau cùng.

Như vậy bạn đã thấy, thao tác so sánh 2 string với nhau đã được rút gọn thông qua việc tính giá trị hash function. Giá trị hash function của mỗi chuỗi con sẽ được tính nhanh dựa trên kết quả của giá trị hash function của chuỗi con ngay trước đó.

Vậy tổng chi phí của thuật toán này là bao nhiêu:

  • Tính hash function của chuỗi s -> O(|s|)
  • Tính hash function của chuỗi con đầu tiên của t có độ dài bằng với độ dài của s -> O(|s|)
  • Dùng rolling hash, tính hash function của các chuỗi con còn lại của t và so sánh với giá trị hash của chuỗi s -> O(|t|)
  • Nếu giá trị hash của chuỗi con của t bằng với giá trị hash của chuỗi s, ta thực hiện so sánh từng ký tự của chuỗi con này với chuỗi s -> O(|s|)

Vậy là tới đây, mình đã giải thích xong về cách hoạt động của thuật toán Rapin Karp đối với bài toán string matching, và kỹ thuật rolling hash.
Tới đây đã hết chưa nhỉ? Mời các bạn đón đọc những bài viết tiếp theo của mình, và đừng quên kipalog nhé ;)

LePhongVu 25-04-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 5 tháng trước
23 2
White
23 4
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...
Lê Phong Vũ viết 4 tháng trước
23 4
White
23 28
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 28
Bài viết liên quan
White
44 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 8 tháng trước
44 7
{{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á!