Я пытаюсь создать хеш-карту, которая является поточно-ориентированной. У меня есть вектор мьютексов для каждого сегмента в хэш-карте для поддержки блокировки чтения-записи для каждой записи в хэш-карте.
Однако, когда я хочу перефразировать хэш-карту, я хочу заблокироватьвся карта, так что во время перефразирования не может произойти чтение / запись.
Я думаю, что мне нужен дополнительный мьютекс, однако мои методы Gets / Puts также должны получать этот мьютекс? Как заблокировать другие потоки от чтения / записи, только когда происходит перефразирование, и не блокировать друг друга, когда происходит только запись и чтение?
Так выглядит мой текущий класс хэш-таблиц:
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);
}
};