tailieunhanh - Chương 5: Bảng băm (Hash table)

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

Không thể tạo bản xem trước, hãy bấm tải xuống
Tải xuống
TÀI LIỆU LIÊN QUAN

Tổng quan về ứng dụng công nghệ thông tin - truyền thông trong giáo dục
3    401    8

Mô tả công việc Giám đốc công nghệ thông tin
2    390    0

Luận văn: Tính toán hiệu quả chuyển giao công nghệ thông tin thông qua thị trường tin học
76    278    3

Công nghệ thông tin và ứng dụng công nghệ thông tin trong dạy học
8    386    15

Chương trình giáo dục Đại học theo học chế tín chỉ ngành: Công nghệ thông tin
28    289    0

Quyết định 995/QĐ-BTC năm 2013
5    277    0

Bài giảng Chương 2 - Thiết kế và quản lý dự án Công nghệ thông tin - PGS.TS Nguyễn Văn Định
26    311    1

Bài giảng Đại cương Công nghệ thông tin và truyền thông - ThS. GV. Phạm Quang Quyền
118    287    3

Giáo trình Tiếng Anh chuyên ngành Công nghệ thông tin
47    1247    85

Ebook Tìm hiểu Luật Công nghệ thông tin và các Nghị định hướng dẫn thi hành - NXB Bưu điện
74    359    6
TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8    461914    55

Giới thiệu :Lập trình mã nguồn mở
14    22877    64

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13    10958    531

Câu hỏi và đáp án bài tập tình huống Quản trị học
14    10145    450

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3    9557    104

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249    8337    1127

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16    8270    423

Mẫu đơn thông tin ứng viên ngân hàng VIB
8    7882    2224

Đề tài: Dự án kinh doanh thời trang quần áo nữ
17    6765    253

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152    5951    1438
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG

Giáo án mầm non chương trình đổi mới: Gia đình vui nhộn
4    318    1    11-05-2024

extremetech Hacking BlackBerry phần 9
31    259    0    11-05-2024

Trading Strategies Profit Making Techniques For Stock_8
23    180    1    11-05-2024

Đóng mới oto 8 chỗ ngồi part 9
10    123    0    11-05-2024

Báo cáo tốt nghiệp: Vận hành và bảo dưỡng trong MPLS
92    147    3    11-05-2024

Giáo trình phân tích phương trình vi phân viết dưới dạng thuật toán đặc tính của hệ thống p1
5    107    0    11-05-2024

Giáo án điện tử tiểu học môn lịch sử: Cách mạng mùa thu
39    117    0    11-05-2024

Các liệu pháp chăm sóc đặc biệt cho đôi chân
4    99    0    11-05-2024

Microsoft SQL Server 2012 T-SQL Fundamentals
442    96    0    11-05-2024

báo cáo khoa học: "Ultrasound-guided diagnostic breast biopsy methodology: retrospective comparison of the 8-gauge vacuum-assisted biopsy approach versus the spring-loaded 14-gauge core biopsy approach"
15    96    0    11-05-2024
TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB
8    7882    2224

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152    5951    1438

Ebook Chào con ba mẹ đã sẵn sàng
112    3780    1247

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62    5378    1137

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249    8337    1127

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561    3532    651

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13    10958    531

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122    3723    525

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274    4140    522

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35    4168    481
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.