liuyun827@foxmail.com原创，转载请注明出处：
Key-Value缓存有很多，用的较多的是memcache、redis，他们都是以独立服务的形式运行，在工作中有时需要嵌入一个本地的key-value缓存，当然已经有LevelDb等，但感觉还是太重量级了。
本文实现了一种超级轻量的缓存，
1、实现代码仅仅需要400行；
2、性能高效，value长度在1K时测试速度在每秒200万左右
3、缓存是映射到文件中的，所以没有malloc、free的开销，以及带来的内存泄露、内存碎片等；
4、如果服务挂掉了，重启后缓存内容继续存在；
5、如果把缓存映射到磁盘文件就算机器挂了，缓存中内容还是会存在，当然有可能会出现数据损坏的情况；
6、一定程度上实现了LRU淘汰算法，实现的LRU不是全局的只是一条链上的，所以只能说在一定程序上实现了；
7、稳定，已经在多个项目中运用，线上部署的机器有几十台，运行了大半年了没出过问题；
8、普通的缓存key、value都是字符串的形式，此缓存的key、value都可以是class、struct对象结构使用更方便；
老规矩直接上代码：
template<typename K, typename V>class HashTable{public:HashTable(const char *tablename, uint32_t tableLen, uint32_t nodeTotal);virtual ~HashTable();bool Add(K &key, V &value){AutoLock autoLock(m_MutexLock);//check is existuint32_t nodeId = GetIdByKey(key);if(nodeId != m_InvalidId) return false;nodeId = GetFreeNode();if(nodeId == m_InvalidId) return false;uint32_t hashCode = key.HashCode();Entry *tmpNode = m_EntryAddr + nodeId;tmpNode->m_Key = key;tmpNode->m_Code = hashCode;tmpNode->m_Value = value;uint32_t index = hashCode % m_HeadAddr->m_TableLen;AddNodeToHead(index, nodeId);return true;}bool Del(K &key){AutoLock autoLock(m_MutexLock);uint32_t nodeId = GetIdByKey(key);if(nodeId == m_InvalidId) return false;uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;return RecycleNode(index, nodeId);}bool Set(K &key, V &value){AutoLock autoLock(m_MutexLock);uint32_t nodeId = GetIdByKey(key);if(nodeId == m_InvalidId) return false;(m_EntryAddr + nodeId)->m_Value = value;return true;}bool Get(K &key, V &value){AutoLock autoLock(m_MutexLock);uint32_t nodeId = GetIdByKey(key);if(nodeId == m_InvalidId) return false;value = (m_EntryAddr + nodeId)->m_Value;return true;}bool Exist(K &key){AutoLock autoLock(m_MutexLock);uint32_t nodeId = GetIdByKey(key);if(nodeId == m_InvalidId) return false;return true;}uint32_t Count(){AutoLock autoLock(m_MutexLock);return m_HeadAddr->m_UsedCount;}//if exist set else addbool Replace(K &key, V &value){AutoLock autoLock(m_MutexLock);if(Exist(key)) return Set(key, value);else return Add(key, value);}/***************************************************LRU: when visit a node, move it to head ****************************************************///if no empty place,recycle tailbool LruAdd(K &key, V &value, K &recyKey, V &recyValue, bool &recycled){AutoLock autoLock(m_MutexLock);if(Exist(key)) return false;if(Add(key, value)) return true;uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;uint32_t tailId = GetTailNodeId(index);if(tailId == m_InvalidId) return false;Entry *tmpNode = m_EntryAddr + tailId;recyKey = tmpNode->m_Key;recyValue = tmpNode->m_Value;recycled = true;RecycleNode(index, tailId);return Add(key, value);}bool LruSet(K &key, V &value){AutoLock autoLock(m_MutexLock);if(Set(key, value)) return MoveToHead(key);else return false;}bool LruGet(K &key, V &value){AutoLock autoLock(m_MutexLock);if(Get(key, value)) return MoveToHead(key);else return false;}//if exist set else add; if add failed recycle tail than addbool LruReplace(K &key, V &value, K &recyKey, V &recyValue, bool &recycled){AutoLock autoLock(m_MutexLock);recycled = false;if(Exist(key)) return LruSet(key, value);else return LruAdd(key, value, recyKey, recyValue, recycled);}void Clear(){AutoLock autoLock(m_MutexLock);m_HeadAddr->m_FreeBase = 0;m_HeadAddr->m_RecycleHead = 0;m_HeadAddr->m_UsedCount = 0;for(uint32_t i = 0; i < m_HeadAddr->m_TableLen; ++i){(m_ArrayAddr+i)->m_Head = m_InvalidId;(m_ArrayAddr+i)->m_Tail = m_InvalidId;}}int GetRowKeys(vector<K> &keys, uint32_t index){AutoLock autoLock(m_MutexLock);if(index >= m_HeadAddr->m_TableLen) return -1;keys.clear();keys.reserve(16);int count = 0;Array *tmpArray = m_ArrayAddr + index;uint32_t nodeId = tmpArray->m_Head;while(nodeId != m_InvalidId){Entry *tmpNode = m_EntryAddr + nodeId;keys.push_back(tmpNode->m_Key);nodeId = tmpNode->m_Next;++count;}return count;}void *Padding(uint32_t size){AutoLock autoLock(m_MutexLock);if(size > m_HeadSize – sizeof(TableHead)) return NULL;else return m_HeadAddr->m_Padding;}private:static const uint32_t m_InvalidId = 0xffffffff;static const uint32_t m_HeadSize = 1024;struct TableHead{uint32_t m_TableLen;uint32_t m_NodeTotal;uint32_t m_FreeBase;uint32_t m_RecycleHead;uint32_t m_UsedCount;charm_TableName[256];uint32_t m_Padding[0];};struct Array{uint32_t m_Head;uint32_t m_Tail;};struct Entry{V m_Value;K m_Key;uint32_t m_Code;uint32_t m_Next;uint32_t m_Prev;};size_tm_MemSize;uint8_t *m_MemAddr;TableHead *m_HeadAddr;Array*m_ArrayAddr;Entry*m_EntryAddr;ThreadMutex m_MutexLock;bool MoveToHead(K &key);uint32_t GetIdByKey(K &key);void AddNodeToHead(uint32_t index, uint32_t nodeId);bool MoveNodeToHead(uint32_t index, uint32_t nodeId);bool RecycleNode(uint32_t index, uint32_t nodeId);uint32_t GetTailNodeId(uint32_t index);uint32_t GetFreeNode();DISABLE_COPY_AND_ASSIGN(HashTable);};template<typename K, typename V>HashTable<K, V>::HashTable(const char *tablename, uint32_t tableLen, uint32_t nodeTotal){AbortAssert(tablename != NULL);m_MemSize = m_HeadSize + tableLen*sizeof(Array) + nodeTotal*sizeof(Entry);m_MemAddr = (uint8_t*)MemFile::Realloc(tablename, m_MemSize);AbortAssert(m_MemAddr != NULL);m_HeadAddr = (TableHead*)(m_MemAddr);m_ArrayAddr = (Array*)(m_MemAddr + m_HeadSize);m_EntryAddr = (Entry*)(m_MemAddr + m_HeadSize + tableLen*sizeof(Array));m_HeadAddr->m_TableLen = tableLen;m_HeadAddr->m_NodeTotal = nodeTotal;strncpy(m_HeadAddr->m_TableName, tablename, sizeof(m_HeadAddr->m_TableName));if(m_HeadAddr->m_UsedCount == 0)//if first use init array to invalid id{for(uint32_t i = 0; i < tableLen; ++i){(m_ArrayAddr+i)->m_Head = m_InvalidId;(m_ArrayAddr+i)->m_Tail = m_InvalidId;}m_HeadAddr->m_FreeBase = 0;m_HeadAddr->m_RecycleHead = 0;}}template<typename K, typename V>HashTable<K, V>::~HashTable(){MemFile::Release(m_MemAddr, m_MemSize);}template<typename K, typename V>bool HashTable<K, V>::MoveToHead(K &key){uint32_t nodeId = GetIdByKey(key);uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;return MoveNodeToHead(index, nodeId);}template<typename K, typename V>uint32_t HashTable<K, V>::GetIdByKey(K &key){uint32_t hashCode = key.HashCode();uint32_t index = hashCode % m_HeadAddr->m_TableLen;Array *tmpArray = m_ArrayAddr + index;uint32_t nodeId = tmpArray->m_Head;while(nodeId != m_InvalidId){Entry *tmpNode = m_EntryAddr + nodeId;if(tmpNode->m_Code == hashCode && key.Equals(tmpNode->m_Key)) break;nodeId = tmpNode->m_Next;}return nodeId;}template<typename K, typename V>void HashTable<K, V>::AddNodeToHead(uint32_t index, uint32_t nodeId){if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return;Array *tmpArray = m_ArrayAddr + index;Entry *tmpNode = m_EntryAddr + nodeId;if(m_InvalidId == tmpArray->m_Head){tmpArray->m_Head = nodeId;tmpArray->m_Tail = nodeId;}else{tmpNode->m_Next = tmpArray->m_Head;(m_EntryAddr + tmpArray->m_Head)->m_Prev = nodeId;tmpArray->m_Head = nodeId;}}template<typename K, typename V>bool HashTable<K, V>::MoveNodeToHead(uint32_t index, uint32_t nodeId){if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return false;Array *tmpArray = m_ArrayAddr + index;Entry *tmpNode = m_EntryAddr + nodeId;//already headif(tmpArray->m_Head == nodeId){return true;}uint32_t nodePrev = tmpNode->m_Prev;uint32_t nodeNext = tmpNode->m_Next;(m_EntryAddr+nodePrev)->m_Next = nodeNext;if(nodeNext != m_InvalidId){(m_EntryAddr+nodeNext)->m_Prev = nodePrev;}else{tmpArray->m_Tail = nodePrev;}tmpNode->m_Prev = m_InvalidId;tmpNode->m_Next = tmpArray->m_Head;(m_EntryAddr + tmpArray->m_Head)->m_Prev = nodeId;tmpArray->m_Head = nodeId;return true;}template<typename K, typename V>bool HashTable<K, V>::RecycleNode(uint32_t index, uint32_t nodeId){if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return false;Array *tmpArray = m_ArrayAddr + index;Entry *tmpNode = m_EntryAddr + nodeId;uint32_t nodePrev = tmpNode->m_Prev;uint32_t nodeNext = tmpNode->m_Next;if(nodePrev != m_InvalidId){(m_EntryAddr + nodePrev)->m_Next = nodeNext;}else{tmpArray->m_Head = nodeNext;}if(nodeNext != m_InvalidId){(m_EntryAddr + nodeNext)->m_Prev = nodePrev;}else{tmpArray->m_Tail = nodePrev;}(m_EntryAddr+nodeId)->m_Next = m_HeadAddr->m_RecycleHead;m_HeadAddr->m_RecycleHead = nodeId;–(m_HeadAddr->m_UsedCount);return true;}template<typename K, typename V>uint32_t HashTable<K, V>::GetTailNodeId(uint32_t index){if(index >= m_HeadAddr->m_TableLen) return m_InvalidId;Array *tmpArray = m_ArrayAddr + index;return tmpArray->m_Tail;}template<typename K, typename V>uint32_t HashTable<K, V>::GetFreeNode(){uint32_t nodeId = m_InvalidId;if(m_HeadAddr->m_UsedCount < m_HeadAddr->m_FreeBase)//get from recycle list{nodeId = m_HeadAddr->m_RecycleHead;m_HeadAddr->m_RecycleHead = (m_EntryAddr+nodeId)->m_Next;++(m_HeadAddr->m_UsedCount);}else if(m_HeadAddr->m_UsedCount < m_HeadAddr->m_NodeTotal)//get from free mem{nodeId = m_HeadAddr->m_FreeBase;++(m_HeadAddr->m_FreeBase);++(m_HeadAddr->m_UsedCount);}else{nodeId = m_InvalidId;}//init nodeif(nodeId < m_HeadAddr->m_NodeTotal){Entry *tmpNode = m_EntryAddr + nodeId;memset(tmpNode, 0, sizeof(Entry));tmpNode->m_Next = m_InvalidId;tmpNode->m_Prev = m_InvalidId;}return nodeId;}
，偶尔会想，如果人生真如一场电子游戏，
