Cách hash làm việc trong Ruby

Hash là một datatype hữu ích và được sử dụng nhiều nhất trong Ruby. Nó có một cấu trúc tốt và có thể dễ dàng mô phỏng các vấn đề thực tế, cùng với đó là tốc độ truy vấn cực nhanh. Chính vì thế mà Ruby Hash được sử dụng gần như ở mọi nơi và mọi ứng dụng. Nó cũng từng được sử dụng ngay chính bên trong Ruby để lưu toàn bộ các hàm, biến và hằng số. Chúng ta thường mặc định khi sử dụng hash rằng chúng sẽ chạy như vậy mà không biết bên trong nó thực thi như thế nào. Ở bài viết này, tôi muốn chia sẻ với các bạn về cách mà hash hoạt động, làm thế nào mà nó có thể hoạt động một cách hiệu quả như vậy.

Implmentation

big_four_stock_prices = {
    :google => 801.23,
    :apple => 115.57,
    :facebook => 128.35,
    :microsoft => 57.19
}

Điều gì xảy ra ở đây ? Hãy cùng tìm hiểu:

Đầu tiên, chương trình thực thi sẽ cấp phát bộ nhớ cho toàn bộ cấu trúc dữ liệu hash trên. Sau đó thì nó sẽ thực hiện việc hash key đầu tiên:

:google.hash

#=> 3592

Hàm hash được định nghĩa bên trong class kernel của Ruby, vậy nên tất cả các object khác trong ruby (đêu kế thừa từ Object) đều sẽ chứa hàm này. Giá trị này sẽ tùy thuộc vào một vài yếu tố khác nhau, tuy nhiên điều quan trọng là giá trị này sẽ không that đổi trong phiên làm việc (runtime) của chương trình.

Việc tiếp theo cần thực hiện đó là lưu giá trị (value) của key. Giá trị sẽ được đặt trong một bucket (hoặc bin). Một Ruby hash khởi điểm sẽ cấp phát 11 bucket. Công việc cần làm bây giờ là quyết định xem giá trị sẽ được lưu ở bucket nào. Chương trình thực thi chỉ cần thực hiện phép tính căn bản sau:

:google.hash % 11
# => 5

Điều này có nghĩa là giá trị của key :google (801.23) sẽ được đặt ở bucket thứ 5 của bảng hash với một định danh như sau:

[:google, 801.23]

Quá trình trên sẽ được thực hiện cho tất cả các cặp key-value của hash. Để lấy giá trị ra, trình thực thi chỉ cần lặp lại việc tính toán để tìm bucket và lấy giá trị ra từ bucket đó. Tuy nhiên còn một vài trường hợp đặc biệt mà ta cần xem xét sau.

Trùng bucket

Các bạn có thể thắc mắc rằng nếu chỉ có 11 bucket, sớm muộn gì cũng sẽ xảy ra trường hợp có 2 giá trị bị trùng bucket. Điều gì sẽ xảy ra tiếp theo ? Ruby Hash sẽ lưu các giá trị cùng một bucket theo dạng một danh sách liên kết (linked list). Nếu key của hash mà trùng với key được lưu trong bucket (kiểm tra bằng hàm equal?) thì giá trị của nó sẽ được trả về, nếu không thì nó sẽ di chuyển tiếp trong danh sách để tìm ra giá trị đúng.

Tất nhiên là quá trình trên sẽ tốn rất nhiều thời gian - giả sử như một bucket chứa 1000 giá trị khác ? Về mặt lý thuyết thì nó có thể tốn nhiều thời gian để trả về giá trị mong muốn, mà chúng ta dùng hash phần lớn với mục đích là nó có tốc độ truy xuất cao. Ruby tất nhiên sẽ có giải pháp cho vấn đề này. Ruby sẽ tính toán số lượng trung bình của các giá trị trong mỗi bucket trong toàn bộ bảng hash. Nếu số lượng này vượt quá 5, Ruby sẽ xóa bô 11 bucket mặc định và tạo số lượng bucket mới, cùng với đó là tính toán lại để đặt các giá trị có sẵn vào các bucket mới kia. Như vậy, danh sách liên kết trong mỗi bucket sẽ nhỏ và sẽ làm giảm thời gian tìm kiếm giá trị.

Sự quan trọng của thuật toán hash

Để củng cố sự hiểu biết về hash, hãy cùng làm một ví dụ sau. Vấn đề gì sẽ xảy ra nếu ta override hàm hash mặc định của Ruby và luôn trả về một số nhất định nào đó ? Nếu chiếu theo những gì ta đã biết ở trên thì có thể thấy là giá trị mới được đưa vào hash luôn được trỏ vào cùng một bucket. Như vậy thì thời gian để lấy một phần tử ở phía cuối của danh sách liên kết sẽ rất lâu. Hãy thử nghiệm nó với đoạn code sau:

require 'benchmark'

class GoodHash
end

class BadHash
  def hash
    7
  end
end

hashing_algorithm == BadHash  # switch to GoodHash for inverse

17.times do |ex|
  lookup_key = nil
  size = 2**ex
  test_hash = {}
  (1..size).each do |n|
    index = hashing_algorithm.new
    lookup_key = index if n > size/2 and lookup_key.nil?
    test_hash[index] = rand
  end

  Benchmark.bm do |bench|
    bench.report("Hash size: #{size} elements 10000 times\n") do
      10000.times do
        test_hash[lookup_key]
      end
    end
  end
end

Đoạn code trên sẽ sinh ra một hash như sau:

test_hash = {
    #<BadHash:0x007f92941eaae0> => 0.029655456018705673,
    #<BadHash:0x007f92941e3c68> => 0.973576967117432,
    #<BadHash:0x007f92941e1508> => 0.2443654110192186,
    #<BadHash:0x007f92941d1ab8> => 0.7536013342129247
}

Bây giờ ta sẽ xem xét từng dòng code:

Đầu tiên ta tạo một class mới GoodHash sử dụng hàm hash mặc định của Ruby. Tiếp theo là lặp 17 lần, mỗi lần sẽ lấy giá trị bình phương. Sau đó ta đưa một giá trị bất kỳ nào đó vào test_hash sử dụng một instance của GoodHash làm key. Sau đó ta tìm với một giá trị key nào đó 1000 lần vào đo kết quả khi thực hiện nó trước khi thực hiên với BadHash.

Kết quả sẽ như sau:

Kết quả trên cho thấy những gì về mặt lý thuyết đều đúng. Khi số lượng giá trị tăng dần thì thời gian tìm kiếm với BadHash tăng theo cấp số mũ, còn với GoodHash thì thời gian không khác biệt là bao.

Ruby cấp phát các bucket mới như thế nào ?

Ruby sẽ tính toán với một danh sách các số nguyên tó mà gần với lũy thừa của 2 nhất. Mục đích của việc này là để khi module giữa giá trị hash và số lượng bucket luôn khác nhau, tránh trường hợp ra cùng kết quả dẫn tới việc giá trị bị đưa vào cùng một bucket quá nhiều.

References

Diving into How Hashes Work in Ruby