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;
- }
- }
以上示例主要实现思路是, 每个 KEY 值经 hash 变换后生成对应的 hashvalue, 由 hashvalue 可在数组所构成的所有 "桶" 中找对指定的桶, 再遍历桶中所有的 KEY 值, 直到找到为止.
来源: https://www.cnblogs.com/share-ideas/p/10486107.html