Cùng tìm hiểu về bucket trong unordered_map C++. Bạn sẽ học được khái niệm Bucket trong C++ là gì cũng như các cách xử lý bucket trong unordered_map C++ sau bài học này.

Bucket trong C++ là gì

Bucket trong C++ là một không gian bộ nhớ trong bảng hash của container (unordered_map), trong đó các phần tử sẽ được chỉ định dựa trên giá trị hash của khóa của chúng. Phạm vi giới hạn hợp lệ của các bucket là từ 0 đến bucket_count - 1.

Trong bài Unordered_map trong C++ là gì chúng ta đã biết các phần tử trong unordered_map lại được lưu trữ dựa trên giá trị hash của khóa chứ không phải dựa trên thứ tự của các khóa.

Và các giá trị hash của khóa này sẽ được quản lý theo bucket mà Kiyoshi vừa giới thiệu ở trên.

Lấy vị trí bucket chứa phần tử có khóa chỉ định bằng hàm unordered_map bucket

Hàm bucket là một hàm thành viên trong class std:unordered_map, có tác dụng lấy vị trí bucket chứa phần tử có khóa chỉ định.

Chúng ta sử dụng hàm bucket để lấy số bucket chứa phần tử có khóa chỉ định trong unordered_map C++ với cú pháp như sau:

Trong đó mp là unordered_map và k là khóa cần tìm số bucket chứa phần tử được xác định bởi nó.

Hàm bucket sẽ trả về vị trí (số thứ tự) của bucket chứa phần tử có khóa k được chỉ định.

Ví dụ cụ thể, chúng ta lấy số bucket chứa phần tử có khóa chỉ định bằng hàm bucket như sau:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main ()
{
    unordered_map<string,int> mymap = {
                { "alpha", 10 },
                { "beta", 20 },
                { "gamma", 30 } };

  for (auto& x: mymap) {
    std::cout << "Phần tử [" << x.first << ":" << x.second << "]";
    std::cout << " nằm tại bucket số #" << mymap.bucket (x.first) << std::endl;
  }

  return 0;
}

Và kết quả:

Phần tử [gamma:30] nằm tại bucket số #2
Phần tử [beta:20] nằm tại bucket số #0
Phần tử [alpha:10] nằm tại bucket số #0

Lấy số bucket tạo ra bởi unordered_map bằng hàm bucket_count

Hàm bucket_count là một hàm thành viên trong class std:unordered_map, có tác dụng lấy số bucket được tạo ra từ unordered_map.

Chúng ta sử dụng hàm bucket_count để lấy số bucket có trong unordered_map C++ với cú pháp như sau:

Trong đó mp là unordered_map cần đếm số bucket đã được tạo ra từ nó.

Hàm bucket_count sẽ trả về số bucket được tạo ra từ unordered_map chỉ định.

Ví dụ cụ thể, chúng ta lấy số bucket tạo ra bởi unordered_map bằng hàm bucket_count như sau:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main ()
{
    unordered_map<char,int> mp;
    mp.insert(make_pair('a', 1));
    mp.insert(make_pair('b', 2));
    mp.insert(make_pair('c', 3));  
    mp.insert(make_pair('d', 1));
    mp.insert(make_pair('e', 2));

    unsigned n = mp.bucket_count();
    
    cout << "Có tất cả " << n << " buckets.\n";
    
    for (unsigned i=0; i<n; ++i) {
        cout << "bucket #" << i << " chứa: ";
        for (auto it = mp.begin(i); it!=mp.end(i); ++it)
            cout << "[" << it->first << ":" << it->second << "] ";
        cout << "\n";
    }

  return 0;
}

Và kết quả:

Có tất cả 13 buckets.
bucket #0 chứa: 
bucket #1 chứa: 
bucket #2 chứa: 
bucket #3 chứa: 
bucket #4 chứa: 
bucket #5 chứa: 
bucket #6 chứa: [a:1] 
bucket #7 chứa: [b:2] 
bucket #8 chứa: [c:3] 
bucket #9 chứa: [d:1] 
bucket #10 chứa: [e:2] 
bucket #11 chứa: 
bucket #12 chứa: 

Lấy số phần tử lưu trữ trong bucket bằng hàm bucket_size

Hàm bucket_size là một hàm thành viên trong class std:unordered_map, có tác dụng lấy số phần tử của unordered_map được lưu trữ trong bucket.

Chúng ta sử dụng hàm bucket_size để lấy số phần tử lưu trữ trong bucket với cú pháp như sau:

Trong đó mp là unordered_map và i là số thứ tự của bucket cần đếm số phần tử trong nó.

Hàm bucket_size sẽ trả về số phần tử của unordered_map được lưu trữ trong bucket có số thứ tự chỉ định.

Ví dụ cụ thể, chúng ta lấy số phần tử lưu trữ trong bucket bằng hàm bucket_size như sau:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main ()
{
    unordered_map<char,int> mp;
    mp.insert(make_pair('a', 1));
    mp.insert(make_pair('b', 2));
    mp.insert(make_pair('c', 3));  
    mp.insert(make_pair('d', 1));
    mp.insert(make_pair('e', 2));

    unsigned nbuckets = mp.bucket_count();
    
    cout << "Có tất cả " << nbuckets << " buckets.\n";
        
    for (unsigned i=0; i<nbuckets; ++i) {
        cout << "bucket #" << i << " có " << mp.bucket_size(i) << " phần tử.\n";
    }

  return 0;
}

Và kết quả:

Có tất cả 13 buckets.
bucket #0 có 0 phần tử.
bucket #1 có 0 phần tử.
bucket #2 có 0 phần tử.
bucket #3 có 0 phần tử.
bucket #4 có 0 phần tử.
bucket #5 có 0 phần tử.
bucket #6 có 1 phần tử.
bucket #7 có 1 phần tử.
bucket #8 có 1 phần tử.
bucket #9 có 1 phần tử.
bucket #10 có 1 phần tử.
bucket #11 có 0 phần tử.
bucket #12 có 0 phần tử.

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn về bucket trong C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.

URL Link

https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/unordered-map-trong-cpp/bucket-trong-unordered-map-cpp/