Bài Giảng Cấu Trúc Dữ Liệu Và Giải Thuật: Bảng Băm - TaiLieu.VN

Trang chủ » Bảng Băm Trong 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: Bảng Băm - TaiLieu.VN

Có thể bạn quan tâm

OPTADS360 intTypePromotion=1 zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn tailieu.vn NÂNG CẤP Đăng Nhập | Đăng Ký Chủ đề »
  • Thiết kế cơ sở dữ liệu
  • Cài đặt SQL Server 2008
  • SQL Server 2008
  • Cơ sở dữ liệu quan hệ
  • Hệ quản trị cơ sở dữ liệu
  • HOT
    • TL.01: Bộ Tiểu Luận Triết Học
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi...
    • LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên...
    • FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    • CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị Doanh...
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Công Nghệ Thông Tin » Cơ sở dữ liệu Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Phan Mạnh Hiển (2020)

Chia sẻ: Minh Nhân | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST Báo xấu 42 lượt xem 4 download Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 học các kiến thức: Bảng băm, so sánh các cấu trúc dữ liệu, hàm băm (hash function), một hàm băm đơn giản, một hàm băm cho các xâu ký tự,... Mời các bạn cùng tham khảo nội dung chi tiết.

AMBIENT/ Chủ đề:
  • Bài giảng Cấu trúc dữ liệu và giải thuật
  • Cấu trúc dữ liệu và giải thuật
  • Cấu trúc dữ liệu
  • Cơ sở dữ liệu
  • Bảng băm
  • Hàm băm cho các xâu ký tự

Bình luận(0) Đăng nhập để gửi bình luận!

