哈希函数编程实现

class Node{//边节点类 public:

Node(char *ptr){

int len=strlen(ptr); str=new char[len+1]; for(int i=0;istr[len]='\\0'; next=NULL; }

~Node(){delete []str;}

friend class Hash;//定义为友元 private:

char* str; Node*next; };

class Hash{//哈希散列表类 public:

Hash(int len=0){//构造函数 length=len; count=0;

head=new Node*[len]; for(int i=0;ifile=NULL; }

~Hash(){//析构函数

ClearList();//用于清空哈希表中的数据 delete[]head; }

void HashTest(int type){//运用哈希函数进行测试，tupe=0为BKDR,type=1为ELF,type=2为AP,type=3为自己设计哈希函数

ClearList();//用于清空散列表中的数据，进行新的哈希函数测试 file=fopen(\"data.txt\指定读入文件为data.txt

if(file==NULL){

cout<<\"文件打开失败!\"<char str[32];//假定每个字符长度不超过32 unsigned int position; while(!feof(file)){ count++;

fscanf(file,\"%s\ if(type==0){

position=BKDRHash(str); }else if(type==1){

position=ELFHash(str); }else if(type==2){

position=APHash(str); }else{

position=MyHash(str); }

position=position%length; Node *node=new Node(str); if(head[position]==NULL){ head[position]=node; }else{

Node*temp;

temp=head[position];

while(temp->next!=NULL){ temp=temp->next; }

temp->next=node; } }

fclose(file);

Assess(type);//计算桶使用率和平均桶长 }

void SetFile(int num){//设计随机数据文件 ofstream fout(\"data.txt\"); if(!fout.is_open()) {

cout<<\"无法打开输出流!!程序退出\"<srand(time(0));//置随机数种子，一个随机数序列只需置一次。 for(int i=0;iint clength=1+rand()%32;//字符串的长度1到32,全字母字符串

for(int j=0;jchar cname=(char)(d); fout<if(i!=num-1) fout<<\" \"; }

fout.close(); }

void Display(){//查看哈希表内存存入状态 Node*temp;

for(int i=0;icout<cout<while(temp!=NULL){

cout<str<<\" \"; temp=temp->next; }

cout<private:

void Assess(int type){//计算评价指标，输出到控制台 int backet_num=0;

for(int i=0;ibacket_usage=(float)backet_num/length; avg_backet_len=(float)count/backet_num; if(type==0){

cout<<\"测试\"<cout<<\"桶的平均长度为:\"<cout<<\"测试\"<cout<<\"测试\"<cout<<\"测试\"<cout<void ClearList(){//清空哈希表，用于继续测试其他哈希函数 Node *temp1,*temp2; for(int i=0;iwhile(temp1!=NULL){ temp2=temp1;

temp1=temp1->next; delete temp2; }

head[i]=NULL; }

count=0; }

unsigned int MyHash(char *str){//自己设计哈希函数具体实现 unsigned int hashcount=0; unsigned int x=0; int i=0; while(*str){

if((i&1)==0){

hashcount=((hashcount<<3)+*(str++)); }else{

hashcount=((hashcount<<5)+~(*str++)); }

if((x=hashcount&0xF0000000)!=0){ hashcount=hashcount^(x>>24); hashcount=hashcount&(~x); } }

return (hashcount&0x7FFFFFF); }

unsigned int APHash(char *str){//AP哈希函数 unsigned int hashcount=0; int i;

for(i=0;*str;i++){ if((i&1)==0){

hashcount^=((hashcount<<7)^(*str++)^(hashcount>>3)); }else{

hashcount^=(~((hashcount<<11)^(*str++)^(hashcount>>5))); } }

return (hashcount&0x7FFFFFFF); }

unsigned int BKDRHash(char *str){//BKDR哈希函数 unsigned int seed=131; unsigned int hashcount=0; while(*str){

hashcount=hashcount*seed+(*str++); }

return (hashcount&0x7FFFFFF); }

unsigned int ELFHash(char *str){//ELF哈希函数 unsigned int hashcount=0; unsigned int x=0; while(*str){

hashcount=(hashcount<<4)+(*str++); if((x=hashcount&0xF0000000)!=0){ hashcount^=(x>>24); hashcount&=~x; } }

return hashcount; } private:

Node**head;//哈希表头 int length;//哈希表长

int count;//读入字符串数量

FILE*file;//数据读入文件头指针 float backet_usage;//桶的使用率 float avg_backet_len;//平均桶长 };

int main()

{

Hash hash(90000);

hash.SetFile(90000);//进行10000个随机数据哈希函数性能的比较 hash.HashTest(0);//BKDR,

hash.HashTest(1);//ELF

hash.HashTest(2);//AP

hash.HashTest(3);//自己设计哈希函数 return 0; }