HashMap数据结构的C++实现

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值，直到找到为止。