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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Bảng băm" cung cấp cho người đọc các kiến thức khái quát về băm, hàm băm, sự đụng độ, các phương pháp giải quyết đụng độ, tổng kết. | Giảng viên Văn Chí Nam Nguyễn Thị Hồng Nhung Đặng Nguyễn Đức Tiến 2 Khái quát về băm Hàm băm Sự đụng độ Các phương pháp giải quyết đụng độ Kết luận Cấu trúc dữ liệu và giải thuật HCMUS 2015 https tailieudientucntt FIT-HCMUS 1 3 Hash Table Cấu trúc dữ liệu và giải thuật HCMUS 2015 4 Vấn đề Cho trước 1 tập S gồm các phần tử được đặc trưng bởi giá trị khóa. Trên giá trị các khóa này có quan hệ thứ tự. Tổ chức S như thế nào để tìm kiếm 1 phần tử có khóa k cho trước có độ phức tạp ít nhất trong giới hạn bộ nhớ cho phép Ý tưởng Biến đổi khóa k thành một số bằng hàm hash và sử dụng số này như là địa chỉ để tìm kiếm trên bảng dữ liệu. Cấu trúc dữ liệu và giải thuật HCMUS 2015 https tailieudientucntt FIT-HCMUS 2 5 ĐNĐTiến VCNam NTHNhung Cấu trúc dữ liệu và giải thuật HCMUS 2015 6 Chi phí tìm kiếm trung bình O 1 Chi phí tìm kiếm trong trường hợp xấu nhất O n rất ít gặp . Cấu trúc dữ liệu và giải thuật HCMUS 2015 https tailieudientucntt FIT-HCMUS 3 7 Định nghĩa Hàm băm hash function là hàm biến đổi khóa k của phần tử thành địa chỉ trong bảng băm. Tổng quát về phép biến đổi khóa Là 1 ánh xạ thích hợp từ tập các khóa U vào tập các địa chỉ A. H U A k a h k Tập các giá trị khóa U có thể lớn hơn rất nhiều so với số khóa thực tế K rất nhiều. Cấu trúc dữ liệu và giải thuật HCMUS 2015 8 T 1 Key Data . 2 . 3 3 Tập U . . . 2 1 4 4 5 5 6 . . . 4 3 6 Tập K 7 10 8 8 8 9 7 9 10 10 Cấu trúc dữ liệu và giải thuật HCMUS 2015 https tailieudientucntt FIT-HCMUS 4 9 Chọn số Digit-selection Chọn một vài chữ số trong khóa và ghép lại tạo thành giá trị băm. Ví dụ h 001364825 35 Ưu điểm Đơn giản tính toán nhanh Khuyết điểm Không thể hiện tính chất của khóa không phân bố đều Cấu trúc dữ liệu và giải thuật HCMUS 2015 10 Gấp số folding Cộngcác chữ số của khóa Nhóm các chữ số thành số và cộng lại Ví dụ h 001364825 0 0 1 3 6 4 8 2 5 29 h 001364825 001 .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Bảng băm
• Hàm băm
• Phương pháp giải quyế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ấ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
• 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
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đá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
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• 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
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp