Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 12: Bảng và truy xuất thông tin

trúc dữ liệu và Giải thuật 333
danh sách), số phần tử được mong đợi trong danh sách đang được tìm kiếm là λ = 
n/t. Do đó số lần thử trung bình của một lần tìm kiếm không thành công là λ. 
Bây giờ chúng ta hãy giả sử là việc tìm kiếm sẽ thành sông. Từ phân tích của 
việc tìm tuần tự, chúng ta đã biết rằng số lần so sánh trung bình là 
2
1 (k+1), với 
k là chiều dài của danh sách chứa phần tử cần tìm. Nhưng chiều dài mong đợi của 
danh sách này không lớn hơn λ, và chúng ta biết trước là nó chứa ít nhất một 
phần tử (phần tử cần tìm). Ngoại trừ phần tử cần tìm, n –1 phần tử còn lại được 
phân phối như nhau trên tất cả t danh sách; vậy số phần tử mong đợi trên danh 
sách có chứa phần tử cần tìm là 1+(n-1)/t. Không kể các bảng có kích thước 
nhỏ, chúng ta lấy xấp xỉ (n-1)/t bằng n/t=λ. Vậy số lần thử trung bình cho 
một lần tìm kiếm thành công gần với 
2
1 (k+1) ≈ 
2
1 (1 + λ + 1) = 1 + 
2
1 λ. 
Tóm lại, việc truy xuất một bảng băm nối kết có hệ số tải λ trung bình cần 
đến 1 + 
2
1 λ lần thử cho một lần tìm kiếm thành công và λ lần thử cho một lần 
tìm kiếm không thành công. 
12.6.4. Phân tích phương pháp địa chỉ mở 
Để phân tích số lần thử trong bảng băm địa chỉ mở, trước hết chúng ta bỏ qua 
vấn đề gom tụ với giả thiết rằng không chỉ lần thử đầu tiên là ngẫu nhiên mà 
ngay cả sau khi xảy ra đụng độ, lần thử kế tiếp cũng ngẫu nhiên trên khắp các vị 
trí còn lại của bảng. Nói cách khác, giả sử rằng bảng băm có kích thước rất lớn 
sao cho mọi lần thử có thể được xem là độc lập nhau. Kết quả tính được như sau: 
Việc truy xuất từ bảng băm địa chỉ mở, với phép thử ngẫu nhiên và hệ số tải 
λ, có số lần thử trung bình xấp xỉ bằng 
 1 1 
 ⎯ ln ⎯⎯ 
 λ 1 - λ 
trong trường hợp tìm kiếm thành công và 1/(1-λ) trong trường hợp tìm kiếm 
không thành công. 
Trong trường hợp bảng băm địa chỉ mở với phép thử tuyến tính, lưu ý rằng giả 
thiết các lần thử độc lập nhau là không thể chấp nhận. Kết quả tính được như 
sau: 
Việc truy xuất bảng băm địa chỉ mở với phép thử tuyến tính và hệ số tải λ 
cần số lần thử trung bình xấp xỉ bằng 
Chương 12 – Bảng và truy xuất thông tin 
Giáo trình Cấu trúc dữ liệu và Giải thuật 334
 1 1 
 ⎯ 1 + ⎯⎯ 
 2 1 - λ 
trong trường hợp thành công và 
 1 1 
 ⎯ 1 + ⎯⎯⎯ 
 2 (1 - λ)2 
