分塊鎖與unordered_map
分塊鎖不可以和unordered_map聯用
unordered_map 的rehash機制
unordered_map 的底層數據結構為HashTable。
HashTable有rehash機制，觸發的時機為"Rehash will occur only if the new number of buckets respect the unordered_map maximum load factor."template<typename _Key, typename _Value,
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits>
void
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::true_type)
{
__bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin()._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
while (__p)
{
__node_type* __next = __p->_M_next();
std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
if (!__new_buckets[__bkt])
{
__p->_M_nxt = _M_before_begin()._M_nxt;
_M_before_begin()._M_nxt = __p;
__new_buckets[__bkt] = &_M_before_begin();
if (__p->_M_nxt)
__new_buckets[__bbegin_bkt] = __p;
__bbegin_bkt = __bkt;
}
else
{
__p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
__new_buckets[__bkt]->_M_nxt = __p;
}
__p = __next;
}
_M_deallocate_buckets(_M_buckets, _M_bucket_count);//銷毀舊內存地址
_M_bucket_count = __n;//更新桶數
_M_buckets = __new_buckets;//指向新內存地址
}
如上，rehash操作時存在舊地址數據拷貝到新地址，及舊地址銷毀、更新地址指向的過程。
當多線程環境下分塊鎖+unordered_map使用如下：
std::unordered_map<std::string,MidInfo*> mid_tag_cache_
int InsertMidTagToCache(MidInfo* info) {
std::string &mid = info->mid;
uint32_t hash = Hash(mid.c_str(),mid.length(),0);
int mutex_index = hash % mid_tag_lock_num_;
info->mid_hash = hash;
std::mutex &mutex_lock = mid_tag_mutex_[mutex_index];
std::lock_guard<std::mutex> lock(mutex_lock);
mid_tag_cache_[mid]=info;
return 0;
}
int GetMidInfo(std::string &mid,MidInfo* mid_info)const {
uint32_t hash = Hash(mid.c_str(),mid.length(),0);
int mutex_index = hash % mid_tag_lock_num_;
std::mutex &mutex_lock = mid_tag_mutex_[mutex_index];
int ret = 0;
std::lock_guard<std::mutex> lock(mutex_lock);
auto iter = mid_tag_cache_.find(mid);
if(iter != mid_tag_cache_.end()) {
MidTagInfo* cache_info = iter->second;
}else {
ret = NOT_EXIST;
}
return ret;
}
在unordered_map觸發rehash後，存在程序core的風險。
問題解決
在閱讀levelDb lrucache代碼，結合此問題，理解了lrucache的設計思想。
unordered_map使用心得
unordered_map默認的桶數為11 ，load_factor是1。
在實際使用中如果需要存儲有大量數據，頻繁的rehash會非常影響性能。
解決辦法是在unordered_map建立時根據實際需要預先設定桶數和元素數避免後期可能的rehashint main() {
std::unordered_map<int, int> t;
t.reserve(10000000);//預設元素數
t.rehash(10000000);//預設桶數
for (int i = 0; i <= 10000000; ++i) {
t.insert(make_pair(i, 1));
}
}
推薦閱讀：