Hash Table Là Gì

     

Bảng băm là gì?

Bảng băm xuất xắc HashTable là một kết cấu mà khi người dùng thực hiện nay truy xuất một trong những phần tử qua khóa thì nó sẽ được ánh xạ vào trải 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 tiến hành thông qua hàm băm (Hashing). Một bảng băm tốt cần phải tất cả hàm băm tốt. Bảng băm là 1 trong mảng có M địa điểm được viết số từ 0 mang lại M – 1.


*
*
*
*
HashTable Chaining

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

Bây giờ bọn họ 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ư đang nói, phương pháp kết nối trực tiếp cần sử dụng danh sách link đơn, các thành phần 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 liên kết đơn trên i trong bảng băm. Vị đó, một trong những phần tử trong 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à một trong những mảng chứa những nút, giả sử mình bao gồm 100 phần tử, vậy mình sẽ quan niệm một HashTable như sau:

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

HashTable mHashTable;Các bạn có thể dễ dàng thấy một nút vào bảng là một con trỏ trỏ mang đến một Node, như vậy, bọn họ cần phải khởi tạo chúng bởi NULL để tránh gặp lỗi. Mình sẽ sở hữu đượ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 ở trên, để dễ dàng mình sẽ á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 một nút, ta đề xuất xác định vị trí đã thêm qua hàm băm h(k), tiếp nối thêm vào danh sách liên kết ở vị trí h(k) đó. Bài toán đụng độ đang được xử lý do nếu va độ thì khóa sẽ tiến hành tự sản xuất sau danh sách liên kết đơ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ũng 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) phường = p->next; p->next = newNode;

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

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

Xem thêm: Essentials Là Gì ? Định Nghĩa, Ví Dụ, Giải Thích Định Nghĩa, Ví Dụ, Giải Thích

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ử ra khỏi bảng băm, đầu tiên ta cũng phải xác định h(k), tiếp đến tìm coi nó nằm nơi đâu trong danh sách links đơn tại vị trí h(k) kia 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 nên 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ới DeleteAfter cũng sẽ được mình trình diễn trong bài Danh sách link đơn vào C++ rồi đề xuất mình sẽ không còn giả thích hợp 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 đơn giản, bạn chỉ việc duyệt qua mảng, mỗi phần tử của mảng là một trong những danh sách link đơn, vậy thì chu đáo danh sách links đơn nữa là xong.

void Traverse(Node *p) // chuẩn 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 dữ liệu lớn, việc cấp phép một mảng quá lớn sẽ khiến lãng phí bộ nhớ không đáng có, mặc dù nhiên, việc M lớn đảm bảo việc chạm độ ít xẩy ra do các khóa phân bổ đều. Ngược lại, nếu M nhỏ dại để tiết kiệm ngân sách 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 việc đụng độ xẩy ra với gia tốc cao hơn.

Xem thêm: Cách Đặt Mật Khẩu Máy Tính Hp, Hướng Dẫn Cách Cài Mật Khẩu Cho Laptop, Pc

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 hiệu suất và dung tích lưu trữ.

Tổng kết

Như vậy là trong nội dung bài viết này, mình đã trình làng đến các bạn 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 cần sử 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 bên 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) phường = 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) phường = 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;