Đăng nhập để gửi bình luận! Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Phan Mạnh Hiển (2020)

  1. Bảng băm (Hash Tables) Nguyễn Mạnh Hiển hiennm@tlu.edu.vn
  2. Bảng băm • Các phần tử dưới dạng cặp khóa-giá trị (key-value) • Mỗi phần tử được lưu trữ vào một ô nào đó trong mảng tùy theo khóa của nó là gì • Thực hiện các phép tìm/chèn/xóa trong thời gian O(1) • Không hiệu quả với các thao tác đòi hỏi thông tin thứ tự: − VD: tìm phần tử lớn nhất và nhỏ nhất
  3. Ví dụ bảng băm Mỗi phần tử là một cặp khóa-giá trị: - Tên là khóa - Thu nhập là giá trị
  4. So sánh các cấu trúc dữ liệu • So sánh thời gian tìm kiếm: − Vector và danh sách liên kết: O(N) − Cây AVL: O(log N) − Bảng băm: O(1)
  5. Hàm băm (hash function) • Ánh xạ khóa sang số nguyên (vị trí trong bảng băm) • Nếu nhiều khóa ánh xạ sang cùng một số nguyên (cùng vị trí trong bảng băm) thì sẽ dẫn đến đụng độ − Đụng độ sẽ giảm nếu các khóa phân bố đồng đều hơn trên bảng băm − Khi đụng độ xảy ra, ta phải tìm cách phân giải sao cho các phần tử không ghi đè lên nhau (sẽ xem xét sau)
  6. Một hàm băm đơn giản • Gọi: − key: khóa có giá trị nguyên − tableSize: kích thước bảng băm • Một hàm băm đơn giản dùng phép chia lấy phần dư: hash(key) = key % tableSize • Giả sử: − key = 24, 48, 51, 78, 15 − tableSize = 10 • Thế thì: key % tableSize = 4, 8, 1, 8, 5 • Để giảm đụng độ, ta thường chọn kích thước bảng là một số nguyên tố
  7. Một hàm băm cho các xâu ký tự int hash(const string & key, int tableSize) { int hashVal = 0; for (int i = 0; i < key.size(); i++) hashVal += key[i]; return hashVal % tableSize; } • Ví dụ: − tableSize = 100 − key = "ABC" (mã ASCII của A, B, C là 65, 66, 67) − hashVal = (65 + 66 + 67) % 100 = 198 % 100 = 98 − Nếu key = "CBA" thì hashVal = ? • Một hàm băm tốt hơn cho xâu ký tự key = x0x1...xk-2xk-1 như sau: hash(key) = (x0*ak−1 + x1*ak−2 + ··· + xk−2*a + xk−1) % tableSize − Nếu xâu ký tự là từ tiếng Anh, có thể chọn a = 33, 37, 39 hoặc 41
  8. Thiết kế bảng băm 1. Hàm băm: Ánh xạ khóa sang một vị trí trong bảng băm − VD: hash(key) = key % tableSize 2. Phân giải đụng độ: − Giải quyết trường hợp nhiều khóa ánh xạ đến cùng một vị trí − Hai giải pháp thường gặp: • Dây chuyền (separate chaining) • Thăm dò (probing)
  9. Giải pháp dây chuyền • Mỗi ô trong mảng giữ một danh sách liên kết các phần tử (dây chuyền) • Các phần tử có khóa ánh xạ tới cùng một ô được giữ trong cùng một danh sách liên kết • Ví dụ: – hash(key) = key % 10 – chèn 10 số chính phương đầu tiên vào bảng băm
  10. Phân tích giải pháp dây chuyền • Xét bảng băm có M ô và chứa N phần tử • Chèn không kiểm tra tính duy nhất: O(1) – Tìm vị trí chèn dùng hàm băm – Gọi pushFront • Tìm/xóa/chèn có kiểm tra tính duy nhất, trường hợp tồi nhất (phải quét hết danh sách liên kết có N phần tử): O(N) • Tìm/xóa/chèn có kiểm tra tính duy nhất, tính trung bình: 1 + O(N/M) – Ta sẽ tăng kích thước bảng nếu số phần tử trung bình trong một ô, N/M, vượt quá hệ số tải  (≤ 1) – Do đó, thời gian trung bình = 1 + O() = O(1)
  11. Bảng băm thăm dò • Bảng băm dây chuyên phức tạp do phải duy trì một danh sách liên kết ở mỗi ô • Giải pháp thăm dò ô trống: − Nếu đụng độ xảy ra, thử các ô khác trong bảng − Thử lần lượt các ô h0(x), h1(x), h2(x), h3(x), … cho đến khi tìm được một ô trống • hi(x) = [hash(x) + f(i)] % tableSize • f(0) = 0 (vì ta sẽ bắt đầu thăm dò từ vị trí thu được sau khi áp dụng phép băm)
  12. Thăm dò tuyến tính hi(x) = [hash(x) + f(i)] % tableSize, f(i) = i • Phép chèn (giả sử các khóa không trùng nhau): 1. index = hash(x) 2. nếu table[index] rỗng, đặt phần tử mới (gồm khóa và giá trị) vào ô table[index] 3. nếu table[index] không rỗng: – index++; index = index % tableSize – quay lại bước 2 • Tìm kiếm: 1. index = hash(x) 2. nếu table[index] rỗng, trả về -1 (không tìm thấy) 3. nếu table[index].key == x, trả về index (tìm thấy) 4. index++; index = index % tableSize; quay lại bước 2
  13. Ví dụ Chèn 89, 18, 49, 58, 69 (hash(x) = x % 10)
  14. Thăm dò bậc hai hi(x) = [hash(x) + f(i)] % tableSize, f(i) = i2
  15. Tổ chức lại bảng băm • Bảng băm có thể bị đầy − Khi đó không thể chèn thêm được nữa • Bảng băm có thể khá đầy (nhưng chưa đầy 100%) − Chèn, xóa và tìm kiếm mất nhiều thời gian hơn • Giải pháp: Tổ chức lại bảng băm − Tạo bảng mới có kích thước lớn hơn (VD: gấp hai lần) − Định nghĩa hàm băm mới − Di chuyển các phần tử từ bảng cũ sang bảng mới • Chi phí tổ chức lại bảng băm = O(N) (N là số phần tử) − Khá tốn kém nhưng xảy ra không thường xuyên − Chỉ xảy ra khi bảng băm khá đầy (đầy X%, trong đó X là tham số điều chỉnh được)
  16. Ví dụ tổ chức lại bảng băm thăm dò tuyến tính Tổ chức lại bảng băm: Bảng băm ban đầu ‒ Gấp đôi kích thước cũ rồi tìm số nguyên tố kế tiếp (ở đây là 17) để dùng làm kích thước mới ‒ Quét bảng băm cũ từ đầu đến cuối để lấy ra các giá trị rồi chèn vào bảng mới theo đúng thứ tự lấy ra Chèn thêm 23
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật

    ppt 47 p | 175 | 17

  • Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến

    pdf 7 p | 162 | 9

  • Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp

    pdf 28 p | 77 | 9

  • Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính

    pdf 92 p | 116 | 9

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên

    pdf 25 p | 81 | 8

  • Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây

    pdf 21 p | 77 | 8

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu

    pdf 193 p | 59 | 7

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)

    ppt 62 p | 94 | 6

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )

    ppt 62 p | 159 | 6

  • Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây

    ppt 65 p | 58 | 6

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên

    pdf 30 p | 35 | 6

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)

    ppt 67 p | 106 | 4

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên

    pdf 68 p | 40 | 4

  • Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)

    pdf 44 p | 43 | 4

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên

    pdf 38 p | 47 | 4

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch

    pdf 24 p | 58 | 3

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung

    pdf 41 p | 68 | 3

  • Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu

    pdf 17 p | 50 | 2

Thêm tài liệu vào bộ sưu tập có sẵn: Đồng ý Thêm vào bộ sưu tập mới: *Tên bộ sưu tập Mô Tả: *Từ Khóa: Tạo mới Báo xấu
  • Hãy cho chúng tôi biết lý do bạn muốn thông báo. Chúng tôi sẽ khắc phục vấn đề này trong thời gian ngắn nhất.
  • Không hoạt động
  • Có nội dung khiêu dâm
  • Có nội dung chính trị, phản động.
  • Spam
  • Vi phạm bản quyền.
  • Nội dung không đúng tiêu đề.
Hoặc bạn có thể nhập những lý do khác vào ô bên dưới (100 ký tự): Vui lòng nhập mã xác nhận vào ô bên dưới. Nếu bạn không đọc được, hãy Chọn mã xác nhận khác.. Đồng ý LAVA AANETWORK THÔNG TIN
  • Về chúng tôi
  • Quy định bảo mật
  • Thỏa thuận sử dụng
  • Quy chế hoạt động
TRỢ GIÚP
  • Hướng dẫn sử dụng
  • Upload tài liệu
  • Hỏi và đáp
HỖ TRỢ KHÁCH HÀNG
  • Liên hệ
  • Hỗ trợ trực tuyến
  • Liên hệ quảng cáo
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

Đang xử lý... Đồng bộ tài khoản Login thành công! AMBIENT

Từ khóa » Bảng Băm Trong Cấu Trúc Dữ Liệu Và Giải Thuật