(91) 350-9520 support@omarine.org M-F: 7 AM - 7 PM; Weekends: 9 AM - 5 PM

Hash và chiến lược tìm kiếm

Giải vấn đề là tìm kiếm lời giải. Hiệu quả tìm kiếm phụ thuộc vào tốc độ xử lý, nhưng quan trọng hơn nhiều, là chiến lược thu gọn không gian.

Hàm băm (Hash function)

Hàm băm là một hàm ánh xạ dữ liệu kỹ thuật số có kích thước bất kỳ thành dữ liệu kỹ thuật số có kích thước cố định. Giá trị trả về của hàm gọi là giá trị băm hay mã băm, với một độ dài dữ liệu gọi là chiều dài băm.

Một giá trị băm với chiều dài cố định, chẳng hạn một chuỗi nhị phân 32 bits, có thể đại diện cho các số nguyên liên tiếp từ 0 tới 2³²-1, là cơ sở cho quá trình định lượng hóa. Với một chiều dài băm và thuật toán băm thích hợp, một hàm băm có thể được sử dụng để định lượng hóa, tính toán chỉ số để truy vấn tức thời một bảng dữ liệu kích thước lớn. Thời gian tìm kiếm bản ghi không phụ thuộc kích thước của bảng theo số lượng bản ghi, mà tính bằng thời lượng tính toán băm cộng với thời gian xử lý một vài kỹ thuật sau định lượng. Không gian tìm kiếm trên cơ sở dữ liệu cực lớn được thu gọn thành một vài bản ghi, thậm chí một bản ghi. Một bảng dữ liệu với một triệu bản ghi thu gọn không gian tìm kiếm trở thành một bản ghi sẽ nhanh hơn danh sách tuần tự đơn thuần có kích thước tương đương, một triệu lần. Bảng dữ liệu sử dụng hàm băm như thế gọi là bảng băm.

Bảng băm (Hash table)

Bảng băm sử dụng hàm băm để tính toán chỉ số vào một mảng. Chỉ số mảng dùng làm địa chỉ đi vào một vùng dữ liệu của bảng, có thể là một bản ghi, một vài bản ghi, hoặc không có bản ghi nào. Trường hợp không có bản ghi nghĩa là chưa có bản ghi nào dành cho địa chỉ ấy. Mỗi phần tử của mảng gọi là một khe(slot). Như vậy mảng là mảng của các khe được đánh địa chỉ. Khe có thể chứa trực tiếp một bản ghi, trong trường hợp này mảng khe chứa toàn bộ dữ liệu của bảng. Trường hợp khác, khe chỉ chứa tham chiếu đến một cấu trúc danh sách chứa các bản ghi. Một cấu trúc danh sách “đựng” một vài bản ghi giống như một cái “xô”(bucket) đựng bản ghi và “treo” vào một địa chỉ trên mảng khe. Khe nào không có bản ghi thì hoặc là không có xô treo(đó là tham chiếu- con trỏ trỏ vào null) hoặc là treo một cái xô không(con trỏ trỏ vào một danh sách rỗng). Như vậy theo hình dung gọi mảng khe là mảng xô cũng được. Khác nhau là, mảng khe hàm ý mảng địa chỉ, còn mảng xô hàm ý mảng dữ liệu bảng. Bản ghi phải là dữ liệu kiểu từ điển với cặp khóa-giá trị. Vì vậy mảng thuộc dạng mảng kết hợp(associative array).

Tính toán chỉ số

Với mỗi khóa vào(key), hàm băm sẽ cho ra một giá trị băm(hash). Chỉ số(index) sau đó được tính toán tùy theo người thiết kế bảng, thông thường lấy phần dư của phép chia hash cho kích thước mảng(array_size)

hash = hashfunc(key)
index = hash % array_size

Nếu cỡ mảng là lũy thừa của 2 thì phần dư này có thể đạt được bằng mặt nạ bit, trong ngôn ngữ C, sử dụng phép toán “&” như sau

