tailieunhanh - Bài giảng Cở sở dữ liệu 2: Chương 2 - Trương Hải Bằng

Chương 2 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. Chương này cũng 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. Mời các banjc ùng tham khảo để nắm bắt các nội dung chi tiết. | Trương Hải Bằng - Cấu trúc dữ liệu 2 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 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 đổi khoá thành số nguyên E Ví dụ loại bỏ dấu - trong mã số 9635-8904 đưa về số nguyên 96358904 Chương 2 Bảng băm Trang 1 Trương Hải Bằng - Cấu trúc dữ liệu 2 E Đối với chuỗi sử dụng