trong trường hợp không thành công. 
12.6.5. Các so sánh lý thuyết 
Hình 12.13 cho thấy các giá trị của các biểu thức trên với các trị khác nhau 
của hệ số tải λ. 
Chúng ta có thể thấy được một vài kết luận từ bảng này. Trước hết, rõ ràng là 
bảng băm nối kết cần ít lần thử hơn bảng băm địa chỉ mở. Mặt khác, việc duyệt 
các danh sách liên kết thường chậm hơn là truy xuất mảng, điều này làm giảm ưu 
điểm của bảng băm nối kết, nhất là trong những trường hợp mà việc so sánh 
khóa có thể được thực hiện rất nhanh. Phương pháp nối kết trở nên hợp lý khi 
các phần tử có kích thước lớn và thời gian cần để so sánh các khóa là nhiều. 
Ngoài ra, nó còn tỏ ra có lợi thế khi việc tìm kiếm không thành công thường xảy 
ra, do những lúc quá trình tìm kiếm gặp được một danh sách rỗng hoặc một danh 
sách thật ngắn và có thể kết thúc nhanh với rất ít lần so sánh khóa. 
Đối với việc tìm kiếm thành công trong bảng băm địa chỉ mở, phương pháp 
thử tuyến tính đơn giản không làm chậm quá trình tìm kiếm đi nhiều so với các 
phương pháp giải quyết đụng độ phức tạp khác, ít nhất là cho đến khi bảng gần 
Hình 12.13 – So sánh lý thuyết các phương pháp băm
Chương 12 – Bảng và truy xuất thông tin 
Giáo trình Cấu trúc dữ liệu và Giải thuật 335
như đầy. Tuy nhiên, đối với việc tìm kiếm không thành công, hiện tượng gom tụ 
nhanh chóng làm cho phép thử tuyến tính suy thoái thành quá trình tìm kiếm 
tuần tự. Vì thế, chúng ta có thể kết luận rằng nếu việc tìm kiếm thường thành 
công, và hệ số tải vừa phải, thì phép thử tuyến tính sẽ đáp ứng được; còn trong 
những trường hợp khác, nên sử dụng những phương pháp giải quyết đụng độ khác 
như phương pháp thử bậc hai chẳng hạn. 
12.6.6. Các so sánh thực nghiệm 
Một điều quan trọng cần nhớ là các tính toán trong hình 12.13 chỉ là các con 
số xấp xỉ, và trong thực tế không có gì là hoàn toàn ngẫu nhiên, do đó chúng ta 
luôn biết rằng sẽ có một vài điều khác nhau giữa các kết quả lý thuyết và việc 
tính toán thực sự. Vì vậy, để so sánh, hình 12.14 cho thấy kết quả của việc 
nghiên cứu bằng thực nghiệm với 900 khóa lấy ngẫu nhiên giữa 0 và 1. 
Nếu so sánh các con số trong hai bảng 12.15 và 12.16, chúng ta thấy rằng kết 
quả thực nghiệm trên bảng băm nối kết gần giống với kết quả lý thuyết. Các kết 
quả của phép thử bậc hai lại gần giống với kết quả lý thuyết của việc thử ngẫu 
nhiên; sự khác nhau có thể được giải thích dễ dàng là vì thử bậc hai chưa thật sự 
ngẫu nhiên. Đối với thử tuyến tính, các kết quả tương tự khi bảng còn tương đối 
trống, nhưng khi bảng gần như đầy thì các con số xấp xỉ được tính bằng lý thuyết 
khác nhiều so với thực nghiệm. Đó là hậu quả của các giả thiết đã được đơn giản 
hóa trong toán học. 
So sánh với các phương pháp truy xuất thông tin khác, điều quan trọng cần lưu 
ý về tất cả những con số này là chúng chỉ phụ thuộc vào hệ số tải, mà không phụ 
thuộc vào số phần tử thực sự có trong bảng. Việc truy xuất từ bảng băm có 20,000 
phần tử trong 40,000 vị trí có thể có của bảng, xét trung bình, không chậm hơn 
Hình 12.14 – So sánh thực nghiệm các phương pháp băm. 
Chương 12 – Bảng và truy xuất thông tin 
Giáo trình Cấu trúc dữ liệu và Giải thuật 336
việc tìm kiếm trong 20 phần tử trong 40 vị trí có thể có. Với việc tìm tuần tự, một 
danh sách có kích thước lớn gấp 1000 lần sẽ làm cho quá trình tìm lâu hơn 1000 
lần. Với tìm kiếm nhị phân, tỉ lệ này giảm xuống 10 (chính xác hơn là lg1000), 
nhưng thời gian tìm kiếm vẫn luôn phụ thuộc vào kích thước của danh sách, điều 
này không có ở bảng băm. 
Chúng ta có thể tổng kết những khảo sát về việc truy xuất từ n phần tử như 
sau: 
• Tìm tuần tự là θ(n). 
• Tìm nhị phân là θ(log n). 
• Truy xuất bảng băm là θ(1). 
Cuối cùng, chúng ta nhấn mạnh về tầm quan trọng của việc lựa chọn một hàm 
băm tốt, một hàm băm thực hiện tính toán nhanh và rải đều các khóa trong 
bảng. Nếu hàm băm không tốt thì băm sẽ suy thoái về tìm kiếm tuần tự. 
12.7. Kết luận: so sánh các phương pháp 
Trong chương này và chương 7, chúng ta đã xem xét bốn phương pháp khác 
nhau để truy xuất thông tin: 
• Tìm tuần tự, 
• Tìm nhị phân, 
• Tra cứu bảng, và 
• Băm. 
Nếu được hỏi rằng phương pháp nào là tốt nhất, trước hết chúng ta cần chọn 
ra các tiêu chí để đánh giá. Các tiêu chí gồm các yêu cầu của ứng dụng, và các mối 
quan tâm khác có ảnh hưởng lên sự chọn lựa cấu trúc dữ liệu, do hai phương pháp 
đầu chỉ có thể áp dụng với các danh sách còn hai phương pháp sau chỉ dành cho 
các bảng. Trong nhiều ứng dụng, chúng ta cũng được tự do trong việc chọn lựa 
giữa danh sách và bảng. 
Về mặt tốc độ cũng như tính thuận lợi, việc tra cứu theo thứ tự trong các bảng 
chắc chắn là tốt nhất, nhưng có nhiều ứng dụng mà điều này lại không áp dụng 
được do tập các khóa khá thưa thớt hoặc đối với chúng danh sách tỏ ra ưu thế 
hơn. Một điều không thích ứng nữa là khi việc thêm và loại phần tử xảy ra 
thường xuyên, trong vùng nhớ liên tục các tác vụ này đòi hỏi phải di chuyển một 
số lớn dữ liệu. 
Trong ba phương pháp còn lại, phương pháp nào là tốt nhất phụ thuộc vào tiêu 
chí khác như dạng của dữ liệu. 
Chương 12 – Bảng và truy xuất thông tin 
Giáo trình Cấu trúc dữ liệu và Giải thuật 337
Tìm tuần tự là phương pháp mềm dẻo nhất trong các phương pháp. Dữ liệu có 
thể được lưu theo bất kỳ thứ tự nào, trong hiện thực liên tục hoặc liên kết. Tìm 
nhị phân đòi hỏi nhiều hơn, các khóa phải lưu theo thứ tự và dữ liệu phải lưu 
trong vùng nhớ cho phép truy xuất ngẫu nhiên (vùng nhớ liên tục). Băm còn đòi 
hỏi nhiều hơn nữa, tuy thứ tự khác thường của các khóa vẫn đáp ứng được việc 
truy xuất từ bảng băm, nhưng nói chung nó không có lợi cho bất kỳ một mục đích 
nào khác. Nếu như dữ liệu cần phải luôn sẵn sàng cho một sự khảo sát thì một 
thứ tự nào đó là cần thiết, và như vậy bảng băm không đáp ứng. 
Cuối cùng là vấn đề liên quan đến việc tìm kiếm không thành công. Tìm tuần 
tự và băm khi không thành công thì xem như không có kết quả gì. Trong khi đó, 
nếu thất bại thì tìm nhị phân sẽ cho biết dữ liệu có khóa gần với khóa cần tìm, 
và như vậy nó có thể cung cấp thông tin hữu ích. Trong chương 9 và 10 chúng ta 
đã nghiên cứu các phương pháp lưu trữ dữ liệu dựa trên cơ sở cây, có kết hợp tính 
hiệu quả của tìm nhị phân với sự mềm dẻo của các cấu trúc liên kết. 
Chương 12 – Bảng và truy xuất thông tin 
Giáo trình Cấu trúc dữ liệu và Giải thuật 338