Helpex - Trao đổi & giúp đỡ Đăng nhập
0

Tôi đang cố gắng phát triển bản đồ băm an toàn theo luồng. Để hỗ trợ khóa trình đọc-ghi cho từng phần tử trong bản đồ băm, tôi có một vectơ các mutexes cho mỗi nhóm trong bản đồ băm.

Tuy nhiên, khi tôi băm lại bản đồ băm, tôi muốn khóa toàn bộ bản đồ sao cho không có hoạt động đọc hoặc ghi nào xảy ra trong suốt quá trình băm lại.

Tôi tin rằng tôi cần thêm một mutex; nhưng, các phương thức Gets/Puts của tôi có yêu cầu mutex này không? Làm cách nào tôi có thể ngăn các luồng khác tiến hành Đọc/Ghi trừ khi quá trình băm lại đang diễn ra chứ không phải khi chỉ đơn giản là viết và đọc? (Giống như trong ví dụ này)

Đây là bố cục của lớp bảng băm hiện tại của tôi:

template<typename K, typename T>
class HashTable {
    int num_buckets_;
    double threshold_ratio_;
    int num_elements_;
    vector<vector<pair<T, K>>> table_;
    vector<mutex> read_write_locks_;
    mutex mu_;

    int GetHash(const K& key) {
        return hash<K>{}(key) % num_buckets_;
    }

    void Rehash() {
        scoped_lock<mutex> lock(mu_);   // Lock the whole table?
        cout << "Threshold Value has been reached. Rehashing...\n";

        vector<vector<T>> new_table(2 * num_buckets_);
        num_buckets_ = 2 * num_buckets_;

        vector<mutex> new_mutexes(2 * num_buckets_);
        read_write_locks_.swap(new_mutexes);
        // TODO : Implementation
    }

public:
    explicit HashTable(int num_buckets) : num_buckets_(num_buckets), threshold_ratio_(0.75), num_elements_(0) {
        table_.resize(num_buckets);
        vector<mutex> temp(num_buckets);
        read_write_locks_.swap(temp);
    }

    void Put(const K& key, const T& val) {
        ++num_elements_;
        if (static_cast<double>(num_elements_) / num_buckets_ > threshold_ratio_) {
            Rehash();
        }
        int hash_val = GetHash(key);
        scoped_lock<mutex> write_lock(read_write_locks_[hash_val]);
        cout << "Putting Key: " << key << ", Hash: "<< hash_val << "  with Value: " << val << '\n';
        table_[hash_val].push_back({val, key}); //TODO: For existing keys it should replace the value, not create a new entry
    }

    T Get(const K& key) {
        int hash_val = GetHash(key);
        scoped_lock<mutex> read_lock(read_write_locks_[hash_val]);

        if (table_[hash_val].size() >= 1) {
            for (const auto& elem : table_[hash_val]) {
                if (elem.second == key) {
                    cout << "Key: " << key << " gets value: " << elem.first << '\n';
                    return elem.first;
                }
            }
        }
        cerr << "Unable to find key in hash table. Terminating Program. \n";
        exit(EXIT_FAILURE);
    }
};
0 hữu ích 0 bình luận 546 xem chia sẻ
loading
Không tìm thấy câu trả lời bạn tìm kiếm? Duyệt qua các câu hỏi được gắn thẻ c++ hashmap , hoặc hỏi câu hỏi của bạn.

Có thể bạn quan tâm

loading