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

编程实现哈希存储算法的简单实现实例。通过编写一个简单的哈希实例来加强对哈希算法的理解。下面实例包括存储与查找算法。拉链法解决冲突问题。如果时间长了对哈希算法的理论知识不够了解，可以先阅读前面转载的两篇文档：字符串哈希到整数函数，算法：http://www.linuxidc.com/Linux/2014-05/101600.htmHash算法冲突解决方法分析：http://www.linuxidc.com/Linux/2014-05/101601.htm--------------------------------------分割线 --------------------------------------2014阿里实习面试题——哈希的原理和Java中HashMap如何实现的 http://www.linuxidc.com/Linux/2014-04/100598.htm哈希连接（hash join）原理 http://www.linuxidc.com/Linux/2013-11/92483.htmC++中对hash_map自定义哈希函数和比较函数的理解 http://www.linuxidc.com/Linux/2012-11/73706.htm--------------------------------------分割线 --------------------------------------// 假设现在要实现一个存储学生信息的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://www.linuxidc.com/Linux/2014-05/101600.htm
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 "）;
}
else
{
printf（"name:%s age:%d ",pstu->name.c_str（）,pstu->age）;
} printf（"end~ "）;
delete[] buff;
return 0;
}如有任何问题，希望各位指正，谢谢。本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-05/101602.htm