hashmap::begin() 坑

因业务需要， 使用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() 坑的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。