TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - TS. Trần Ngọc Việt

Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm được biên soạn gồm các nội dung chính sau: giới thiệu bảng băm; hàm băm; xung đột và bài tập. Mời các bạn cùng tham khảo! | GIỚI THIỆU Tổ chức lưu trữ thông tin 100 nhân viên của một công ty ABC mỗi nhân viên có mã số riêng EMP_ID trong phạm vi 0 99 Ta có thể dùng mảng để lưu trữ với EMP_ID là chỉ mục tương ứng trong mảng. Dữ liệu An Bình Minh Ngọc EMP_ID 0 1 2 99 3 KHOA CÔNG NGHỆ THÔNG TIN GIỚI THIỆU Tổ chức lưu trữ thông tin 100 nhân viên của một công ty ABC mỗi nhân viên có mã số riêng EMP_ID trong phạm vi 00000 99999 Ta cần một mảng có 100 000 phần tử để lưu trữ với EMP_ID là chỉ mục tương ứng trong mảng. Dữ liệu An Bình Minh Ngọc EMP_ID 00000 00001 00002 99 99999 Tốn nhiều không gian lưu trữ 4 KHOA CÔNG NGHỆ THÔNG TIN GIỚI THIỆU Cần giải pháp khác để lưu trữ 100 nhân viên với EMP_ID có phạm vi 00000 99999 Cần có hàm chuyển EMP_ID có 5 số về EMP_ID có 2 số hàm băm Cần có mảng ánh xạ mỗi khóa EMP_ID 5 số tới vị trí trong mảng EMP_ID 2 số. Bảng băm 5 KHOA CÔNG NGHỆ THÔNG TIN BẢNG BĂM Bảng băm là một cấu trúc dữ liệu mà các khóa được ánh xạ đến các vị trí trong mảng thông qua một hàm băm. Trong bảng băm một phần tử có khóa k được lưu tại chỉ mục có hàm băm h k chứ không phải vị trí k. Quá trình ánh xạ các khóa vào vị trí phù hợp trong bảng băm gọi là hashing. Khi hai khóa có cùng vị trí trong bảng băm gọi là xung đột collision 6 KHOA CÔNG NGHỆ THÔNG TIN BẢNG BĂM Bảng băm là một cấu trúc dữ liệu mà các khóa được ánh xạ đến các vị trí trong mảng thông qua một hàm băm. 7 KHOA CÔNG NGHỆ THÔNG TIN HÀM BĂM Hàm băm là một công thức toán học khi áp dụng ánh xạ cho khóa k sẽ tạo ra một số nguyên dùng làm chỉ mục trong bảng băm. Một hàm băm thỏa mãn các điều kiện sau 1. Tính toán nhanh 2. Các khóa được phân bố đều trong bảng 3. Ít xảy ra xung đột 4. Xử lý các loại khóa có kiểu dữ liệu khác nhau 8 KHOA CÔNG NGHỆ THÔNG TIN CÁC PHƯƠNG PHÁP TẠO HÀM BĂM 1. Phương pháp chia h x x M Ví dụ 1 tính giá trị băm cho các khóa 1234 5462 2362 M 10 chọn số chẵn kích thước bảng h 1234 1234 10 4 h 5462 5462 10 2 Xung đột h 2362 2362 10 2 9 KHOA CÔNG NGHỆ THÔNG TIN CÁC PHƯƠNG PHÁP TẠO HÀM BĂM 1. Phương pháp chia

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bảng băm
• Phương pháp tạo hàm băm
• Kỹ thuật dò tuyến tính
• 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
• 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
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• 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