tailieunhanh - Cấu trúc dữ liệu và giải thuật II - Chương 2

BẢNG BĂM (HASH TABLE) Phép băm được đề xuất và hiện thực trên máy tính từ những năm 50 của thế kỷ 20. Nó dựa trên ý tưởng: chuyển đổi khóa thành một số (xử lý băm) và sử dụng số này để đánh chỉ số cho bảng dữ liệu. Các phép toán trên các cấu trúc dữ liệu như danh sách, cây nhị phân, phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Chương này sẽ. | CHƯƠNG 2 - BẢNG BĂM HASH TABLE Phép băm được đề xuất và hiện thực trên máy tính từ những năm 50 của thế kỷ 20. Nó dựa trên ý tưởng chuyển đổi khóa thành một số xử lý băm và sử dụng số này để đánh chỉ số cho bảng dữ liệu. Các phép toán trên các cấu trúc dữ liệu như danh sách cây nhị phân . phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Chương này sẽ khảo sát một cấu trúc dữ liệu mới được gọi là bảng băm hash table . Các phép toán trên bảng băm sẽ giúp hạn chế số lần so sánh và vì vậy sẽ cố gắng giảm thiểu được thời gian truy xuất. Độ phức tạp của các phép toán trên bảng băm thường có bậc là 0 1 và không phụ thuộc vào kích thước của bảng băm. Chương này sẽ giới thiệu các chủ đề và các phép toán chính thường dùng trên cấu trúc bảng băm Phép băm hay hàm băm hash function Tập khoá của các phần tử trên bảng băm Tập địa chỉ trên bảng băm Phép toán thêm phần tử vào bảng băm Phép toán xoá một phần tử trên bảng băm Phép toán tìm kiếm trên bảng băm Thông thường bảng băm được sử dụng khi cần giải quyết những bài toán có các cấu trúc dữ liệu lớn và được lưu trữ ở bộ nhớ ngoài. 1. PHÉP BĂM Hash Function Định nghĩa Trong hầu hết các ứng dụng khoá được dùng như một phương thức để truy xuất dữ liệu một cách gián tiếp. Hàm được dùng để ánh xạ một khoá vào một dãy các số nguyên và dùng các giá trị nguyên này để truy xuất dữ liệu được gọi là hàm băm hình 1 K ---------M h ------------------ h K Hình 1 Như vậy hàm băm là hàm biến đổi khóa của phần tử thành địa chỉ trên bảng băm. Khóa có thể là dạng số hay số dạng chuỗi. Hàm băm tốt thỏa mãn các điều kiện sau o Tính toán nhanh. o Các khoá được phân bố đều trong bảng. o Ít xảy ra đụng độ. Giải quyết vấn đề băm với các khoá không phải là số nguyên o Tìm cách biến đổ khoá thành số nguyên Ví dụ loại bỏ dấu - trong mã số 9635-8904 đưa về số nguyên 96358904 Đối với chuỗi sử dụng giá trị các ký tự trong bảng mã ASCCI o Sau đó sử dụng các hàm băm