因業務需要， 使用stl中的list+hashmap實現了一個容器做緩存；支持lru特性、? 支持O(1)時間的push_back, pop_head, find/delete。

大概實現是 將hashmap的iterator的關鍵部分作為list的元素； 將list的iterator的關鍵部分作為hashmap的value的其中一部分。 hashmap是真正存放數據的。

這樣能夠狠容易的從hashmap::iterator中解析得到對應的list::iterator， 也能夠狠容易的從list::iterator解析得到對應的hashmap::iterator。

其中后者代碼如下：

inline typename HashType::iterator LitToHit(typename ListType::iterator &it){//static typename HashType::iterator hit = m_hash.begin();//只是重用其中的_M_ht_List_node<ListKeyType> * lnode = static_cast<_List_node<ListKeyType> *>(it._M_node);hit._M_cur = lnode->_M_data;return hit;}
這個函數用的非常頻繁。 測試中發現這個函數非常影響性能，當時十分不理解， 以為就是很簡單的O(1)而已。 仔細看代碼之后才發現其中玄機。

hashmap一維是個指針數組， 數組元素指向沖突處理鏈表。begin遍歷該數組， 返回第一個指針非空的數組下標指向的數據節點。 當元素較少時， begin可能會非常慢、一直遍歷到數組尾部才能找到第一個數據節點。

解決方法是使用static變量即可。

代碼如下，以后會有很多地用到，貼出以做備忘。

#pragma once//queue。 插入時key唯一。 O(1)的pushback, pophead, find/delete#include <list> #include <ext/hash_map>using namespace std; using namespace __gnu_cxx;template <typename Key, typename Value> class UniqQueue { public:class ValueNode;typedef hash_map<Key, ValueNode> HashType;typedef _Hashtable_node<pair<const Key, ValueNode> > * ListKeyType;typedef list<ListKeyType> ListType;typedef Key KeyType;typedef Value ValueType;typedef UniqQueue ThisType;class ValueNode{public:_List_node<ListKeyType> *list; // lru鏈表中的位置Value value; // 元素ValueNode():list(NULL), value() {}ValueNode(const ValueNode &r):list(r.list), value(r.value){}private:ValueNode &operator=(const ValueNode &r);//disable};private: HashType m_hash;ListType m_list;pthread_mutex_t m_lock;pthread_cond_t m_cond;public:UniqQueue():m_hash(1000000){pthread_cond_init(&m_cond, NULL);pthread_mutex_init(&m_lock, NULL);}~UniqQueue(){pthread_cond_destroy(&m_cond);pthread_mutex_destroy(&m_lock);}pthread_mutex_t & lock(){return m_lock;}void push_back(const Key & k, const Value &content){ pthread_mutex_lock(&m_lock);pair<typename HashType::iterator, bool> it = m_hash.insert(make_pair(k, ValueNode()));it.first->second.value = content;if(it.second == true)//cache中新加的數據{ typename ListType::iterator lii = m_list.insert(m_list.end(), GetListNode(it.first));SetList(it.first, lii);}else{}pthread_cond_signal(&m_cond);pthread_mutex_unlock(&m_lock);return;}Value peak_head(){Value vn;typename ListType::iterator lii;typename HashType::iterator hit;// pthread_cleanup_push(Cleanup, this);pthread_mutex_lock(&m_lock);while(m_list.size() == 0){pthread_cond_wait(&m_cond, &m_lock);}lii = m_list.begin();hit = LitToHit(lii);//can not define Value vn; here.. because of cond_wait?? vn = hit->second.value;pthread_mutex_unlock(&m_lock);// pthread_cleanup_pop(0);return vn;}Value peak_head_nolock(){Value vn;typename ListType::iterator lii = m_list.begin();typename HashType::iterator hit = LitToHit(lii);vn = hit->second.value;return vn;}Value find(const Key &k){Value v;pthread_mutex_lock(&m_lock);typename HashType::iterator it = m_hash.find(k);if(it == m_hash.end()) ;elsev = it->second.value;pthread_mutex_unlock(&m_lock);return v;}void pop_head(bool want = true){if(want) pthread_mutex_lock(&m_lock);typename ListType::iterator lii = m_list.begin();typename HashType::iterator hit = LitToHit(lii);m_list.erase(lii);m_hash.erase(hit);if(want) pthread_mutex_unlock(&m_lock);}private://lock helperstatic void Cleanup(void *arg){ThisType *tis = (ThisType *)arg;pthread_mutex_unlock(&(tis->m_lock));}private: //iterator tool functionsinline ListKeyType GetListNode(typename HashType::iterator &v){return v._M_cur;}inline typename HashType::iterator LitToHit(typename ListType::iterator &it){static typename HashType::iterator hit = m_hash.begin();//只是重用其中的_M_ht_List_node<ListKeyType> * lnode = static_cast<_List_node<ListKeyType> *>(it._M_node);hit._M_cur = lnode->_M_data;return hit;}inline void SetList(typename HashType::iterator &v, typename ListType::iterator it){v->second.list = static_cast<_List_node<ListKeyType> * >(it._M_node);} };
當時測試場景：

1寫線程從1開始遞增key，不停得push_back；? 1讀線程不停的peak_head+pop_head。

異常現象：

1）push_back線程的pthread_mutex_lock獲取鎖操作時間越來越長， 從0-1us變為幾十個ms。

2）peak_head+pop_head非常消耗cpu，幾乎吃滿cpu。 而寫線程只占30%左右的cpu。

3）內存用完后變得更慢， push_back大概每秒只能push 30個左右。

4）其他等等

當時百思不得其解，甚至懷疑pthread contidion的效率、 系統環境有問題。

其實1和2都已經明確的指向了同一個問題了。 1獲取鎖慢， 肯定是其他線程持有鎖的時間長導致的。 2吃滿cpu，正好說明獲取鎖后做大量運算需要時間長。

就是peadk_head慢。 慢在哪， 仔細分析就是hashmap::begin慢

總結

以上是生活随笔為你收集整理的hashmap::begin() 坑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。