Ctdl: Bảng Băm Là Gì – Chi Tiết Bài Học Bảng Bă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.

Đang xem: Bảng băm là gì

Bạn đang xem: Bảng băm là gìBạn đang xem: Bảng băm là gìBạn đang xem: Bảng băm là gì

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

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.

Xem thêm: Thẻ Vietcombank Chuyển Khoản Được Cho Những Ngân Hàng Nào ? Vietcombank Chuyển Khoản Được Cho Ngân Hàng Nào

Hệ số tải (load factor)

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

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

Nguồn ảnh: wikipedia.org

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.

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ở

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ò

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

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.