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ố)?
Nội dung trích xuất từ tài liệu:
Chapter 5: Bảng băm (Hash Table) Chương 5 Bảng băm Bả Bảng băm (Hash Table) Bảng Các thuật toán tìm kiếm đều dựa vào việc Nội dung Nội so sánh giá trị khoá (Key) Phụ thuộc kích thước của tập các phần tử 1 Bảng băm 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), 2 Định nghĩa hàm băm O(logn), …) 3 Phương pháp xây dựng hàm băm => 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 4 Phương pháp giải quyết đụng độ không ( độ phức tạp hằng số)? 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Bảng truy xuất trực tiếp Bảng xuấ trự tiế Cấu trúc bảng băm trúc bả Bảng gồm m phần tử được K: tập các giá trị khoá (set lưu trữ dưới dạng bảng chỉ of keys) cần lưu trữ mục A: tập các địa chỉ (set of addresses) trong bảng băm Phần tử có giá trị khoá k được lưu trữ tương ứng tại vị HF(k): hàm băm dùng để trí thứ k ánh xạ một khoá k từ tập các khoá K thành một địa Tìm kiếm bằng cách tra trong chỉ tương ứng trong tập bảng chỉ mục các địa chỉ A Thời gian tìm kiếm là O(1) Đây là dạng bảng băm cơ bản 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Hàm băm (Hash function) Hàm Phân loại bảng băm loạ bả Là hàm biến đổi giá trị khoá (số, chuỗi…) thành địa chỉ, chỉ mục Bảng băm đóng : trong bảng băm Số phần tử cố định Giá trị khoá Hàm băm Địa chỉ, chỉ mục 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 Ví dụ : hàm băm biến đổi khóa chuỗi thành 1 địa chỉ (số nguyên) thời gian truy xuất là hằng số int hashfunc( char *s, int n ) Bảng băm mở : { int sum = 0; while( n-- ) sum = sum + *s++; Số phần tử không cố định return sum % 256; 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ử Tính địa chỉ của khoá “AB” : hashfunc(“AB”,2) 131 Thời gian truy xuất có thể bị suy giảm đôi chút 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 độ (Collision) 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 5 Bảng băm Bả Chương 5 Bảng băm Bả Hàm băm (Hash function) Hàm ...