Cấu Trúc Dữ Liệu : BẢNG BĂM (HASH TABLE) Part 2 - TaiLieu.VN

Trang chủ » Bảng Băm Sử Dụng Danh Sách Liên Kết » Cấu Trúc Dữ Liệu : BẢNG BĂM (HASH TABLE) Part 2 - 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
    • CEO.24: Bộ 240+ Tài Liệu Quản Trị Rủi...
    • TL.01: Bộ Tiểu Luận Triết Học
    • FORM.04: Bộ 240+ Biểu Mẫu Chứng Từ Kế...
    • LV.26: Bộ 320 Luận Văn Thạc Sĩ Y...
    • CEO.27: Bộ Tài Liệu Dành Cho StartUp...
    • CEO.29: Bộ Tài Liệu Hệ Thống Quản Trị...
    • CMO.03: Bộ Tài Liệu Hệ Thống Quản Trị...
    • FORM.08: Bộ 130+ Biểu Mẫu Thống Kê...
    • FORM.07: Bộ 125+ Biểu Mẫu Báo Cáo...
    LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài...
TUYỂN SINH YOMEDIA ADSENSE Trang Chủ » Công Nghệ Thông Tin » Cơ sở dữ liệu Cấu trúc dữ liệu : BẢNG BĂM (HASH TABLE) part 2

Chia sẻ: Alfhau Sdjfka | Ngày: | Loại File: PDF | Số trang:5

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

3. Các phương pháp tránh xảy ra đụng độ 2.4.1. Bảng băm với phương pháp kết nối trực tiếp (Direct chaining Method) Bảng băm được cài đặt bằng các danh sách liên kết, các phần tử trên bảng băm được “băm” thành M danh sách liên kết (từ danh sách 0 đến danh sách M–1). Các phần tử bị xung đột tại địa chỉ i được kết nối trực tiếp với nhau qua danh sách liên kết i. Chẳng hạn, với M=10, các phần tử có hàng đơn vị là 9 sẽ được băm vào danh sách liên kết i...

