TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 14: Bảng băm

Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 14: Bảng băm" cung cấp cho người học các kiến thức: Hàm băm, một số phương pháp xây dựng hàm băm, bảng băm - Hash table. Cuối phần bài giảng có phần bài tập để người học ôn tập và củng cố kiến thức. | 3. Tìm kiếm theo địa chỉ Bảng băm - Hash Tables 0 1 025-612-0001 2 981-101-0002 3 4 451-229-0004 2004 Goodrich Tamassia I. Hàm băm Cấu trúc hàm băm Hàm băm có dạng như sau h K 0 h K x y 1 2 Trong đó 3 z - h được gọi là hàm băm hash function m-1 - K là tập giá trị khóa - là bảng địa chỉ là các số nguyên - m là kích thước của bảng Yêu cầu khi xây dựng hàm băm Hàm phải dải đều các địa chỉ trên bảng địa chỉ Hàm băm phải được tính toán đơn giản. 2 Hình ảnh hàm băm 0 h k1 1 h k3 K h k k1 h k2 k3 k2 N-1 3 Hàm băm Các đối tượng Hàm băm Bảng địa 012 N-1 chỉ Một hàm băm ánh xạ các đối tượng vào tập các địa chỉ 0 N-1 4 II. Một số phương pháp xây dựng hàm băm 1. Phương pháp chia Để tính địa chỉ dải của đối tượng ta lấy giá trị khóa chia cho kích thước của bảng. Địa chỉ dải là phần dư của phép chia đó. h k k m Yêu cầu Hàm h phải dải đều các đối tượng trên bảng một cách ngẫu nhiên. Để có được điều đó h phải phụ thuộc vào m. Phụ thuộc vào m Thông thường người ta chọn m là một số nguyên tố nhỏ hơn gần với 10 100 1000 . nhất. 5 2. Phương pháp nhân Giá trị khóa được nhân với chính nó sau đó lấy con số bao gồm một số chữ số ở giữa kết quả để làm địa chỉ rải . Ví dụ k k2 h k gồm 3 chữ số 5402 29181604 181 hoặc 816 0367 00134689 134 hoặc 346 1246 01552516 552 hoặc 525 Rõ ràng các chữ số ở giữa phụ thuộc vào mọi chữ số của khóa do đó nếu khóa có khác nhau chút ít thì địa chỉ dải vẫn khác nhau nhiều. 6 3. Phương pháp phân đoạn Giá trị khóa được phân ra thành nhiều đoạn bằng nhau Người ta sử dụng hai kỹ thuật phân đoạn sau đây Tách Tách các đoạn ra và mỗi đoạn được xếp thành một hàng dóng lề trái hoặc lề phải. Gấp Gấp các đoạn lại theo đường biên tương tự như gấp giấy các chữ rơi vào cùng một chỗ được đặt thành hàng thẳng nhau. 7 Ví dụ Tách giả sử có khóa là k 17046329 329 046 017 392 Gấp 046 923 710 Chọn 167 1679 hoặc 679 8 III. Bảng băm - Hash table Một bảng băm là một cấu trúc dựa trên mảng để lưu trữ các phần tử mỗi phần tử là một cặp Khóa-Giá trị key-value Các thành phần

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Lập trình C++
• Kỹ thuật lập trình
• Ngôn ngữ lập trình
• Bảng băm
• Hash table
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cơ sở dữ liệu
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Kiểu dữ liệu cây
• Phân loại cây
• Bài giảng Maple
• Cấu trúc dữ liệu trong maple
• Cấu trúc dữ liệu dãy
• Cấu trúc dữ liệu tập hợp
• Cấu trúc dữ liệu mảng
• Cấu trúc dữ liệu bảng
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Cấu trúc chương trình
• Cấu trúc điều khiển
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Cấu trúc dữ liệu cây AA
• Cây AA
• Biến đổi hiệu chỉnh cây AA
• Danh sách liên kết
• Thao tác duyệt cây
• Cấu trúc dữ liệu ngăn xếp
• Hàng đợi
• Biểu thức toán học
• Cây nhị phân
• Cấu trúc dữ liệu nâng cao
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu tuyến tính
• Cách dùng con trỏ
• Cài đặt danh sách
• Các kiểu dữ liệu cơ bản
• Giải thuật tìm tuyến tính