{ //进行参数的校验 for(int i=0i<HASH_SIZEi++)
{
HashTable[i].key = 0 HashTable[i].p =NULL }
}//保存到这个链表中//如果这个链表是空的话,就作为头指针,如果这个链表不为空,则添加到吧数字添加到末尾int savedata(struct data_node **head,int num)
{ struct data_node *tmp_p = *head struct data_node *p = (struct data_node *)malloc(sizeof(struct data_node)) if(p == NULL) return 0 if(*head == NULL)
{
*head = p p->count = 1 p->num = num p->next = NULL } else //如果不为空,则这个时候应该添加到链表末尾 { while(tmp_p != NULL)//如果存在,则将这个节点的count加1就可以了 { if(tmp_p->num == num)
{
free(p) ++tmp_p->count return 0 } if(tmp_p->next == NULL) break tmp_p = tmp_p->next }
tmp_p->next = p p->count =1 p->num = num p->next = NULL } return 0}//添加数字//将这个数字经过hash求出结果,然后再保存到相应的链表中//返回真或者假就可以了int add_hash(hash_node *HashTable,int num)
{ int mod = do_hash(num) return savedata(&HashTable[mod].p,num)}int main()
{ int num = 100 hash_node *H = HashTable InitHashTable(H) add_hash(H,num) add_hash(H,num) add_hash(H,3) add_hash(H,1) add_hash(H,4) //在这里我们可以发现一个好的hash函数是多么的重要,如果hash函数不好造成很多冲突的话,效率并不会提高很多的,理想的情况是冲突几乎没有 //这也就是设计hash函数的精髓所在 return 0}
Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。Hash算法在信息安全方面的应用主要体现在以下的3个方面:文件校验、数字签名、鉴权协议程程序实现// 说明:Hash函数(即散列函数)在程序设计中的应用目标 ------ 把一个对象通过某种转换机制对应到一个//size_t类型(即unsigned long)的整型值。// 而应用Hash函数的领域主要是 hash表(应用非常广)、密码等领域。// 实现说明:// ⑴、这里使用了函数对象以及泛型技术,使得对所有类型的对象(关键字)都适用。// ⑵、常用类型有对应的偏特化,比如string、char*、各种整形等。// ⑶、版本可扩展,如果你对某种类型有特殊的需要,可以在后面实现专门化。// ⑷、以下实现一般放在头文件中,任何包含它的都可使用hash函数对象。//------------------------------------实现------------------------------------------------#include <string>using std::stringinlinesize_thash_str(const char* s){unsigned long res = 0for (*s++s)res = 5 * res + *sreturnsize_t(res)}template <class Key>struct hash{size_toperator () (const Key&k) const}// 一般的对象,比如:vector<queue<string>>;的对象,需要强制转化template <class Key >size_thash<Key>::operator () (const Key&k) const{size_tres = 0size_tlen = sizeof(Key)const char* p = reinterpret_cast<const char*>(&k)while (len--){res = (res<<1)^*p++}return res}// 偏特化template<>size_thash<string >::operator () (const string&str) const{return hash_str(str.c_str())}typedef char* PChartemplate<>size_thash<PChar>::operator () (const PChar&s) const{return hash_str(s)}typedef const char* PCChartemplate<>size_thash<PCChar>::operator () (const PCChar&s) const{return hash_str(s)}template<>size_t hash<char>::operator () (const char&x) const { return x}template<>size_t hash<unsigned char>::operator () (const unsigned char&x) const { return x}template<>size_t hash<signed char>::operator () (const signed char&x) const { return x}template<>size_t hash<short>::operator () (const short&x) const { return x}template<>size_t hash<unsigned short>::operator () (const unsigned short&x) const { return x}template<>size_t hash<int>::operator () (const int&x) const { return x}template<>size_t hash<unsigned int>::operator () (const unsigned int&x) const { return x}template<>size_t hash<long>::operator () (const long&x) const { return x}template<>size_t hash<unsigned long>::operator () (const unsigned long&x) const { return x}// 使用说明://// ⑴、使用时首先由于是泛型,所以要加上关键字类型。//// ⑵、其次要有一个函数对象,可以临时、局部、全局的,只要在作用域就可以。//// ⑶、应用函数对象作用于对应类型的对象。//----------------------- hash函数使用举例 -------------------------#include <iostream>#include <vector>#include <string>using namespace stdint main(){vector<string>vstr⑵;vstr[0] = "sjw"vstr[1] = "suninf"hash<string>strhash// 局部函数对象cout <<" Hash value: " <<strhash(vstr[0]) <<endlcout <<" Hash value: " <<strhash(vstr[1]) <<endlcout <<" Hash value: " <<hash<vector<string>>() (vstr) <<endlcout <<" Hash value: " <<hash<int>() (100) <<endl// hash<int>() 临时函数对象return 0}