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

3. Các phương pháp tránh xảy ra đụng độ . 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. | 3. Các phương pháp tránh xảy ra đụng độ . 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. Khi 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. Khi 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. Đe 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 30 50 60 11 21 31 . Hình . 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. Khi 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 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 .