学步园

编程实现哈希存储算法的简单实现实例。

通过编写一个简单的哈希实例来加强对哈希算法的理解。下面实例包括存储与查找算法。拉链法解决冲突问题。

如果时间长了对哈希算法的理论知识不够了解，可以先阅读前面转载的两篇文档：

字符串哈希到整数函数，算法：http://blog.csdn.net/hzhsan/article/details/25552153

Hash算法冲突解决方法分析：http://blog.csdn.net/hzhsan/article/details/25555127

// 假设现在要实现一个存储学生信息的hash内存表，封装hash值的存储与获取，并通过拉链法解决地址冲突。
#include <stdio.h>
#include <string>
using std::string;

// 定义hash表初始开辟内存空间元素的个数。这里只用1000做测试。
#define BUFF_COUNT 1000

// 学生信息结构
struct Student_info
{
        string name;
        int age;
};

// 实际存储元素结构
struct Store_info
{
       string key;                                     // 将key做存储，目的是为了判断冲突问题
        struct Student_info stu;                        // 实际需要存储的数据信息
        Store_info *pNext;                              // 当发生冲突时用以形成链表
        Store_info():pNext(NULL){}
};
Store_info *buff;		//之后用于申请大片存储数据的内存

// BKDRHash函数，得到一个字符串所对应的整型，用于计算hash值。此函数见：http://blog.csdn.net/hzhsan/article/details/25552153
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF);
}

bool Hash_set(string key, const Student_info& student)
{
        // 计算实际的hash值，除以BUFF_COUNT是为了使hash的映射到一个较小的范围。
        unsigned int hash_index =  BKDRHash((char*)key.c_str())%BUFF_COUNT;

        Store_info *pStore = &buff[hash_index];
        while ((pStore->key != key) && (pStore->pNext != NULL)) // if some key exists, store to the link list
        {
                pStore = pStore->pNext;
        }

        if (pStore->key == key)
        {
                pStore->stu = student;
                return true;
        }

        Store_info *pNewStore = new Store_info();
        pNewStore->key = key;
        pNewStore->stu = student;

        pStore->pNext = pNewStore;
        return true;
}

Student_info* Hash_get(string key)
{
        unsigned int hash_index =  BKDRHash((char*)key.c_str())%BUFF_COUNT;
        Store_info *pStore = &buff[hash_index];
        if ((pStore->key != key) && (pStore->pNext != NULL))
        {
                pStore = pStore->pNext;
        }

        if (pStore->key == key)
        {
                return &pStore->stu;
        }
        return NULL;
}

int main()
{
        buff = new Store_info[BUFF_COUNT];
        Student_info stu1;
        stu1.name = "hu";
        stu1.age = 11;
        Hash_set("key1", stu1);

        Student_info stu2 = stu1;
        stu2.age = 22;
        Hash_set("key2", stu2);

        Student_info stu3 = stu1;
        stu3.age = 33;
        Hash_set("key2", stu3);

        Student_info *pstu = Hash_get("key2");
        if (pstu == NULL)
        {
                        printf("ERROR:Get NULL\n");
        }
        else
        {
                        printf("name:%s\nage:%d\n",pstu->name.c_str(),pstu->age);
        }

        printf("end~\n");
        delete[] buff;// 这里是有问题的，会有内存泄漏，解决方法：可以对每个结点的析构函数进行完善。那就可以了。
        return 0;
}

如有任何问题，希望各位指正，谢谢。