index = hash & (array_size-1);

Phép toán mặt nạ bit làm tăng tốc độ thực hiện.

Xung đột khóa

Xung đột khóa là không tránh khỏi khi các khóa được băm ngẫu nhiên vào bảng. Dù cho phân phối khóa là đồng đều trong bảng, như chúng ta đã biết về vấn đề sinh nhật, nếu 2500 khóa được băm vào một triệu khe thì xác suất gần 96% có ít nhất hai khóa được băm vào cùng một khe. Bạn có thể vận dụng công thức (*) trong bài trước và tiện ích kcalc để tính thử. Kết quả chính xác hơn là 95.6%. Vì vậy các bảng băm đều cần các biện pháp xử lý xung đột khóa.

Chọn hàm băm tốt

Yêu cầu cơ bản là hàm băm phải đảm bảo phân phối đồng đều các giá trị băm. Phân phối không đồng đều gây ra tăng xung đột và giảm hiệu quả của bảng do quá nhiều khóa bị dồn vào một khe hoặc hiện tượng tụ đám của các khóa liên tiếp trong khi lại thừa khoảng trống chỗ khác (hiện tượng tụ đám của các khóa liên tiếp làm giảm hiệu quả của bảng kiểu địa chỉ mở được trình bày bên dưới). Việc phân phối cũng cần chú ý đến sự đồng bộ trong cơ cấu bảng, chẳng hạn với bảng cần kích thước là lũy thừa của 2 thì không phù hợp cho thuật toán băm chỉ băm đều khi cỡ bảng là số nguyên tố. Hàm băm mật mã là hàm băm tốt cho bảng băm tuy rằng phải trả giá về chi phí tính toán.

Tính đồng đều phân phối khóa đôi khi khó đảm bảo trong thiết kế nhưng có thể đánh giá hiệu quả sử dụng bằng kiểm tra thống kê, như kiểm định Chi-bình phương theo tiêu chuẩn phù hợp Pearson với giả thiết qui luật phân bố xác suất đồng đều rời rạc. Nội dung chi tiết kiểm định được trình bày bên dưới.

Hệ số tải (load factor)

Hệ số tải là tỉ số của số khóa chia cho số khe, n/k với n là số khóa còn k là số khe. Hệ số tải cần được giữ hợp lý, nếu quá lớn sẽ làm cho bảng băm trở nên chậm, điều quan trọng là cân đối giữa chất lượng của bảng với hiệu quả sử dụng tài nguyên, đó là không lãng phí bộ nhớ.

Các kiểu bảng băm thông dụng


Bảng băm với danh sách móc nối độc lập

450px-Hash_table_5_0_1_1_1_1_1_LL.svg

Bảng băm với danh sách độc lập

Nguồn ảnh: wikipedia.org

Mỗi một khe sẽ được gắn với một cấu trúc danh sách móc nối các bản ghi độc lập với mảng khe. Các chỉ số xung đột sẽ trở thành cùng một địa chỉ. Kỹ thuật này còn gọi là địa chỉ đóng(closed addressing), tức là địa chỉ không thay đổi. Một khi đạt được địa chỉ của khe, các hoạt động chèn, xóa và duyệt bản ghi được thực hiện trên con trỏ móc nối danh sách theo phương thức của cấu trúc danh sách thông thường, với khóa đích mong muốn. Thời lượng hoạt động bảng là thời gian tìm khe(là hằng số), cộng với thời gian cho danh sách hoạt động. Bảng băm kiểu này hoạt động trong điều kiện tốt là mỗi khe có nhiều cũng chỉ gồm hai, ba bản ghi.

