Hash表在计算机的应用编程中是一种很常用的数据结构，很多算法的实现都离不开它。虽然C++11标准模板库中的有hashmap类型的实现，但在工程实践中，若项目本身使用的是较低版本的C++，或是出于性能的考虑，可能需要开发出一套独立的hashmap数据类型，从而能更加方便高效的维护相关业务。出于这种目的，有必要自己梳理一下其实现代码，并分享给大家。
至于hash表实现的原理主要就两种：1、链表法，2、开放地址法。在此以链表法来实现hashmap的数据结构，相关示例代码如下：
//创建HashMap的数据结构类型 template<typename KEY, typename VALUE, unsigned int NUM> class HashMapper { public: struct item { item(const KEY &key, const VALUE& value):first(key),second(value),next(NULL){} item(const KEY &key):first(key),next(NULL){} item():next(NULL){} KEY first; VALUE second; item* next; }; public: HashMapper(); virtual ~HashMapper(); item* Select(const KEY &key); const item* Select(const KEY &key) const; int Insert(const KEY &key, const VALUE& value); int Remove(const KEY &key); VALUE& operator[](const KEY &key); protected: virtual void Key2Hash(const KEY &key, unsigned int &hashvalue) const = 0; item* hash_bucket[NUM]; }; //得到指定key的map节点 Select(const KEY &key) { unsigned int value; Key2Hash(key, value); item* pCur = hash_bucket[value]; while(pCur != NULL) { if (key == pCur->first) { return pCur; } pCur = pCur->next; } return NULL; } // 向hashmap中插入键值对 Insert(const KEY &key, const VALUE& value) { unsigned int hashvalue; Key2Hash(key, hashvalue); //hash位置没有内容 if (hash_bucket[hashvalue] == NULL) { hash_bucket[hashvalue] = new item(key, value); return 0; } item* pCur = hash_bucket[hashvalue]; do { if (key == pCur->first) { return -1; } if (pCur->next == NULL) { break; } else { pCur = pCur->next; } } while(1); pCur->next = new item(key, value); return 0; } //删除指定key值的节点 Remove(const KEY &key) { unsigned int hashvalue; Key2Hash(key, hashvalue); item* pCur = hash_bucket[hashvalue]; item* pLast = NULL; while(pCur != NULL) { if (key == pCur->first) { if (pLast == NULL) { hash_bucket[hashvalue] = pCur->next; } else { pLast->next = pCur->next; } delete pCur; return 0; } pLast = pCur; pCur = pCur->next; } return -1; } //由字符串转化为hash值，如若要求保证唯一性，则可利用MD5来转化成u long long类型 void Key2Hash(const KEY & index, unsigned int & hashvalue) { hashvalue = 0; int len = index.strlen(); for (int i = 0; i < len; ++i) { hashvalue = ((unsigned char)index[i] + hashvalue) % hashsize; } }