tailieunhanh - Chapter 5: Bảng băm (Hash Table)

Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá (Key). Phụ thuộc kích thước của tập các phần tử Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết ( O(n), O(logn), ) = Có phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cao hơn không ( độ phức tạp hằng số)? | Chương 5 Bàng băm Bảng truy xuất trực tiếp Bảng gồm m phần tử được lưu trữ dưới dạng bảng chỉ mục Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị trí thứ k Tìm kiếm bằng cách tra trong bảng chỉ mục Thời gian tìm kiếm là 0 1 Đây là dạng bảng băm cơ bản direct access table cc I led Ic n Chương 5 Bảng băm Bảng băm Hash Table Các thuật toán tìm kiếm đều dựa vào việc so sánh giá trị khoá Key Phụ thuộc kích thước của tập các phần tử Thời gian tìm kiếm không nhanh do phải thực hiện nhiều phép so sánh có thể không cần thiết O n O logri . CÓ phương pháp lưu trữ nào cho phép thực hiện tìm kiếm với hiệu suất cào hơn không độ phức tạp hằng số Chương 5 Bảng băm cấu trúc bảng băm K tập các giá trị khoá set of keys cần lưu trữ A tập các địa chỉ set of addresses trong bảng băm HF k hàm băm dùng để ánh xạ một khoá k từ tập các khoá K thành một địa chỉ tương ứng trong tập các địa chỉ A Táp khóa K TảpđịachỉA Hinh Chương 5 Bảng băm Chương 5 Bàng băm Phân loại bảng băm Hàm băm Hash function Bảng băm đóng Số phần tử cố định Mỗi khóa ứng với một địa chỉ Không thể thực hiện các thao tác thêm xóa trên bảng băm thời gian truy xuất là hằng số Bảng băm mở Số phần tử không cố định Một số khóa có thể có cùng địa chỉ Có thể thực hiện các thao tác thêm xóa phần tử Thời gian truy xuất có thể bị suy giảm đôi chút Là hàm biến đổi giá trị khoá số chuỗi. thành địa chỉ chỉ mục trong bảng băm Giá trị khoá Hàm băm Địa chỉ chỉ mục Ví dụ hàm băm biến đổi khóa chuỗi thành 1 địa chỉ số nguyên int hashfunc char s int n int sum 0 while n-- sum sum s return sum 256 Tính địa chỉ của khoá AB hashfunc AB 2 131 Tính địa chỉ của khoá BA hashfunc BA 2 131 Khi hàm băm 2 khoá vào cùng 1 địa chỉ gọi là đụng độ Chương 5 Bàng băm Hàm băm Hash function Chương 5 Bảng băm Phương pháp xây dựng hàm băm Tiêu chuẩn đánh giá hàm băm Tính toán nhanh. Các khoá được phân bố đều trong bảng. Ít xảy ra đụng độ . Hàm băm dạng bảng tra Hàm băm dùng phương pháp chia Hàm băm dùng phương pháp nhân Chương 5 Bảng băm Hàm băm dạng