HASH TABLE LÀ GÌ

  -  

Bảng băm là gì?

Bảng băm tốt HashTable là một cấu tạo mà khi người dùng thực hiện truy xuất một trong những 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: Hash table 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 tốt cần phải có hàm băm tốt. Bảng băm là một mảng tất cả M địa chỉ được khắc số từ 0 cho M – 1.


*
*
*
*
HashTable Chaining

Như chúng ta có thể thấy vào hình, các khóa như 7, 17 đụng độ nhau thì chúng sẽ tiến hành thêm vào danh sách liên kết ở h(k) = M. Giống như các khóa 4, 19 cũng bị đụng và được cung ứng danh sách links ở h(k) = 2…

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

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

Như đã nói, phương thức kết nối trực tiếp sử dụng danh sách links đơn, các phần tử bị đụng độ tại thành phần i trong bảng băm thì sẽ tiến hành thêm vào danh sách link đơn tại i vào bảng băm. Bởi đó, một trong những phần tử trong bảng băm có cấu trúc như một nút trong danh sách liên kết đơn.

struct Node int key; Node* next;;

Cấu trúc bảng băm cùng hàm khởi tạo

Một bảng băm là 1 mảng chứa các nút, đưa sử mình gồm 100 phần tử, vậy bản thân sẽ có mang một HashTable như sau:

#define M 100typedef Node *HashTable;Như vậy, bạn cũng 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 trong con trỏ trỏ đến một Node, như vậy, bọn họ cần phải khởi tạo chúng bởi NULL nhằm tránh gặp lỗi. Mình sẽ sở hữu 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ư đang nói ở 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 yêu cầu xác xác định trí vẫn thêm qua hàm băm h(k), tiếp đến thêm vào danh sách liên kết tại đoạn h(k) đó. Vấn đề đụng độ vẫn được giải quyết và xử lý do nếu va độ thì khóa sẽ được tự cung ứng sau danh sách links đơn. Mình sẽ sở hữu được hàm thêm như sau:

void InsertNode(HashTable &HT, int k) int i = Hash(k); AddTail(HT, k);Hàm AddTail thì vào danh sách links đơn, mình đã có 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

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

Xem thêm: 1001 Kí Tự Đặc Biệt Đẹp Nhất 2021 Đầy Đủ Thể Loại Cho Game, Kí Tự Đặc Biệt 2021 ✔️✔️✔️ Đẹp Chất Hay Số 1️⃣ Vn

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 thoát khỏi bảng băm

Để xóa một trong những phần tử thoát khỏi bảng băm, trước tiên ta cũng phải khẳng định h(k), kế tiếp tìm xem nó nằm nơi đâu trong danh sách liên kết đơn tại địa điểm 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 đó phường = p->next; if (p == NULL) cout k " not found!" endl; else if (p == HT) DeleteHead(HT); // Nút buộc phải xóa là bộ phận đầu của DSLK else DeleteAfter(q); // Xóa nút sau nút qHai hàm DeleteHead với DeleteAfter cũng được mình trình bày trong bài Danh sách liên kết đơn vào C++ rồi đề nghị mình sẽ không giả yêu thích 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 danh sách liên kết đơn, vậy thì trông nom danh sách liên kết đơn nữa là xong.

void Traverse(Node *p) // duyệt y DSLK 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);

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ẽ gây lãng phí bộ nhớ lưu trữ không xứng đáng có, mặc dù nhiên, việc M lớn bảo vệ việc va độ ít xảy ra do những khóa phân bổ đều. Ngược lại, nếu như M nhỏ để tiết kiệm ngân sách và chi phí bộ nhớ, vấn đề này sẽ có tác dụng giảm công 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.

Xem thêm: " Ccm Là Gì ? Viết Tắt Của Từ Gì? Completed Contract Method (Ccm) Là Gì

Do vậy, khi làm việc với bảng băm, các bạn phải cân kể giữa nă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, bản thân đã trình làng đến chúng ta về bảng băm trong C++, cách thiết đặt bảng băm bằng 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ó ngẫu nhiên ý kiến, góp phần 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 chúng ta đã 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 *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* p = 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; p. = 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;