Một trong những cấu trúc dữ liệu yêu thích của tôi là bảng băm vì nó đơn giản và mạnh mẽ.
Bạn có thể đã sử dụng nó trước đây vì đây là một cách hiệu quả để lưu trữ các cặp khóa-giá trị.
Có một số khái niệm khoa học máy tính thú vị đằng sau việc triển khai bảng băm đáng để nghiên cứu và đó chính xác là những gì chúng ta sẽ làm trong bài viết này!
Nhóm &Hàm băm
Ý tưởng cơ bản của bảng băm là cho phép chúng ta sử dụng một cách hiệu quả (trong O(1) ) truy xuất dữ liệu được lập chỉ mục bởi một khóa.
Như một bản cập nhật nhanh, đây là cách sử dụng bảng băm trông như thế nào trong Ruby:
prices = {
apple: 0.50,
ice_cream: 3,
steak: 10
}
Để triển khai một bảng băm, chúng ta cần hai thành phần:
- Nơi lưu trữ các mục trong bảng
- Một cách để gán các cặp khóa / giá trị cho một vị trí (chỉ mục) cụ thể bên trong kho dữ liệu này
Nói cách khác, chúng ta cần một mảng &một hàm băm.
Triển khai một hàm băm đơn giản
Hàm băm là một thành phần quan trọng của bảng băm.
Hàm này biến khóa thành một chỉ mục có thể được sử dụng để tra cứu hoặc cập nhật giá trị liên quan của nó.
Đây là sự khác biệt lớn giữa mảng đơn giản và bảng băm.
Trong một mảng, bạn chỉ có thể truy cập các giá trị thông qua chỉ mục của chúng và chỉ mục chỉ có thể là một số. Trong bảng băm, bạn truy cập các giá trị thông qua khóa của chúng và khóa có thể là bất kỳ thứ gì (chuỗi, ký hiệu, số nguyên…), miễn là bạn có thể viết hàm băm cho nó.
Bạn có thể viết một hàm băm đơn giản cho các chuỗi bằng cách chuyển đổi tất cả các chữ cái thành các giá trị ASCII của chúng rồi cộng chúng lại.
Đây là một ví dụ :
BUCKETS = 32
def hash(input)
input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETS
end
Trong phương pháp này, chúng tôi sử dụng to_s để đảm bảo rằng chúng tôi đang làm việc với một chuỗi.
Điều này sẽ giúp chúng tôi tránh lỗi "phương pháp không xác định". Sau đó là sự kết hợp của các ký tự chars (để chuyển đổi chuỗi thành một Array các ký tự của nó) &inject để cộng các giá trị.
Bên trong khối, tôi đã sử dụng ord để chuyển đổi các ký tự thành giá trị thứ tự của chúng.
Cuối cùng, tôi đã sử dụng toán tử modulo % để đảm bảo giá trị kết quả phù hợp với mảng. Chúng tôi gọi mỗi mục nhập trong mảng này là 'thùng'.
Phân phối nhóm
Lý tưởng nhất là chúng tôi muốn tất cả các nhóm của chúng tôi được lấp đầy đồng đều, điều này sẽ mang lại cho chúng tôi hiệu suất tốt nhất khi chúng tôi cần truy xuất một giá trị.
Hãy xem điều gì sẽ xảy ra khi chúng tôi kiểm tra hàm băm của mình bằng mã này:
# 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
Điều này tạo ra các kết quả sau:
[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ó vẻ như các khóa của chúng tôi được phân bổ đồng đều…
… Nhưng điều gì sẽ xảy ra nếu chúng ta tăng số lượng nhóm?
Trong ví dụ này, tôi đã sử dụng kích thước nhóm là 128 (trước đây là 32):
[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]
Đó không còn là một bản phân phối tuyệt vời nữa!
Chuyện gì đang xảy ra?
Vấn đề là hàm băm của chúng ta không đủ tốt vì tất cả các chuỗi có cùng kích thước nằm trong một phạm vi nhất định. Đó là lý do tại sao chúng tôi có rất nhiều thùng rỗng ở giữa.
Chức năng băm tốt hơn
Chúng tôi cần một cách tốt hơn để chuyển đổi chuỗi của chúng tôi thành một chỉ mục. Hãy xem một cách triển khai có thể thực hiện được.
BUCKETS = 256
def hash(input)
input.to_s.each_char.inject(0) do |sum, ch|
(sum << 8) ^ (ch.ord) ^ (sum >> 4)
end % BUCKETS
end
Những gì đang xảy ra ở đây là sự thay đổi bit (với >> &<< toán tử). Các giá trị được kết hợp bằng cách sử dụng “toán tử OR độc quyền” (^ ).
Sự thay đổi bit này sẽ trộn lẫn mọi thứ, điều này sẽ cung cấp cho chúng tôi phân phối khóa tốt hơn . Không hoàn hảo, nhưng nó tốt hơn chức năng dựa trên ASCII đơn giản của chúng tôi 🙂
Nếu bạn muốn có một hàm băm thích hợp, bạn sẽ xem xét một thứ gì đó giống như MurmurHash, mà tôi tin rằng đó là những gì Ruby sử dụng.
Xử lý va chạm
Chúng tôi chưa có bảng băm hữu ích.
Tại sao?
Chà, bạn có thể nhận thấy rằng khi hai khóa băm thành cùng một chỉ mục, chúng sẽ ghi đè lên giá trị cũ và điều đó không tốt!
Đây được gọi là xung đột băm và có một số chiến lược để đối phó với những điều này.
Ví dụ :
- Băm kép
- Thăm dò tuyến tính
- Chuỗi riêng biệt
Hãy xem xét chuỗi riêng biệt, nơi chúng tôi sử dụng danh sách được liên kết để lưu trữ các mục nhập cho một “nhóm” cụ thể.
Vì vậy, nếu chúng ta giả định rằng :abc &:ccc băm cho cùng một chỉ mục, bảng băm của chúng ta sẽ trông giống như sau:
3: [:abc, 100] -> [:ccc, 200] 4: nil 5: [:yx, 50]
Sau đó, chúng tôi sẽ cần tìm kiếm tuyến tính để tìm ra khóa chính xác.
Điều này sẽ ảnh hưởng đến hiệu suất của chúng tôi vì thời gian tra cứu của chúng tôi có thể giảm dần về phía O(n) , thay vì O(1) như mong đợi .
Nếu bạn không quen với
O(something)này ký hiệu được gọi là "Ký hiệu Big-O".
Để tránh danh sách được liên kết phát triển quá sâu và do đó làm giảm hiệu suất của bảng băm, cần tạo lại bảng băm bằng cách sử dụng số lượng nhóm lớn hơn.
Ruby thực hiện việc này cho bạn một cách tự động, nhưng bạn vẫn nên biết.
Kết luận
Mục đích của bài viết này không phải để bạn viết cách triển khai bảng băm mà là để giúp bạn hiểu cách chúng thực sự hoạt động, vì vậy tôi hy vọng rằng bạn thấy điều đó thú vị!
Đừng quên chia sẻ bài đăng này để blog tiếp tục phát triển 🙂