AMBIENT/ Chủ đề:
  • Cấu trúc dữ liệu
  • tài liệu Cấu trúc dữ liệu
  • đề cương Cấu trúc dữ liệu
  • giáo trình Cấu trúc dữ liệu
  • bài giảng Cấu trúc dữ liệu

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: Cấu trúc dữ liệu : BẢNG BĂM (HASH TABLE) part 2

  1. 3. Các phương pháp tránh xảy ra đụng độ 2.4.1. Bảng băm với phương pháp kết nối trực tiếp (Direct chaining Method) Bảng băm được cài đặt bằng các danh sách liên kết, các phần tử trên bảng băm được “băm” thành M danh sách liên kết (từ danh sách 0 đến danh sách M–1). Các phần tử bị xung đột tại địa chỉ i được kết nối trực tiếp với nhau qua danh sách liên kết i. Chẳng hạn, với M=10, các phần tử có hàng đơn vị là 9 sẽ được băm vào danh sách liên kết i = 9. K hi thêm một phần tử có khóa k vào bảng băm, hàm băm f(k) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sách liên kết i mà phần tử này sẽ được thêm vào. K hi tìm một phần tử có khóa k vào b ảng băm, hàm băm f(k) cũng sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sách liên kết i có thể chứa phần tử này. Như vậy, việc tìm kiếm phần tử trên bảng băm sẽ được qui về bài toán tìm kiếm một phần tử trên danh sách liên kết. Đ ể minh họa ta xét bảng băm có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9} - H àm băm h(key) = key % 10. 6
  2. 30, 50,60,11,21,31,… H ình 1.6. b ảng băm với phương pháp kết nối trực tiếp H ình trên minh họa bảng băm vừa mô tả. Theo hình vẽ, bảng băm đã "b ăm" phần tử trong tập khoá K theo 10 danh sách liên kết khác nhau, mỗi danh sách liên kết gọi là một bucket: · Bucket 0 gồm những phần tử có khóa tận cùng bằng 0. · Bucket i(i=0 | … | 9) gồm những phần tử có khóa tận cùng bằng i. · K hi khởi động bảng băm, con trỏ đầu của các bucket là NULL. Theo cấu trúc này, với tác vụ insert, hàm băm h(k) sẽ được dùng để tính địa chỉ của khoá k, tức là xác định bucket chứa phần tử và đặt phần tử cần chèn vào bucket này. V ới tác vụ search, hàm băm sẽ được dùng để tính địa chỉ và tìm phần tử trên bucket tương ứng + i=h(k) => thuoc danh sach thu I (bucket[i] + tim kiem khoa K tren danh sach bucket[i] Cài đặt bảng băm dùng phương pháp kết nối trực tiếp : 7
  3. a. Khai báo cấu trúc bảng băm: #define M 100 struct nodes { int key; struct nodes *next }; typedef struct nodes *NODEPTR; //khai bao kieu con tro chi nut /*khai bao mang bucket chua M con tro dau cua Mbucket */ NODEPTR bucket[M]; BT: xay dung bang bam theo PP ket noi truc tiep b.Các phép toán: - Tính giá trị hàm băm: G iả sử chúng ta chọn hàm băm dạng %: h(key)=key % M. - Phép toán initbuckets: khởi tạo các bucket băng Null. - Phép toán emmptybucket(b): kiểm tra bucket b có bị rỗng không? - Phép toán emmpty: K iểm tra bảng băm có rỗng không? - Phép toán insert: Thêm phần tử có khóa k vào bảng băm. + i=h(k) + ktra bucket [i]: neu rong =>cc o nho cho bucket, gan khoa k them phan tu co khoa k vao ds theo thu tu tang dan. - Phép toán remove: Xóa phần tử có khóa k trong bảng băm. - Phép toán clear: Xóa tất cả các phần tử trong bảng băm. - Phép toán traversebucket: X ử lý tất cả các p hần tử trong bucket b. - Phép toán traverse: Xử lý tất cả các phần tử trong bảng băm. - Phép toán search: Tìm kiếm một phần tử trong bảng băm, nếu không tìm thấy hàm này trả về hàm NULL, nếu tìm thấy hàm này trả về địa chỉ của phần tử có khóa k. B1: Tìm danh sách liên kết có thể chứa khóa k b = h(k); p = bucket[b]; B2: Tìm khóa k trong danh sách liên kết p. 8
  4. N hận xét bảng băm dùng phương pháp kết nối trực tiếp: Bảng băm dùng phương pháp kết nối trực tiếp sẽ "băm” n phần tử vào danh sách liên kết (M bucket). Đ ể tốc độ thực hiện các phép toán trên b ảng hiệu quả thì cần chọn hàm băm sao cho băm đều n phần tử của bảng băm cho M bucket, lúc này trung bình mỗi bucket sẽ có n/M phần tử. Chẳng hạn, phép toán search sẽ thực hiện việc tìm kiếm tuần tự trên bucket nên thời gian tìm kiếm lúc này có bậc 0(n/M) – nghĩa là, nhanh gấp M lần so với việc tìm kiếm trên một danh sách liên kết có n phần tử. N ếu chọn M càng lớn thì tốc độ thực hiện các phép toán trên bảng băm càng nhanh, tuy nhiên lại càng dùng nhiều bộ nhớ. Do vậy, cần điều chỉnh M để dung hòa giữa tốc độ truy xuất và dung lượng bộ nhớ. · N ếu chọn M=n thì năng xuất tương đương với truy xuất trên mảng (có bậc O(1)), tuy nhiên tốn nhiều bộ nhớ. 2.4.2. Bảng băm với phương pháp kết nối hợp nhất Mô tả: - Cấu trúc dữ liệu: Tương tự như trong trường hợp cài đặt bằng phương pháp kết nối trực tiếp, bảng băm trong trường hợp này được cài đ ặt bằng danh sách liên kết dùng mảng, có M phần tử. Các phần tử bị xung đột tại một địa chỉ được kết nối nhau qua một danh sách liên kết. Mỗi phần tử của bảng băm gồm hai trường: · Trường key: chứa khóa của mỗi phần tử · Trường next: co n trỏ chỉ đến phần tử kế tiếp nếu có xung đột. - K hởi động: Khi khởi động, tất cả trường key của các phần tử trong bảng băm được gán bởi giá trị NullKey, còn tất cả các trường next được gán –1. - Thêm mới một phần tử: Khi thêm mới một phần tử có khóa key vào bảng băm, hàm băm hkey) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1. · N ếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ này. · N ếu bị xung đột thì phần tử mới được cấp phát là phần tử trống phía cuối m ảng. Cập nhật liên kết next sao cho các phần tử bị xung đột hình thành một danh sách liên kết. - Tìm kiếm: Khi tìm kiếm một phần tử có khóa key trong bảng băm, hàm băm h(key) sẽ giúp giới hạn phạm vi tìm kiếm bằng cách xác định địa chỉ i trong 9
  5. khoảng từ 0 đến M-1, và việc tìm kiếm phần tử khóa có khoá key trong danh sách liên kết sẽ xuất phát từ địa chỉ i. Đ ể minh họa cho bảng băm với phương pháp kết nối hợp nhất, xét ví dụ sau: G iả sử, khảo sát bảng băm có cấu trúc như sau: - Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9} - H àm băm f(key) = key % 10. VD: K ey : 11 12 21 1 13 H ash: 1 2 11 3 Add Key N ext Add Key Next 0 NullKey -1 0 NullKey -1 1 NullKey -1 1 11 9 … NullKey -1 2 12 -1 M-1 NullKey -1 3 13 -1 … NullKey -1 8 1 -1 9 21 8 K hai báo cấu trúc bảng băm: #define NULLKEY –1 #define M 100 typedef struct node { int key; //khoa cua nut tren bang bam int next; //con tro chi nut ke tiep khi co xung dot } NODE; 10
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

  • Cấu trúc dữ liệu : BẢNG BĂM (HASH TABLE) part 1

    pdf 5 p | 480 | 80

  • Cấu trúc dữ liệu : BẢNG BĂM (HASH TABLE) part 3

    pdf 5 p | 480 | 61

  • Ứng dụng và cài đặt cấu trúc dữ liệu bằng C: Phần 2

    pdf 239 p | 71 | 14

  • Ứng dụng và cài đặt cấu trúc dữ liệu bằng C: Phần 1

    pdf 338 p | 35 | 12

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - ThS. Trịnh Quốc Sơn (ĐH Công nghệ Thông tin8

    pdf 17 p | 66 | 11

  • Giáo trình Cấu trúc dữ liệu và Thuật giải 2: Phần 2 - Ng.Thị Thanh Bình, Ng.Văn Phúc

    pdf 35 p | 135 | 8

  • 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ảng băm - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

    pdf 17 p | 62 | 6

  • 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)

    pdf 16 p | 41 | 4

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

    ppt 53 p | 59 | 4

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Nguyễn Mạnh Hiển

    pdf 16 p | 66 | 3

  • 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

    pdf 32 p | 34 | 3

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

    pdf 13 p | 62 | 3

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Cây cân bằng Red Black và AA - Nguyễn Tri Tuấn

    pdf 61 p | 33 | 3

  • 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 nâng cao - Nguyễn Tri Tuấn

    pdf 63 p | 39 | 3

  • Java: Hệ thống thuật toán và cấu trúc dữ liệu - Phần 2

    pdf 257 p | 8 | 3

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

    ppt 27 p | 65 | 2

  • Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Đỗ Ngọc Như Loan

    ppt 18 p | 40 | 1

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 Sử Dụng Danh Sách Liên Kết