Chi tiết bài học bảng băm (hash table), bảng băm trong c++
Bảng băm là gì?
Bảng băm tốt HashTable là một kết cấu mà khi người dùng thực hiện tại truy xuất một phần tử qua khóa thì nó sẽ tiến hành ánh xạ vào thông qua hàm băm (Hash function).
Bạn đang xem: Chi tiết bài học bảng băm (hash table), bảng băm trong c++
Quá trình ánh xạ khóa vào bảng băm được triển khai thông qua hàm băm (Hashing). Một bảng băm xuất sắc cần phải có hàm băm tốt. Bảng băm là một mảng có M vị trí được đánh số từ 0 đến M – 1.
Như bạn có thể thấy trong hình, những khóa như 7, 17 chạm độ nhau thì chúng sẽ được thêm vào danh sách liên kết ở h(k) = M. Tương tự các khóa 4, 19 cũng trở thành đụng với được cung cấp danh sách link ở h(k) = 2…
Bây giờ bọn họ hãy cùng bắt đầu cài đặt bảng băm vào vào trong C++ nha.
Cấu trúc một nút trong bảng băm
Như sẽ nói, phương pháp kết nối trực tiếp dùng danh sách links đơn, các thành phần bị chạm độ tại thành phần i trong bảng băm thì sẽ được thêm vào danh sách links đơn trên i vào bảng băm. Bởi vì đó, một phần tử trong bảng băm có cấu tạo như một nút vào danh sách links đơn.
struct Node int key; Node* next;;
Cấu trúc bảng băm và hàm khởi tạo
Một bảng băm là 1 mảng chứa các nút, trả sử mình gồm 100 phần tử, vậy mình sẽ khái niệm một HashTable như sau:#define M 100typedef Node *HashTable
HashTable mHashTable;Các bạn cũng có thể dễ dàng thấy một nút vào bảng là một trong con trỏ trỏ cho một Node, như vậy, họ cần phải tạo lập chúng bằng NULL nhằm tránh gặp gỡ lỗi. Mình sẽ có hàm khởi chế tạo ra bảng như sau:
void InitHashTable(HashTable &HT) for (int i = 0; i M; i++) HT = NULL;Hàm băm
Như đã nói sinh hoạt trên, để dễ dàng và đơn giản mình sẽ thực hiện hàm băm theo phép chia:
int Hash(int k) return k % M;
Thêm một nút vào bảng băm
Để thêm 1 nút, ta đề nghị xác xác định trí vẫn thêm qua hàm băm h(k), tiếp nối thêm vào list liên kết ở phần h(k) đó. Việc đụng độ đang được xử lý do nếu va độ thì khóa sẽ tiến hành tự thêm vào sau danh sách links đơn. Mình sẽ có hàm thêm như sau:void InsertNode(HashTable &HT, int k) int i = Hash(k); AddTail(HT, k);Hàm AddTail thì trong danh sách liên kết đơn, tôi đã có bài viết về nó rồi, các chúng ta có thể đọc lại.
void AddTail(Node *&l, int k) Node *newNode = new Nodek, NULL; if (l == NULL) l = newNode; else Node* phường = l; while (p != NULL && p->next != NULL) p. = p->next; p->next = newNode;
Tìm kiếm một khóa vào bảng băm
Để tìm kiếm một khóa vào bảng băm, ta cũng thực hiện xác xác định trí h(k), sau đó ta thực hiện tìm kiếm trong danh sách links tại vị trí h(k) trong bảng băm.Xem thêm: Hệ Điều Hành Là Phần Mềm Hệ Thống Và Phần Mềm Ứng Dụng Là Gì, Xem Ví Dụ Chi Tiết
Node *SearchNode(HashTable HT, int k) int i = Hash(k); Node *p = HT; while (p != NULL && p->key != k) phường = p->next; if (p == NULL) return NULL; return p;Xóa một nút thoát khỏi bảng băm
Để xóa một phần tử ra khỏi bảng băm, trước tiên ta cũng phải xác định h(k), sau đó tìm coi nó nằm chỗ nào trong danh sách links đơn tại địa điểm h(k) kia rồi triển khai xóa nó đi.
void DeleteNode(HashTable &HT, int k) int i = Hash(k); Node *p = HT; Node *q = p; while (p != NULL && p->key != k) q = p; // giữ lại add của bộ phận trước đó p. = p->next; if (p == NULL) cout k " not found!" endl; else if (p == HT) DeleteHead(HT); // Nút bắt buộc xóa là phần tử đầu của DSLK else DeleteAfter(q); // Xóa nút sau nút qHai hàm DeleteHead và DeleteAfter cũng đã được mình trình bày trong bài Danh sách link đơn trong C++ rồi cần mình sẽ không giả say mê gì thêm.
void DeleteHead(Node *&l) if (l != NULL) Node *p = l; l = l->next; delete p; void DeleteAfter(Node *&q) Node *p = q->next; if (p != NULL) q->next = p->next; delete p;
Duyệt qua bảng băm
Duyệt qua bảng băm rất đối chọi giản, bạn chỉ cần duyệt qua mảng, mỗi phần tử của mảng là một danh sách liên kết đơn, vậy thì phê duyệt danh sách link đơn nữa là xong.void Traverse(Node *p) // để mắt tới DSLK while (p != NULL) cout p->key " "; phường = p->next; cout endl;void TraverseHashTable(HashTable HT) for (int i = 0; i M; i++) cout "Bucket " i ": "; Traverse(HT); Lưu ý về bảng băm
Đối với tài liệu lớn, việc cấp phát một mảng quá rộng sẽ tạo lãng phí bộ nhớ không xứng đáng có, tuy nhiên, việc M lớn đảm bảo an toàn việc chạm độ ít xẩy ra do các khóa phân bổ đều. Ngược lại, nếu như M nhỏ dại để tiết kiệm ngân sách và chi phí bộ nhớ, câu hỏi này sẽ làm cho giảm hiệu suất của bảng băm do câu hỏi đụng độ xảy ra với tần suất cao hơn.
Do vậy, khi thao tác với bảng băm, các bạn cần phải cân nhắc giữa công suất và dung lượng lưu trữ.
Tổng kết
Như vậy là trong bài viết này, mình đã ra mắt đến chúng ta về bảng băm vào C++, cách cài đặt bảng băm bởi phương thức liên kết trực tiếp dùng danh sách link đơn. Nếu các bạn có bất kỳ ý kiến, góp sức nào, chớ ngần ngại phản hồi phía bên dưới bài viết nha. Cảm ơn các bạn đã theo dõi bài bác viết!
Source code
#include using namespace std;#define M 10struct Node int key; Node *next;;typedef Node *HashTableChuyên mục: Domain Hosting
