Bảng Băm Là Gì

  -  

Bảng băm là gì?

Bảng băm xuất xắc HashTable là một trong những cấu trúc nhưng mà Khi người dùng tiến hành tróc nã 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: Bảng băm là gì


Quá trình ánh xạ khóa vào bảng băm được triển khai trải qua hàm băm (Hashing). Một bảng băm xuất sắc rất cần phải có hàm băm giỏi. Bảng băm là 1 mảng có M địa điểm được viết số từ bỏ 0 đến M – 1.


*
*
*
*
HashTable Chaining

Nlỗi bạn có thể thấy trong hình, những khóa nlỗi 7, 17 chạm độ nhau thì chúng sẽ được cung cấp list liên kết nghỉ ngơi h(k) = M. Tương tự những khóa 4, 19 cũng trở thành đụng cùng được cung ứng list liên kết làm việc h(k) = 2…

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

Cấu trúc một nút ít trong bảng băm

Nlỗi vẫn nói, phương pháp liên kết thẳng sử dụng list liên kết solo, những thành phần bị đụng độ trên thành phần i trong bảng băm thì sẽ được cung ứng danh sách liên kết đối chọi trên i vào bảng băm. Do đó, 1 phần tử trong bảng băm có cấu tạo nhỏng một nút vào danh sách links đối chọi.

struct Node int key; Node* next;;

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

Một bảng băm là 1 trong mảng cất những nút, đưa sử bản thân tất cả 100 bộ phận, vậy bản thân sẽ khái niệm một HashTable như sau:

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

HashTable mHashTable;Các bạn cũng có thể thuận tiện thấy một nút ít vào bảng là một trong con trỏ trỏ mang lại một Node, như vậy, họ rất cần được khởi tạo ra chúng bằng NULL để rời chạm mặt lỗi. Mình sẽ sở hữu được hàm khởi sản xuất bảng nlỗi sau:

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

Hàm băm

Như sẽ nói ở trên, để dễ dàng và đơn giản mình sẽ áp dụng hàm băm theo phnghiền chia:

int Hash(int k) return k % M;

Thêm một nút ít vào bảng băm

Để thêm một nút, ta bắt buộc xác xác định trí sẽ thêm qua hàm băm h(k), sau đó tiếp tế list link ở trong phần h(k) đó. Việc đụng độ sẽ tiến hành giải quyết và xử lý bởi vì giả dụ va độ thì khóa sẽ tiến hành tự thêm vào sau danh sách links đối chọi. Mình sẽ sở hữu được hàm thêm nhỏng sau:

void InsertNode(HashTable &HT, int k) int i = Hash(k); AddTail(HT, k);Hàm AddTail thì vào danh sách liên kết đối chọi, tôi đã có nội dung bài viết về nó rồi, các chúng ta cũng 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 &và p->next != NULL) p = p->next; p->next = newNode;

Tìm tìm một khóa vào bảng băm

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

Xem thêm: Nghĩa Của Từ Dock Là Gì, Ứng Dụng Của Nó Như Thế Nào? Đây Là Một Thuật Ngữ Kỹ Thuật Và Công Nghệ

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

Xóa một nút ít thoát khỏi bảng băm

Để xóa 1 phần tử thoát khỏi bảng băm, trước tiên ta cũng cần xác định h(k), sau đó search coi nó ở ở chỗ nào vào list links 1-1 tại vị trí h(k) đó rồi tiến hành 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; // Lưu lại cửa hàng của bộ phận trước kia p = p->next; if (p == NULL) cout k " not found!" endl; else if (p == HT) DeleteHead(HT); // Nút ít cần xóa là phần tử đầu của DSLK else DeleteAfter(q); // Xóa nút ít sau nút qHai hàm DeleteHead cùng DeleteAfter cũng đã được mình trình bày trong bài Danh sách link đối chọi vào C++ rồi buộc phải bản thân sẽ không trả 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 siêu dễ dàng, chúng ta chỉ việc chăm chút qua mảng, từng phần tử của mảng là một trong những list link solo, vậy thì coi ngó list link đối chọi nữa là hoàn thành.

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

Xem thêm: Roce Là Gì? Return On Capital Employed Là Gì ? Ý Nghĩa Và Công Thức Tính Roce

Do vậy, Lúc thao tác với bảng băm, các bạn cần phải Để ý đến giữa công suất và dung lượng lưu trữ.

Tổng kết

bởi thế là vào nội dung bài viết này, mình đã trình làng cho chúng ta về bảng băm trong C++, bí quyết thiết đặt bảng băm bởi cách làm liên kết thẳng dùng danh sách links đơn. Nếu chúng ta gồm bất kỳ chủ kiến, đóng góp làm sao, chớ ngần ngại comment phía dưới bài viết nha. Cảm ơn các bạn vẫ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* 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 &và 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;