TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu: Bảng băm - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Bảng băm cung cấp cho người học những kiến thức như: Hàm băm (hash function); Bảng băm; Đụng độ và xử lí đụng độ; Chuỗi liên kết; Dò tuyến tính/ bậc 2/ băm kép; Kết luận. Mời các bạn cùng tham khảo! | TS. Lê Minh Trung ThS Lương Trần Ngọc Khiết Khoa Công nghệ Thông tin Đại học Sư phạm TP. HCM Bảng băm Hash Table Hàm băm hash function Bảng băm Đụng độ và xử lí đụng độ Chuỗi liên kết Dò tuyến tính bậc 2 băm kép Kết luận Bài toán tìm kiếm Tìm kiếm tuần tự Duyệt qua các phần tử của mảng một cách tuần tự Độ phức tạp O N Tìm kiếm nhị phân Mảng đã được sắp thứ tự Độ phức tạp 2 Trong thực tế kích cỡ mảng cần tìm N có thể lên tới hàng tỷ Có phương pháp tìm kiếm nào có độ phức tạp O 1 Hàm băm Hash function Là hàm ℎ ánh xạ từ tập các khóa key K vào 0 1 . ℎ 0 1 2 1 ℎ được gọi là giá trị băm của . Tập các khóa K có thể là tập các chuỗi các số tự nhiên ℎ 0 1 với ℎ Hàm băm tt Với các khóa chưa ở dạng số hàm băm thường có dạng sau ℎ ℎ2 ℎ1 với là một khóa. ℎ1 để tính mã băm hash code . ℎ2 0 1 2 1 là hàm nén. ℎ2 Ví dụ hàm băm Giả sử các khóa là các chuỗi 1 1 0 Có thể tính mã băm như sau ℎ1 0 128 bảng mã ASCII có 128 kí hiệu ℎ1 0 36 26 chữ thường 10 chữ số Có thể sử dụng hàm nén như sau ℎ2 100 Hàm băm ℎ ℎ2 ℎ1 ℎ1 100 Hàm nén Nhân Nhân Multiply Cộng h2 y y mod N Add và Chia Divide MAD N là kích cỡ của bảng h2 y ay b mod N băm và thường được chọn là số nguyên tố. a và b là các số nguyên không âm sao cho Liên quan tới lí thuyết số. a mod N 0 7 Bảng băm Hash Table Là một bảng mảng có kích cỡ hash_size N. N thường được chọn là số nguyên tố. Mẩu tin record có khóa là k sẽ được lưu trữ tại vị trí h k trong bảng. h là hàm hash h thường được chọn là hàm modulo h k k mod N. Lí tưởng nếu chọn được N là số khóa k thực sự được sử dụng Bảng băm U 0 tất cả các khóa h k1 k1 h k4 K k4 các khóa k5 h k2 h k5 thật sự dùng k2 h k3 k3 N-1 Bảng băm Một đụng độ collision xảy ra khi hai khóa được ánh xạ vào cùng vị trí trong bảng ℎ 1 ℎ 2 . U 0 tất cả các khóa Đụng h k độ1 k1 h k4 K k4 các khóa k5 h k2 h k5 thật sự dùng k2 h k3 k3 N-1 Ví dụ bảng băm Thêm vào các khóa 51 24 37 42 88. 0 Hàm băm h k k mod 10 51 1 42 2 Tìm 37 3 24 4 5 Không thấy Tìm 56 6 37 7 88 8 Tìm 62 9 Đụng độ 0 51 1 Đụng 42 độ 2 Thêm khóa

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu
• Data Structures
• Bảng băm
• Tìm kiếm tuần tự
• Chuỗi liên kết
• Phương pháp chuỗi liên kết
• Phương pháp thăm dò
• 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
• 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
• Ngôn ngữ lập trình
• 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