Nếu phân phối khóa tương đối đồng đều, chi phí thời lượng trung bình cho tìm kiếm bản ghi chỉ phụ thuộc vào số khóa trung bình trên một khe, tức là hệ số tải. Nhược điểm của phương pháp danh sách móc nối độc lập là làm cho hoạt động cache kém hiệu quả(cache là lưu trữ một bản sao của dữ liệu được tham chiếu trong bộ nhớ lưu trữ đặc biệt, để mà tái truy cập nhanh hơn). Để khắc phục nhược điểm này, một cách thức cải tiến là đưa bản ghi đầu tiên của danh sách vào hẳn trong mảng khe thay cho con trỏ từ mảng như trước.

500px-Hash_table_5_0_1_1_1_1_0_LL.svg

Bảng băm với danh sách có bản ghi đầu tiên chứa trong mảng khe

Nguồn ảnh: wikipedia.org

Bảng băm địa chỉ mở

380px-Hash_table_5_0_1_1_1_1_0_SP.svg

Minh họa bảng băm địa chỉ mở với thăm dò tuyến tính(bước thăm dò =1). Đầu tiên “John Smith” được băm vào địa chỉ 152 vốn trước đó là trống. Tiếp theo “Sandra Dee” được băm, kết quả là xung đột ở địa chỉ 152, thăm dò phải di chuyển xuống dưới 1 đơn vị và dừng lại ở địa chỉ 153 còn trống. Sau đó “Ted Baker” được băm với kết quả 153, bản thân giá trị này không xung đột về băm nhưng phương pháp địa chỉ mở đã sắp xếp “Sandra Dee” ở đó, nên “Ted Baker” phải được đặt xuống dưới vào địa chỉ 154 còn trống.

Nguồn ảnh: wikipedia.org

Kiểu bảng này được gọi là bảng băm địa chỉ mở (Open addressing). Toàn bộ các bản ghi được chứa trong mảng khe. Khi một khóa mới được chèn, khóa sẽ được băm vào một khe. Nếu khe này là trống thì địa chỉ khe này sẽ là địa chỉ của khóa mới, nếu không, một chuỗi thăm dò tiến hành kiểm tra các khe cho tới khi một khe trống được tìm thấy, và địa chỉ cho khóa được xác định. Địa chỉ nhìn chung không được xác định bởi băm và có tính “mở” như vậy nên được gọi là địa chỉ mở. Đối với hoạt động tìm kiếm bản ghi, các khe cũng được quét theo trình tự tương tự, cho tới khi bản ghi mục tiêu được tìm thấy, hoặc tìm kiếm đi vào một khe trống, cho biết rằng không có khóa như thế trong bảng. Có 3 loại thăm dò

  • Thăm dò tuyến tính: bước thăm dò là cố định, thường là 1, mỗi lần di chuyển qua một khe

  • Thăm dò bậc hai: bước thăm dò tăng dần bằng cách cộng kết quả kế tiếp của một đa thức bậc hai vào giá trị ban đầu được đưa ra bởi tính toán băm gốc.

  • Băm kép: bước thăm dò được tính toán bằng một hàm băm khác.

Với cách thiết lập bảng như vậy đương nhiên số khóa không thể vượt quá số khe. Thực tế, dù với hàm băm tốt, hoạt động bảng bắt đầu suy thoái khi hệ số tải mọc lên trên 0.7. Điều này có thể được khắc phục bằng cách định lại kích cỡ bảng động, với một cái giá phải trả về chi phí thực hiện.

Phương án địa chỉ mở cũng đưa ra yêu cầu nghiêm ngặt hơn về hàm băm: ngoài việc phân phối các khóa đồng đều hơn trong mảng khe, còn phải có chức năng giảm thiểu hiện tượng tụ đám các giá trị băm liên tiếp theo thứ tự dò, bởi vì nếu điều này xảy ra thì một khóa khác nào đó phải đi qua cả đám lớn đó mới tìm được chỗ trống. So sánh ở khía cạnh này, đối với bảng kiểu danh sách móc nối, mối quan tâm duy nhất chỉ là đừng có để quá nhiều đối tượng băm vào cùng một khe, còn vấn đề chúng có liền kề hay gần đó hay không là hoàn toàn không liên quan.

Phương pháp địa chỉ mở phù hợp cho bảng có cỡ bản ghi nhỏ, vì như thế sẽ bớt lãng phí bộ nhớ do luôn phải duy trì hệ số tải thấp với nhiều bản ghi trống. Trong điều kiện như vậy thì ưu điểm về cache dữ liệu được phát huy, do toàn bộ các bản ghi đều nằm trong mảng khe. Ngược lại, nếu bảng cần phải có hệ số tải cao, bản ghi lớn, hay yêu cầu dữ liệu với kích cỡ thay đổi được thì sử dụng bảng kiểu danh sách móc nối là tốt hơn.

Bảng băm kiểu chim Cúc cu

Kiểu bảng này là một biến thể của giải pháp địa chỉ mở. Trong trường hợp xấu nhất, thời gian tra cứu là hằng số. Hằng số này được hình thành bởi tích lũy dần trong quá trình tạo lập bảng, gây ra bởi các chuỗi hoạt động chèn và xóa các bản ghi như mô tả chi tiết dưới đây. Bảng duy trì hai hay nhiều hàm băm. Để dò tìm một bản ghi, hàm băm thứ nhất được sử dụng. Nếu khóa không được tìm thấy, hàm băm thứ hai được sử dụng, và cứ thế. Khi chèn vào một bản ghi, hàm băm thứ nhất được sử dụng, nếu khóa được băm vào một khe trống, bản ghi mới này coi như tạm thời nằm ở đó. Nếu khóa được băm vào một khe đã được chiếm chỗ bởi một bản ghi khác trước đó, nghĩa là có xung đột xảy ra, thì hàm băm thứ hai được sử dụng để ánh xạ nó tới một khe khác. Nếu tất cả các hàm băm đã được sử dụng cho tới hàm băm cuối cùng mà xung đột vẫn còn xảy ra, thì khóa xung đột trong chặng cuối này sẽ bị di chuyển để nhường chỗ cho khóa mới. Chúng ta nhớ rằng tại thời điểm này khóa mới đã sử dụng hết hàm băm. Nhưng điều này có thể là khác đối với khóa cũ bị di chuyển và khóa này có thể có cơ hội tìm được một chỗ trống, nhưng bản thân nó không nhận thức được điều này và nó đơn giản lần lượt sử dụng các hàm băm bắt đầu từ hàm băm thứ nhất, ngoại trừ hàm băm mà đưa nó tới vị trí hiện tại đang xung đột thì được tính là sử dụng rồi, để tìm chỗ trú chân khác. Nếu xung đột lại tiếp tục xảy ra thì các chuỗi xử lý cứ như thế tiếp tục lặp lại cho tới khi không còn xung đột. Chúng ta hình dung là các bản ghi bị di chuyển (bị xóa và chuyển đi chỗ khác) theo dây chuyền. Các chuỗi quá trình này có xu hướng dồn các bản ghi vào chỗ trống. Thử tưởng tượng một viễn cảnh tồi tệ, đó là một vòng lặp luẩn quẩn xảy ra, một số khóa cứ quay đi quay lại vị trí cũ. Đó là có một số khóa đồng thời bị chập trên tất cả các hàm băm, và số khóa này lớn hơn số hàm băm, cho dù giả sử mỗi hàm băm đảm bảo băm một khóa nhất định vào các vị trí khác nhau, như thế cũng không đủ chỗ cho số khóa như vậy, và quá trình cứ trao đi đổi lại vị trí với vòng lặp vô tận. Tuy nhiên chúng ta biết rằng với vấn đề Sinh nhật, hai giá trị băm ngẫu nhiên xung đột thì dễ nhưng để một giá trị băm thứ ba cũng xung đột vào giá trị băm ấy lúc này đã được coi là xác định, là vấn đề Sinh nhật “Cùng ngày sinh như bạn”, có xác suất nhỏ đáng kể. Thế thì sự xung đột đồng thời trên tất cả các hàm băm của toàn bộ số khóa này là một biến cố hầu như không xảy ra. Với số hàm băm đủ lớn, sẽ không có vấn đề, nghĩa là các khóa sẽ tìm chỗ trú và sử dụng tất cả các khe của bảng. Lúc này nếu còn nhu cầu thêm khóa mới, bảng sẽ được thay đổi kích cỡ, thiết lập lại. Kiểu bảng này tận dụng không gian bảng tối ưu. Tình huống xấu nhất về thời gian tra cứu một bản ghi là để tìm được bản ghi này, sự tra cứu phải đi qua tất cả các hàm băm, đây là thời gian hằng số đối với tất cả các trường hợp như vậy vì tống số hàm băm là không đổi.

 

