Bảng băm là gì

     

Bảng băm là gì?

Bảng băm tốt HashTable là 1 kết cấu cơ mà khi người dùng tiến hành 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: Bảng băm là gì


Quá trình ánh xạ khóa vào bảng băm được thực hiện trải qua hàm băm (Hashing). Một bảng băm tốt cần phải có hàm băm xuất sắc. Bảng băm là 1 trong những mảng tất cả M vị trí được khắc số tự 0 cho M – 1.


*
*
*
*
HashTable Chaining

Nhỏng bạn cũng có thể thấy vào hình, các khóa như 7, 17 va độ nhau thì bọn chúng sẽ được sản xuất list link nghỉ ngơi h(k) = M. Tương từ bỏ những khóa 4, 19 cũng bị chạm với được chế tạo danh sách link ở h(k) = 2…

Bây giờ họ hãy thuộc ban đầu thiết lập 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ư sẽ nói, phương thức kết nối thẳng dùng list liên kết đơn, những phần tử bị va độ tại phần tử i vào bảng băm thì sẽ tiến hành thêm vào list links đối kháng tại i trong bảng băm. Do kia, một trong những phần tử vào bảng băm gồm kết cấu như một nút ít trong list links 1-1.

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à một mảng cất các nút ít, đưa sử mình bao gồm 100 phần tử, vậy mình vẫn tư tưởng một HashTable như sau:

#define M 100typedef Node *HashTable;bởi thế, bạn cũng có thể knhị báo một bảng băm như sau:

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

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

Hàm băm

Như đang nói trên, để đơn giản dễ dàng bản thân đã áp 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 1 nút, ta đề nghị xác xác định trí đang thêm qua hàm băm h(k), tiếp nối cấp dưỡng danh sách liên kết ở phần h(k) đó. Việc va độ sẽ tiến hành giải quyết vì chưng trường hợp đụng độ thì khóa sẽ tiến hành từ bỏ cấp dưỡng sau danh sách link đối kháng. Mình sẽ có hàm thêm nlỗi sau:

void InsertNode(HashTable &HT, int k) int i = Hash(k); AddTail(HT, k);Hàm AddTail thì trong danh sách link 1-1, mình đã có nội dung bài viết về nó rồi, các chúng ta có thể hiểu 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) 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 trong bảng băm, ta cũng tiến hành xác xác định trí h(k), tiếp đến ta thực hiện search kiếm trong list link trên địa điểm h(k) trong bảng băm.

Xem thêm: Workshop #1: Team Bonding Là Gì, Nghĩa Của Từ Bonding Trong Tiếng Việt

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

Để xóa một trong những phần tử thoát ra khỏi bảng băm, đầu tiên ta cũng đề nghị khẳng định h(k), tiếp nối search xem nó ở ở chỗ nào vào danh sách links đối kháng trên địa chỉ 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; // Lưu lại liên hệ 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 nên 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 được mình trình bày trong bài Danh sách liên kết đối kháng vào C++ rồi bắt buộc bản thân sẽ không còn giả ưa 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 cực kỳ đơn giản dễ dàng, chúng ta chỉ việc chuyên chú qua mảng, mỗi bộ phận của mảng là 1 trong những danh sách links 1-1, vậy thì lưu ý danh sách liên kết solo nữa là dứt.

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

Do vậy, Lúc thao tác làm việc với bảng băm, những bạn phải quan tâm đến thân công suất cùng dung lượng tàng trữ.

Tổng kết

Vậy nên là trong nội dung bài viết này, tôi đã ra mắt cho chúng ta về bảng băm vào C++, biện pháp thiết lập bảng băm bởi cách thức kết nối trực tiếp cần sử dụng danh sách liên kết đối kháng. Nếu các bạn có ngẫu nhiên chủ ý, góp phần nào, chớ e dè phản hồi phía bên dưới nội dung bài viết nha. Cảm ơn chúng ta đang theo dõi và quan sát 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 &và 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;

Chuyên mục: Đầu tư tài chính