c++ - 重新散列时锁定散列映射
问题描述
我正在尝试创建一个线程安全的哈希映射。我为哈希映射中的每个存储桶都有一个互斥体向量,以支持哈希映射中每个条目的读写器锁。
但是,当我想重新散列哈希映射时,我想锁定整个映射,以便在重新散列期间不会发生读/写。
我想我需要一个额外的互斥锁,但是我的 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);
}
};
解决方案
这是多虑了。保护整个容器的单个互斥体就足够了。但是如果你坚持实现这种复杂的设计:
- 将 a
std::shared_mutex
用于您的全局容器互斥锁。 - 单独的 getter/putter 需要在全局互斥锁上获取共享锁,然后才能锁定其单独的哈希桶。
- Rehash 获得一个排他锁,它会阻塞所有的 getter/putter。
推荐阅读
- api - 如何在 Postman 中使用第一个 API 响应作为第二个 API 的请求?
- reactjs - ReactJS:检查 `MainRouter` 的渲染方法。错误
- powershell - 递归地向文件夹授予域用户/组权限
- docker - kubernetes 将来自服务的传出 http 流量重定向到 localhost:port
- java - 即使在创建数据库和表之后,SQL(查询)错误或缺少数据库
- java - 如何修改约束布局中的链长?
- node.js - 部署对话流示例代码时出错
- firebase - Vue Firebase:currentUser 为空
- html - 将对象从视图传递到控制器
- cumulocity - 如何在 cumulocity 中使用 API 将“c8y_Address”属性添加到设备?