前言：闲来蛋疼，周末在家陪老婆，中午还要亲自操厨，操厨之前，加深下对hash的理解，写下此篇。
正文：本篇文章主要模拟了海量搜索过程。从txt文件获取大量数据信息（模拟海量），建立hash表，然后输入关键字(字符串)，能迅速定位要找的value。其实就是搜索某个特定的字符串。具体会贴出代码，和验证图。整个过程模拟了海量查找的过程，能切实感觉到hash 海量处理的优势。
先贴几张运行效果图:
图 1
稍微解释一下：结合图1 中的第一行， 第359次，指发生映射的顺序数；992处，指哈希数组中的位置，即hashTable[992]；存入的字符串，为我们哈希映射以后把原字符串存起来，以便查找时比较；value,指映射后要定位的值，比如：我们要查找字符串出现的概率，或是字符串出现的次数等等，在程序里相当于留了一个借口。注意：所有的数据从txt里读取，而txt里的的数据由程序模拟生成，采用rand()函数。具体见后面的程序源码或下载后面贴出的工程文件的下载地址。我生成的是5000个，通过修改宏参数，可以更多，非常贴近真实。
图 2
图 2 最后一行，显示了要查找字符串的位置。如下图，蓝色部分。
网上先搜索了一番，发现要么就是理论一堆，要么就是贴出关键代码，让我等菜鸟始终没法体会海量的涵义。
本文章分为三大部分。第一部分：hash的基本知识，第二部分，hash映射的建立和冲突的解决，具体代码实现
hash 的主要作用就是快速查找，其时间复杂度是O(1),是最好的查找算法。对于hash的入门级别可参考我的一篇其他博文 数据结构-练习2 哈希表。hash的最基本理解就是：根据要查找的字符串的ASCII(经过变换处理)，通过哈希函数，转换成与其存储位置的下标，这样在hash表建立以后，我们就可以根据字符串本身，以相同的哈希函数映射方式迅速定位到其位置，然后查找出相关信息。
哈希函数的构造就成为了最重要的任务之一，常见的方法有：直接取址法，平方取中法，除留余数法，数字分析法，折叠法，随机数法。
本文章的例子采用除留余数法：
基本原理为：H(key)=key%MOD,MOD 为小于表长的一个数，本例子为1024.
结合代码具体分析（SDBM法）：
int SDBMHash(char* str)
{
int hash = 0;
while(*str!='\0')
{
//相当于：65599*hash+*str++,这就是映射函数，通过字符串里每个字符的ASCIIl累计形成
hash = *str++ + (hash << 6) + (hash << 16) - hash;
}
return (hash & 0x7FFFFFFF);
}
最后别忘了求余数：key=key%HashTableLen;//HashTableLen=1024，key就是SDBMHash的返回值。
冲突解决是第二个重要的过程，基本方法包括：链表法，开放地址法，再哈希，开辟公共溢出区。
本文章例子采用常见的链表法：
如图，左边为：第一次获得的key的位置，显然，两个不同的字符串很可能有相同的key,这时我们在后面加个链表存储一下。
代码如：
p=&HashT[key];
while(p->next!=NULL) p=p->next;
{
p->next=new hashNode();
p->next->used=true;
strcpy(p->next->key,str);
p->next->value=rand()%100;
}
贴完整个程序的代码：
#include<iostream> #include<fstream> #include<string> using namespace std; const unsigned int NUM=5000; const int HashTableLen=1024; int count=0;//用于记录hash映射时，发生的次数，验证作用 struct hashNode { bool used; hashNode* next; char key[28]; unsigned int value; hashNode() { used=false; next=NULL; } hashNode(char* KEY,unsigned int VALUE) { strcpy(key,KEY); value=VALUE; } }HashT[HashTableLen] ;// 哈希表的长度为1024，所以取摸的时候用1024； unsigned int elfhash(char* s);//declare the function void createStrTXT(); void establishHaT(); void FindStr(char*); int main() { //for(int i=0;i<50000;++i) //生成txt，文件，往里面随机写入字符串。 //createStrTXT(); establishHaT(); FindStr("qd`e_usigh]oscfwsnfreshayug"); //FindStr(); /* char str[30]; ifstream ifs("str.txt"); ifs>>str; */ } int SDBMHash(char* str) { int hash = 0; while(*str!='\0') { hash = *str++ + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); } unsigned int elfhash(char *s){ int hash = 0, x = 0; while (*s){ hash = (hash << 4) + (*s++); if(((x = hash) & 0xf0000000L) != 0){ hash ^= (x >> 24); hash &= ~x; } } return hash & 0x7fffffff; } void createStrTXT() { for(int i=0;i<NUM;++i) { char temp[30]={'\n','\r',rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91 ,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91,rand()%31+91 ,rand()%31+91,rand()%31+91,'\0'}; char*str=temp; ofstream ofs("str.txt",ios::app); ofs<<str; } } void establishHaT()//采用链表法构造hash表 { hashNode * p; int key; char str[28]; ifstream ifs("str.txt"); while( ifs>>str) { key=SDBMHash(str); key=key%HashTableLen; if(HashT[key].used==false) { strcpy(HashT[key].key,str); HashT[key].used=true; HashT[key].value=rand()%100; count++; //伪随机的目的是模拟key-value 里的value,里面就是我们要查找的值，e.g. 如果要查找字符串是否存 //在， printf("第%d次在 %d处发生了映射,存入的字符串为：%s,value为：%d\n",count,key,str,HashT[key].value);//里面就村字符串本身；如果要查某字符串出现的概率， //里面就是概率值，如果查找的是字符串出现的次数，里面存的就是次数，正如百度的那道查找top 10的 //面试题，原理跟这一样 } else//冲突处理 { p=&HashT[key]; while(p->next!=NULL) p=p->next; { p->next=new hashNode(); p->next->used=true; strcpy(p->next->key,str); p->next->value=rand()%100; count++; printf("第%d次在 %d处发生了映射,存入的字符串为：%s,value为：%d\n",count,key,str,HashT[key].value); } } } } void FindStr(char* str) { hashNode * p; int key; key=SDBMHash(str); key=key%HashTableLen; if(HashT[key].used==false) { printf("此字符串不存在"); } else { p=&HashT[key]; while(p!=NULL) { if(!strcmp(p->key,str)) { printf("在%d位置处找到了目的字符串:%s",key,str); break; } else { p=p->next; } if(p==NULL) printf("SORRY!字符串没有匹配的"); } } }说明：函数 FindStr（char*）主要是查找特定的字符串，原理与构造hash函数的过程一样。注意的是：写入函数参数中的字符串，不应该含有转义符，因为转义符号，程序可能不认识，所以，在TXT里选一个没有转移符号的作为参数，如本例。createStrTXT();主要是创建txt文件，NUM是创建的字符串的个数，注意的是，我创建时，写入文件采用了ios::app,所以每次运行程序，如果都createStrTXT()，txt里的字符 串个数会每次都增加5000次。所以创建一次就可以，以后就注销。工程文件下载地址：此处下载。需要一积分，不好意思，我想攒点分下东西，没积分的 留下邮箱。我将速度发送。