Hash Tables Explained

Bài đăng này đã không được cập nhật trong 2 năm

Một trong những cấu trúc dữ liệu của tôi là mảng băm (Hash Table) vì nó đơn giản nhưng lại rất mạnh mẽ. Chúng giúp chúng ta lưu trữ cặp key - value một cách rất tiện lợi và hiệu quả.

Trong bài viết này, chúng ta sẽ cùng tìm hiểu về kiểu dữ liệu rất hữu ích này.

Buckets & The Hash Function

Ý tưởng cơ bản của mảng băm là cho phép chúng ta có thể lấy được dữ liệu đã được đánh index thông qua một key.

prices = {
  apple: 0.50,
  ice_cream: 3,
  steak: 10
}

Để implement một mảng băm, chúng ta cần 2 thành phần:

Một nơi đểu lưu trữ các thành phần của mảng băm.
Một phương thức để gán cặp key/value vào một vị trí xác định (index) trong nơi lưu trữ dữ liệu.

Nói cách khác, chúng ta cần một mảng thông thường và một hash function.

Implementing a Simple Hash Function

Hash function là một thành phần rất quan trọng của mảng băm. Nhiệm vụ của function này là chuyển đổi key được truyền vào thành index để chúng ta có thể lấy hoặc update dữ liệu được tham chiếu với key đó.

Đây chính là sự khác biệt lớn nhất giữa mảng thông thường và mảng băm.

Với mảng thông thường, bạn chỉ có thể truy cập đến các value được lưu trữ thông qua index của chúng và index chỉ có thể là số nguyên. Còn ở mảng băm, bạn sẽ truy cập đến value thông qua key và key có thể là bất cứ kiểu dữ liệu nào, miễn là bạn implement hash function cho nó.

Bạn có thể viết một hash function đơn giản cho key thuộc kiểu dữ liệu string bằng cách lấy convert tất cả các ký tự sang giá trị thuộc bảng mã ASCII và cộng chúng lại với nhau.

Sau đây là một ví dụ về hash function này

BUCKETS = 32
 
def hash(input)
  input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETS
end

Ở method này, chúng ta dùng method to_s để chắc chắn chúng ta làm việc với một string và tránh lỗi "undefined method". Tiếp theo, method chars sẽ convert string này thành mảng các ký tự. Sau đó, method inject được sử dụng để tính tổng các giá trị của mảng ký tự. Trong block được truyền vào cho method inject, chúng ta sử dụng method ord để convert ký tự thành giá trị tương ứng thuộc bảng mã ASCII. Cuối cùng, toán tử % được sử dụng để chắc chắn rằng kết quả nhận được sẽ không vượt quá kích thước của mảng chúng ta dùng lưu trữ. Mỗi phần tử của mảng này được gọi là một bucket.

Bucket Distribution

Performance là vấn đề luôn được chú trọng trong bất cứ bài toán nào. Vậy làm thế nào để đạt được performance tối đa cho mảng băm mà chúng ta xây dựng? Câu trả lời là khi mà tất cả các key được phân phối đồng đều vào các bucket.

Hãy cùng xem điều gì sẽ xảy ra khi chúng ta sử dụng hash function như đoạn code sau:

# Create an array of size BUCKETS with all elements set to 0
table   = Array.new(BUCKETS) { 0 }
letters = Array('a'..'z')
 
10_000.times do
  # Create a random string
  input = Array.new(5) { letters.sample }.join
 
  # Count hash distribution
  table[hash(input)] += 1
end

Và đây là kết quả chúng ta có được:

[302, 290, 299, 309, 321, 293, 316, 301, 296, 306, 340, 321, 313, 304, 318, 296, 331, 306, 348, 330, 310,
313, 298, 292, 304, 315, 337, 325, 325, 331, 319, 291]

Có thể dễ dàng nhận ra được rằng các key được phân phối vào bucket khá đồng đều. Tuy nhiên, hãy thử đoán xem chuyện gì sẽ xảy ra khi chúng ta tăng kính thước của mảng lưu trữ (số lượng bucket) lên?

Hãy cùng test luôn trong trường hợp số lượng bucket là 128:

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 176, 144, 
180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221, 206, 
220, 208, 213, 201, 191, 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 
57, 54, 40, 46, 32, 36, 30, 21, 25, 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]

Dễ dàng nhận ra là bây giờ các key không còn được phân phối đồng đều vào các bucket nữa.

Vậy vấn đề ở đây là gì? Nguyên nhân là do hash function chúng ta sử dụng chưa thực sự tốt. Đó là lý do vì sao mà có rất nhiều bucket trống ở giữa như trên.

A Better Hash Function

Chắc chắn là chúng ta sẽ cần một hash function tốt hơn để có thể convert các string thành index. Hãy cùng quan sát đoạn code sau:

BUCKETS = 256
 
def hash(input)
  input.to_s.each_char.inject(0) do |sum, ch|
    (sum << 8) ^ (ch.ord) ^ (sum >> 4)
  end % BUCKETS
end

Điểm khác biết của hash function này là dùng phép dịch bit (toán tử << và >>). Sau đó, chúng ta sẽ combine các giá trị sử dụng toán tử OR (^).

Phép dịch bit này sẽ trộn các giá trị lên, điều đó sẽ giúp chúng ta phân phối key vào các bucket một cách đồng đều hơn. Dù chưa phải là cách tối ưu nhưng nó sẽ tốt hơn so với việc chỉ dùng giá trị đơn thuần trong bảng mã ASCII.

Nếu bạn muốn một hash function thực sự tốt thì bạn có thể tìm hiểu về MurmurHash và rất có thể là nó tương tự với hash function mà Ruby sử dụng.

Handling Collisions

Câu hỏi đặt ra là chúng ta đã có được 1 mảng băm tốt chưa? Câu trả lời là chưa.

Để ý một chút thì bạn sẽ thấy rằng 2 key khác nhau có thể có chung index, điều này dẫn đến việc ghi đè giá trị, và tất nhiên là nó không hề tốt.

Việc này được gọi là hash collision và có một vài giải pháp để xử lý nó như sau:

Double Hashing (băm đôi)
Linear probing (thăm dò tuyến tính)
Separate chaining

Hãy quan sát một chút về phương pháp Separate chaining. Với phương pháp này, data được lưu trong mỗi bucket sẽ có dạng linked-list (danh sách liên kết).

Giả sử chúng ta có 2 key có cùng index là :abc và :ccc, khi đó mảng băm sẽ có dạng như sau:

3: [:abc, 100] -> [:ccc, 200]
4: nil
5: [:yx, 50]

Vấn đề ở đây là khi muốn truy cập đến một key, ngoài việc lấy được index qua hash function, ta còn phải duyệt trên linked-list của mỗi bucket một lần nữa. Đây chính là nhược điểm của phương pháp này. Độ phức tạp cho mỗi lần duyệt là O(n) thay vì O(1) như expect.

Để tránh việc linked-list có kích thước lớn và làm giảm performance của mảng băm, thật đơn giản là tăng số lượng bucket cần sử dụng lên, nghĩa là tăng kích thước của mảng lưu trữ.