C++链地址法实现哈希表

哈希表，也叫散列表，是根据关键码值(Key　value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

哈希函数最主要的设计在于哈希函数和冲突处理的解决，其中哈希函数的设计方法主要有直接定址法和除留余数法；冲突处理的方法主要有开放定址法和链地址法。本文主要实现了一个基本存放字符串的哈希表，冲突处理采用链地址法。

代码如下：

#include 
  
   
#include
   
     #define HASHSIZE 19 using namespace std; struct hashnode{ char *key; char *value; hashnode *next; }; char *strcopy(char *s) { int len=strlen(s)+1; char *res=new char[len]; strcpy(res,s); if(res==NULL) return NULL; return res; } class hashtable { public: hashtable(); ~hashtable(); unsigned int hasher(char *s); hashnode *hashfind(char *keys); bool hashinsert(char *keys,char *values); bool hashdelete(char *keys); void display(); private: hashnode *hashdata[HASHSIZE]; }; hashtable::hashtable() { for(int i=0;i
    
     next; delete p->key; delete p->value; delete p; p=q; } } } } //hash函数可以自己定义 unsigned int hashtable::hasher(char *s) { unsigned int res=0; for(;*s!='\0';++s) res=*s+res; return res%HASHSIZE; } hashnode* hashtable::hashfind(char *keys) { unsigned int res=hasher(keys); hashnode *p=hashdata[res]; for(;p!=NULL;p=p->next) if(strcmp(p->key,keys)==0) return p; return NULL; } bool hashtable::hashinsert(char *keys,char *values) { unsigned int res; if(keys==NULL) return 0; hashnode *p; if((p=hashfind(keys))==NULL) { res=hasher(keys); p=new hashnode; if(p==NULL) return 0; p->key=strcopy(keys); p->value=strcopy(values); if(p->key==NULL) return 0; p->next=hashdata[res]; //链表头插入 hashdata[res]=p; } else { delete p->value; //如果key在哈希表中，先删除原有value值 p->value=strcopy(values); } if(p->value==NULL) return 0; return 1; } bool hashtable::hashdelete(char *keys) { hashnode *p=NULL,*q=NULL; unsigned int res=hasher(keys); p=hashdata[res]; if(!p) return 0; if(strcmp(p->key,keys)==0) { hashdata[res]=p->next; delete p->key; delete p->value; delete p; } q=p;p=q->next; while(p&&(strcmp(p->key,keys)!=0)) { q=p; p=p->next; } if(p) { q->next=p->next; delete p->key; delete p->value; delete p; } return 1; } void hashtable::display() { hashnode *p; for(int i=0;i
     
      next) cout<<"("<
      
       key<<","<
       
        value<<")"; cout<<")"<
        
         value<