Bảng băm là gì

     

Bảng băm là gì?

Bảng băm hay HashTable là một kết cấu mà khi người tiêu dùng thực hiện truy xuất một trong những phần tử qua khóa thì nó sẽ được ánh xạ vào thông qua hàm băm (Hash function).

Bạn đang xem: Bảng băm là gì


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 bao gồm hàm băm tốt. Bảng băm là 1 trong những mảng bao gồm M vị trí được khắc số từ 0 mang lại M – 1.


*
*
*
*
HashTable Chaining

Như bạn có thể thấy trong hình, các khóa như 7, 17 va độ nhau thì chúng sẽ tiến hành 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 bị đụng cùng được cấp dưỡng danh sách link ở h(k) = 2…

Bây giờ chúng ta hãy cùng ban đầu cài đặt bảng băm vào trong trong C++ nha.

Cấu trúc một nút vào bảng băm

Như vẫn nói, cách thức kết nối trực tiếp cần sử dụng danh sách links đơn, các phần tử bị va độ tại phần tử i trong bảng băm thì sẽ tiến hành thêm vào danh sách links đơn tại i trong bảng băm. Vì chưng đó, một phần tử vào bảng băm có cấu tạo như một nút trong danh sách link đơ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 những nút, trả sử mình tất cả 100 phần tử, vậy mình sẽ định nghĩa một HashTable như sau:

#define M 100typedef Node *HashTable;Như vậy, chúng ta có thể khai báo một bảng băm như sau:

HashTable mHashTable;Các chúng ta cũng có thể dễ dàng thấy một nút trong bảng là 1 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 chạm mặt lỗi. Mình sẽ sở hữu được hàm khởi tạo thành bảng như sau:

void InitHashTable(HashTable &HT) for (int i = 0; i M; i++) HT = NULL;

Hàm băm

Như vẫn nói sinh hoạt trên, để đơn giản dễ dàng mình sẽ sử dụng 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 một nút, ta buộc phải xác định vị trí đang thêm qua hàm băm h(k), tiếp nối thêm vào danh sách liên kết tại vị trí h(k) đó. Việc đụng độ sẽ được giải quyết do nếu va độ thì khóa sẽ tiến hành tự sản xuất sau danh sách link đơ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 links đơn, mình đã có nội dung bài viết về nó rồi, các bạn có thể đọc lại.

void AddTail(Node *&l, int k) Node *newNode = new Nodek, NULL; if (l == NULL) l = newNode; else Node* p = l; while (p != NULL && p->next != NULL) phường = p->next; p->next = newNode;

Tìm tìm một khóa trong bảng băm

Để kiếm tìm kiếm một khóa vào bảng băm, ta cũng tiến hành xác xác định trí h(k), kế tiếp ta tiến hành tìm tìm trong danh sách links tại vị trí h(k) vào bảng băm.

Xem thêm: Bảo Hiểm Xã Hội Huyện Sóc Sơn Thông Tin Địa Chỉ Liên Hệ, Địa Chỉ Cơ Quan Bảo Hiểm Xã Hội Huyện Sóc Sơn

Node *SearchNode(HashTable HT, int k) int i = Hash(k); Node *p = HT; while (p != NULL && p->key != k) p. = p->next; if (p == NULL) return NULL; return p;

Xóa một nút ra khỏi bảng băm

Để xóa 1 phần tử thoát khỏi bảng băm, thứ nhất ta cũng phải khẳng định h(k), kế tiếp tìm coi nó nằm ở chỗ nào trong danh sách liên kết đơn tại địa chỉ h(k) đó rồi thực hiện 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 showroom 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 phải xóa là thành phần đầu của DSLK else DeleteAfter(q); // Xóa nút sau nút qHai hàm DeleteHead cùng DeleteAfter cũng sẽ được mình trình diễn trong bài Danh sách links đơn trong C++ rồi đề xuất mình sẽ không giả ưng ý 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ỉ việc duyệt qua mảng, mỗi bộ phận của mảng là 1 trong những danh sách liên kết đơn, vậy thì chăm chút danh sách links đơn nữa là xong.

void Traverse(Node *p) // lưu ý 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á to sẽ gây lãng phí bộ lưu trữ không đáng có, mặc dù nhiên, bài toán M lớn đảm bảo việc va độ ít xẩy ra do những khóa phân bổ đều. Ngược lại, ví như M nhỏ tuổi để tiết kiệm ngân sách và chi phí bộ nhớ, vấn đề này sẽ làm cho giảm hiệu suất của bảng băm do việc đụng độ xẩy ra với tần suất cao hơn.

Xem thêm: Các Mẹ Thông Thái Chỉ Em Mua Vitamin A Cho Trẻ Ở Đâu ? Mua Vitamin A Cho Trẻ Ở Đâu

Do vậy, khi thao tác với bảng băm, các bạn phải cân kể giữa hiệu suất và dung lượng lưu trữ.

Tổng kết

Như vậy là trong bài viết này, bản thân đã ra mắt đến các bạn về bảng băm vào C++, cách thiết lập bảng băm bằng phương thức kết nối trực tiếp dùng danh sách link đơn. Nếu chúng ta có bất kỳ ý kiến, góp sức nào, chớ ngần ngại bình luận phía mặt dưới nội dung bài viết nha. Cảm ơn các bạn đã theo dõi bài viết!

Source code

#include using namespace std;#define M 10struct Node int key; Node *next;;typedef Node *HashTable;void InitHashTable(HashTable &HT) for (int i = 0; i M; i++) HT = NULL;int Hash(int k) return k % M;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; void InsertNode(HashTable &HT, int k) int i = Hash(k); AddTail(HT, k);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; void DeleteNode(HashTable &HT, int k) int i = Hash(k); Node *p = HT; Node *q = p; while (p != NULL && p->key != k) q = p; phường = p->next; if (p == NULL) cout k " not found!" endl; else if (p == HT) DeleteHead(HT); else DeleteAfter(q);Node *SearchNode(HashTable HT, int k) int i = Hash(k); Node *p = HT; while (p != NULL && p->key != k) p. = p->next; if (p == NULL) return NULL; return p;void Traverse(Node *p) while (p != NULL) cout p->key " "; p. = p->next; cout endl;void TraverseHashTable(HashTable HT) for (int i = 0; i M; i++) cout "Bucket " i ": "; Traverse(HT); int main() HashTable mHashTable; InitHashTable(mHashTable); InsertNode(mHashTable, 0); InsertNode(mHashTable, 1); InsertNode(mHashTable, 2); InsertNode(mHashTable, 3); InsertNode(mHashTable, 10); InsertNode(mHashTable, 13); InsertNode(mHashTable, 9); InsertNode(mHashTable, 11); cout "HashTable: "; TraverseHashTable(mHashTable); DeleteNode(mHashTable, 3); DeleteNode(mHashTable, 13); DeleteNode(mHashTable, 9); cout "HashTable after Delete: "; TraverseHashTable(mHashTable); Node *result = SearchNode(mHashTable, 10); if (result == NULL) cout "Not found!"; else cout "Found!"; std::cout std::endl; system("pause"); return 0;