Kiểm định thống kê bảng băm


Chúng ta mong muốn bảng băm được phân phối đều các khóa. Cho nên sử dụng kiểm định Chi-bình phương theo tiêu chuẩn phù hợp Pearson với giả thiết qui luật phân bố xác suất đồng đều rời rạc.

Vì bảng băm tốt chỉ có tối đa 3 khóa trên một khe mà tiêu chuẩn phù hợp Pearson yêu cầu tần số quan sát 5 nên chúng ta nhóm mỗi 5 khe thành một khoảng. Để đơn giản cho ví dụ, chúng ta xem xét một bảng nhỏ có 80 khóa, 40 khe, như vậy hệ số tải là 80/40=2. Bảng có kiểu danh sách móc nối. Chia không gian bảng thành 8 khoảng, mỗi khoảng trung bình 10 khóa.

Giả thiết: bảng phân bố theo qui luật đồng đều rời rạc

Kích thước mẫu (cũng là kích thước tổng thể của bảng): N=80

Số ô(số khoảng, số giá trị rời rạc): n=8

Xác suất đồng đều rời rạc: p= 1/n= 1/8

Tần số lý thuyết(bằng nhau với mọi i thuộc [1,n]): Ei= N*p= 80*1/8= 10

Mức ý nghĩa: α = 0.01

Số bậc tự do: n-1= 8-1= 7

Giá trị thống kê kiểm định là

statistic

χ² = thống kê kiểm định, một thống kê tiệm cận phân bố Chi-bình phương

Oi = tấn số quan sát thứ i

Bằng cách truy cập mảng kết hợp theo chỉ số, từ đó đếm số phần từ trong danh sách móc nối của mỗi khe, chúng ta có số khóa của khe tương ứng. Cộng số khóa của 5 khe trong mỗi khoảng thành số khóa của ô đó. Cho rằng số khóa quan sát trong mỗi ô từ ô thứ nhất đến ô thứ 8 lần lượt là 6, 20, 8, 6, 7, 15, 10, 8. Chúng ta lập bảng tính toán sau

i Oi Ei Oi-Ei (Oi-Ei)² (Oi-Ei)²/Ei
1 6 10 -4 16 1.6
2 20 10 10 100 10
3 8 10 -2 4 0.4
4 6 10 -4 16 1.6
5 7 10 -3 9 0.9
6 15 10 5 25 2.5
7 10 10 0 0 0
8 8 10 -2 4 0.4
Tổng 17.4

Với số bậc tự do là 7, tra trong bảng giá trị tới hạn của phân bố Chi-bình phương với mức ý nghĩa α=0.01 chúng ta được giá trị tới hạn là 18.475 > 17.4 . Vậy bảng băm trên được chấp nhận theo giả thiết với mức ý nghĩa α=0.01, có phân bố khóa đồng đều rời rạc.

Advertisements

Gửi phản hồi

Website này sử dụng Akismet để hạn chế spam. Tìm hiểu bình luận của bạn được duyệt như thế nào.

%d bloggers like this: