CHI TIẾT BÀI HỌC BẢNG BĂM
Bảng băm là gì?
Bảng băm tuyệt HashTable là một cấu trúc mà khi người dùng thực hiện nay truy xuất 1 phần tử qua khóa thì nó sẽ tiến hành ánh xạ vào trải qua hàm băm (Hash function).
Bạn đang xem: Chi tiết bài học bảng băm
Quá trình ánh xạ khóa vào bảng băm được thực hiện thông qua hàm băm (Hashing). Một bảng băm xuất sắc cần phải có hàm băm tốt. Bảng băm là một trong mảng tất cả M địa chỉ được đặt số từ 0 đến M – 1.
Như chúng ta có thể thấy vào hình, các khóa như 7, 17 chạm độ nhau thì chúng sẽ được thêm vào danh sách link ở h(k) = M. Tựa như các khóa 4, 19 cũng trở nên đụng cùng được sản xuất danh sách link ở 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ư đã nói, phương pháp kết nối trực tiếp dùng danh sách link đơn, các phần tử bị va độ tại phần tử i vào bảng băm thì sẽ được thêm vào danh sách link đơn tại i vào bảng băm. Do đó, một phần tử vào bảng băm có cấu trúc 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 trong những mảng chứa những 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
HashTable mHashTable;Các chúng ta có thể dễ dàng thấy một nút trong bảng là một trong những con trỏ trỏ đến một Node, như vậy, chúng ta cần phải lập chúng bởi NULL nhằm tránh gặp gỡ lỗi. Mình sẽ sở hữu được hàm khởi tạo bảng như sau:
void InitHashTable(HashTable &HT) for (int i = 0; i M; i++) HT = NULL;Hàm băm
Như đã nói sinh hoạt trên, để đơn giản 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 1 nút, ta đề nghị 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 ở đoạn h(k) đó. Bài toán đụng độ đã được xử lý do nếu va độ thì khóa sẽ được tự chế tạo sau danh sách link đơn. Mình sẽ có đượ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 liên kết đơn, mình đã 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* p = l; while (p != NULL && p->next != NULL) p. = p->next; p->next = newNode;
Tìm kiếm một khóa vào bảng băm
Để search kiếm một khóa vào bảng băm, ta cũng triển khai xác xác định trí h(k), tiếp đến ta tiến hành tìm kiếm trong danh sách liên kết tại vị trí h(k) trong bảng băm.Xem thêm: Cách Đăng Ký Tạo Gmail Không Cần Số Điện Thoại 2015, Cách Lập Email Không Cần Số Điện Thoại
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 ra khỏi bảng băm
Để xóa một phần tử ra khỏi bảng băm, đầu tiên ta cũng phải khẳng định h(k), sau đó tìm xem 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; // lưu lại lại địa chỉ cửa hàng của thành phần trước đó phường = 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 đã được mình trình bày trong bài Danh sách link đơn vào C++ rồi phải mình sẽ không còn giả 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 rất solo giản, bạn chỉ cần duyệt qua mảng, mỗi phần tử của mảng là một trong những danh sách links đơn, vậy thì chăm chút danh sách link đơn nữa là xong.void Traverse(Node *p) // trông nom 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ẽ khiến lãng phí bộ nhớ không đáng có, mặc dù nhiên, bài toán M lớn bảo vệ việc chạm độ ít xảy ra do các khóa phân bổ đều. Ngược lại, giả dụ M nhỏ tuổi để tiết kiệm ngân sách và chi phí bộ nhớ, câu hỏi này sẽ làm giảm nă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.
Do vậy, khi thao tác với bảng băm, các bạn cầ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 nội dung 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 lập bảng băm bởi phương thức liên kết trực tiếp dùng danh sách links đơn. Nếu chúng ta có ngẫu nhiên ý kiến, góp phần nào, đừng ngần ngại phản hồi phía bên dưới bài viết nha. Cảm ơn các bạn đã theo dõi bài bác viết!
