intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

BẢNG BĂM (Hashing Table)

Chia sẻ: Hà Linh | Ngày: | Loại File: PDF | Số trang:25

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

Giả sử ta có 100 số nguyên có giá trị bất kỳ nằm trong khoảng từ 0 . . 999 Nếu sử dụng mảng a gồm 1000 phần tử để lưu trữ các số nguyên này sao cho a[i] = i thì số lần tìm kiếm số nguyên bất kỳ trong 100 số này là 1 lần Tuy nhiên, chỉ có 1/10 bộ nhớ được sử dụng, dẫn đến lãng phí bộ nhớ Phép biến đổi khóa là phương pháp tham khảo trực tiếp các phần tử trong một bảng (bảng băm) thông qua việc biến đổi số học trên...

Chủ đề:

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

Lưu

Nội dung Text: BẢNG BĂM (Hashing Table)

  1. BẢNG BĂM (Hashing Table) Chương 5 1
  2. Khái niệm Giả sử ta có 100 số nguyên có giá trị bất kỳ nằm trong khoảng từ 0 . . 999 Nếu sử dụng mảng a gồm 1000 phần tử để lưu trữ các số nguyên này sao cho a[i] = i thì số lần tìm kiếm số nguyên bất kỳ trong 100 số này là 1 lần Tuy nhiên, chỉ có 1/10 bộ nhớ được sử dụng, dẫn đến lãng phí bộ nhớ Phép biến đổi khóa là phương pháp tham khảo trực tiếp các phần tử trong một bảng (bảng băm) thông qua việc biến đổi số học trên những khoá để có được địa chỉ tương ứng của những phần tử ở trong bảng 2
  3. Khái niệm Phép biến đổi khoá là một phương pháp giải quyết tốt về thời gian và vùng nhớ Tổ chức dữ liệu được dùng cho phép biến đổi khoá là cấu trúc bảng (bảng băm) Để thực hiện phép biến đổi khoá ta cần hai bước: 1. Bước 1: Tính toán việc biến đổi số học (hàm H() nào đó) để biến đổi khoá cần tìm thành địa chỉ trong bảng. Trong bước này, có thể có hai hay nhiều khoá khác nhau thông qua hàm H() sẽ cho cùng một địa chỉ trong bảng 3
  4. Khái niệm 2. Bước 2: Là quá trình giải quyết sự đụng độ cho những khoá khác nhau có cùng một địa chỉ trong bảng Vấn đề trước tiên là phải chọn hàm biến đổi khoá (hàm băm) để biến đổi các khóa thành các địa chỉ trong bảng Yêu cầu của hàm băm là phải đơn giản, dễ tính, phải là hàm phân bố đều tập khoá k trên tập địa chỉ để việc đụng độ ít xảy ra Có một số phương pháp để xây dựng hàm băm như phương pháp chia, nhân, phân đoạn. Tuy nhiên, phương pháp chia modulo thường được sử dụng 4
  5. Xây dựng hàm băm Phương pháp chia modulo: – Gọi M là kích thước bảng băm (thường chọn M là số nguyên tố để ít có bội số - xem trang 8), K là khóa và H(k) là hàm băm, thì: H(k) = k % M – Hàm băm sẽ biến đổi các khoá (là số nguyên, chữ cái hay chuỗi) thành các số nguyên tương ứng trong đoạn [0 ... M - 1] – Nếu khoá là số nguyên thì hàm băm H(k) là: H(k) = k % M 5
  6. Xây dựng hàm băm – Nếu khoá là chữ cái từ A đến Z thì giá trị của k sẽ là giá trị của các chữ cái được mã hoá từ 0 đến 25: Ký tự Nhị phân Thập phân A 00000 0 B 00001 1 c 00010 2 ... Z 11001 25 6
  7. Xây dựng hàm băm – Nếu khoá là chuỗi ký tự thì giá trị k sẽ là giá trị của sự kết hợp các chữ cái trong chuỗi. Ví dụ, kích thước bảng băm là 101 và cần phải tính địa chỉ của một khóa 4 ký tự là AKEY. Nếu mỗi chữ cái được mã hóa bằng số nhị phân 5 bit như trên thì A K E Y k = 00000 01010 00100 11000 = 10 * 322 + 4 * 321 + 24 * 320 = 10392 Do đó, chỉ số của khóa AKEY trong bảng là: 10392 % 101 = 90 7
  8. Xây dựng hàm băm Tại sao kích thước M của bảng phải là số nguyên tố? Để trả lời câu hỏi này, giả sử ta chọn M bằng 32 không phải là số nguyên tố, và khóa là chuỗi AKEY như trên, thì: k = 10 * 322 + 4 * 321 + 24 * 320 chỉ phụ thuộc vào ký tự cuối cùng Y. Nghĩa là sẽ có nhiều khóa khác nhau có cùng chỉ số trong bảng nếu các khóa này có cùng ký tự cuối là Y 8
  9. Xây dựng hàm băm Trong trường hợp các khoá dài thì phải tính hàm băm sao cho không bị tràn số. Khi này có thể sử dụng công thức Horner để tính giá trị của hàm băm k = (((anx + an-1)x + an-2)x + ... + a0) Trong đó, x là cơ số (ví dụ, 5 bit sẽ có cơ số là 32) và M là kích thước của bảng. Trong ví dụ trên, có thể viết lại bằng công thức Horner là: k = (10 * 32 + 4) * 32 + 24 9
  10. Xây dựng hàm băm Giải thuật Horner để tính hàm băm như sau: h = key[0]; for(int i = 1; i < keysize; i++) h = ((h * 32) + key[i]) % M; Trong đó, h (= H(k)) là giá trị băm (chỉ số trong bảng băm), key[i] là giá trị của ký tự thứ i của khóa và keysize là chiều dài của khóa. Ví dụ, khóa VERYLONGKEY và M = 101 thì khóa này sẽ có chỉ số là 72 10
  11. Xử lý đụng độ Sự đụng độ là hiện tượng các khóa khác nhau, nhưng qua hàm băm chúng có cùng địa chỉ trên bảng băm. Vấn đề đặt ra là phải lưu trữ chúng như thế nào trong bảng Xét ba phương pháp: Thử tuyến tính, móc nối ngoài và móc nối trong: 1. Phương pháp thử tuyến tính (linear probing): – Trong phương pháp này khi có sự đụng độ xảy ra thì tìm kiếm vị trí trống từ kế sau phần tử bị đụng độ cho đến cuối bảng thì quay về đầu bảng 11
  12. Xử lý đụng độ – Khai báo: const int M = 11; struct Node { int key; }; Node table[M]; int n; // số phần tử hiện có – Khởi tạo: Giả sử khóa là các số dương, khi khởi tạo ta cho trường key của các phần tử trong bảng một giá trị không thuộc tập khóa, chẳng hạn là –1 và gán số phần tử hiện có trong bảng bằng 0 12
  13. Xử lý đụng độ void init() { for(int i = 0; i < M; i++) table[i].key = -1; n = 0; } – Thêm một khóa vào bảng: Hàm insert() thêm một phần tử có khóa k vào bảng. Giá trị trả về của hàm là vị trí của phần tử mới thêm hoặc –1 nếu bảng bị đầy (xem ví dụ) 13
  14. Xử lý đụng độ – Ví dụ, với M = 11 và các khóa như sau: Khóa k: 16 28 25 6 27 19 41 35 H(k): 5 6 3 6 5 8 8 2 – Như vậy, nếu gọi i là chỉ số trong bảng. Giá trị của hàm băm lại lần j trong phương pháp này là: i0 = H(k) ij = (i0 + j) % M (với j = 1, 2, . . , M - 1) 14
  15. Xử lý đụng độ – Tìm một khóa trong bảng băm: Hàm search() tìm một khóa trong bảng băm. Trả về vị trí của khóa này nếu tìm thấy hoặc trả về –1 nếu không tìm thấy (xem ví dụ) – Nhược điểm của phương pháp này là xảy ra hiện tượng hội tụ xung quanh các địa chỉ không bị đụng độ, làm cho các khóa được băm với địa chỉ này không thể được thêm vào, dẫn đến tốc độ xử lý chậm vì phải tìm vị trí trống còn lại khi bảng gần đầy – Để khắc phục nhược điểm này, người ta sử dụng công thức tính địa chỉ là i0 = H(k) ij = (i0 + j2) % M (j > 0) 15
  16. Xử lý đụng độ – Phương pháp trên được gọi là phương pháp thử bậc hai (quadratic probing 2. Phương pháp móc nối ngoài: – Trong phương pháp này thì mỗi vị trí trong bảng băm trỏ đến đầu danh sách liên kết của các phần tử có cùng địa chỉ trong bảng – Ví dụ, với M = 7 và các khoá như sau: Khóa k: 30 15 17 11 8 8 16 3 11 18 H(k): 2 1 3 4 1 1 2 3 4 4 16
  17. Xử lý đụng độ 17
  18. Xử lý đụng độ – Khai báo: const int M = 7; struct Node { int key; Node *next; }; Node *heads[M]; – Khởi tạo: Cho mảng heads chứa các phần tử mà vùng liên kết next của nó trỏ đến đầu danh sách liên kết. Lúc đầu, các vùng liên kết này trỏ đến NULL 18
  19. Xử lý đụng độ void init() { for(int i = 0; i < M; i++) { heads[i]= new Node; heads[i]->next = NULL; } } – Thêm một khóa vào bảng: Hàm insert() thêm phần tử có khóa k vào DSLK của bảng băm. Mỗi DSLK là một dãy các phần tử đã có thứ tự (tăng dần). Mục đích là để tìm kiếm nhanh. Nếu có nhiều khóa giống nhau thì phần tử mới thêm được chèn vào đầu DSLK (xem ví dụ) 19
  20. Xử lý đụng độ – Tìm một khóa trong bảng: Hàm search() tìm một khóa trong bảng băm. Nếu tìm thấy, nó trả về vị trí của DSLK chứa khoá đó trong mảng heads. Ngược lại, trả về trị là –1 (xem ví dụ) – Ưu điểm của phương pháp này là xử lý đụng độ đơn giản và hiệu quả; kích thước bảng băm không cần lớn hơn các khóa được thêm vào bảng và cuối cùng là thao tác xóa một phần tử trong bảng cũng dễ dàng. Nhược điểm là cần thêm vùng nhớ cho phần liên kết của mỗi phần tử 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
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.

 

Đồng bộ tài khoản
2=>2