哈希算法之除留余+拉链冲突代码

哈希表就是个数组，所有元素和地址组成的结构存在这个数组里，查找就通过除留余找数组下标，找到相应数组的值
插入也通过除留余得到下标，加到此数组下标里
/*
  该程序实现的哈希表：构造哈希函数的方法为除留余数法(函数modhash)，处理哈希冲突的方法为链地址法。
  对哈希表的操作：插入（函数hash_table_insert）、移除（函数hash_table_remove）、
  查找（函数hash_table_lookup）、整个哈希表的释放（函数hash_table_delete）、
  整个哈希表的输出（函数hash_table_print）。 
  哈希表的最大长度可以由HASHMAXLEN设置（我设为1000）。
  输入哈希表的名称拼音字符是长度为10—20（长度可由STR_MAX_LEN和STR_MIN_LEN）的小写字母组成。
  名称拼音字符（关键字）到关键字值的转换方法：先把名称的拼音字符转换对应的ASCII，累加后作为关键字值。
*/ 
#include
#include
#include
#include
#include


/******************************hash table top**********************************/
#define  HASHMAXLEN  1000
typedef struct hashnode_struct HashNode;
struct hashnode_struct
{
       char *Str;
       unsigned int Key;
       HashNode *Pnext; //每个节点都有一个指向下一节点指针，
};
HashNode    *hashtable[HASHMAXLEN];//存放一百个指向此节点的指针
unsigned int     hash_len;


/* initialize hash table */
void hash_table_init()
{
     hash_len=0;
     memset(hashtable,0,sizeof(HashNode*)*HASHMAXLEN);
}
     
/* change string into key_value */
unsigned int str_to_key(const char *str)
{
    unsigned int value=0;
int i,len;
len=strlen(str);
for(i=0;i value+=(unsigned int)(*(str+i));
return value;
}


/* hash function */
unsigned int modhash( unsigned int kvalue,unsigned int h_len)
{
         return(kvalue%h_len);
}


/* insert key to hash table */
void hash_table_insert(const char *str)
{
     if(hash_len >= HASHMAXLEN)
    {
        printf("out of hash table memory!\n");
        return;
    }
    
    unsigned int position=modhash(str_to_key(str),HASHMAXLEN);
    
    HashNode *phead=hashtable[position];
    while(phead)
    {
          if(strcmp(phead->Str,str)==0)
          {
             printf("%s already exists !\n",str);
             return;
          }
          phead=phead->Pnext;
    }
    
    HashNode *pnewnode=(HashNode *)malloc(sizeof(HashNode));
    memset(pnewnode,0,sizeof(HashNode));
    pnewnode->Str=(char *)malloc(sizeof(char)*(strlen(str)+1));
    strcpy(pnewnode->Str,str);
    pnewnode->Key=str_to_key(str);
    pnewnode->Pnext=hashtable[position];//关键所在，让新节点指向老节点，然后使数组指针指向新节点，这样一个节点可以一直指下去，有冲突就一直指下去
    hashtable[position]=pnewnode;
    
    hash_len++;
}


/* remove key from hash table */
void hash_table_remove(const char *str)
{
     unsigned int position=modhash(str_to_key(str),HASHMAXLEN);
     if(hashtable[position])
     {
        HashNode *phead=hashtable[position];
        HashNode *plast=NULL;
        HashNode *premove=NULL;
        while(phead)
        {
           if(strcmp(phead->Str,str)==0)
           {
              premove=phead;
              break;
           }
           plast=phead;
           phead=plast->Pnext;
        }
        if(premove)
        {
           if(plast)
              plast-> Pnext=premove-> Pnext;
           else
              hashtable[position]=NULL;
           free(premove-> Str);
           free(premove);
        }
     }
}


/* lookup a key in hash table */
HashNode *hash_table_lookup(const char *str)
{
         unsigned int position=modhash(str_to_key(str),HASHMAXLEN);
         if(hashtable[position])
         {
            HashNode *phead=hashtable[position];
            while(phead)
            {
               if(strcmp(phead-> Str,str)==0)
                  return phead;
               phead=phead-> Pnext;
            }
         }
         return NULL;
}


/* print the content of hash table */
void hash_table_print()
{
     printf("***********the content of hash table************\n");
     int i;
     for(i=0;i      {
         if(hashtable[i])
         {
            HashNode *phead=hashtable[i];
            printf("%d =>",i);
            while(phead)
            {
               printf("%s:%d",phead-> Str,phead-> Key);
               phead=phead-> Pnext;
            }
            printf("\n");
         }
     }
}


/* delete the hash table */
void hash_table_delete()
{
     int i;
     for(i=0;i      {
       if(hashtable[i])
       {
         HashNode *phead=hashtable[i];
         while(phead)
         {
            HashNode *ptemp=phead;
            phead=phead-> Pnext;
            if(ptemp)
            {
               free(ptemp-> Str);
               free(ptemp);
            }
         }
       }
     }            
}
/***************************hash table bottom**********************************/




/**************************generate random string******************************/
#define STR_MAX_LEN 20
#define STR_MIN_LEN 10
void rand_str(char r[])
{
     int i;
     int len=STR_MIN_LEN+rand()%(STR_MAX_LEN-STR_MIN_LEN);
     for(i=0;i      {
         r[i]='a'+rand()%('z'-'a');
     }
     r[len-1]='\0';
}


/******************************test function***********************************/
int main(int argc,char **argv)
{
     srand(time(NULL));
     
     hash_table_init();
     
     //1.insert testing
     printf("insert testing ......\n");
     int n=15;
     const char *str1="bbbccc";
     const char *str2="dddeee";
     const char *str3="fffggg";
     hash_table_insert(str1);
     hash_table_insert(str2);
     hash_table_insert(str3);
     char stri[STR_MAX_LEN+1];
     while(n--)
     {
        rand_str(stri);
        hash_table_insert(stri);
     }
     hash_table_print();
     
     //2.lookup testing
     printf("\nlookup testing ......\n");
     HashNode *pnode=hash_table_lookup(str1);
     printf("lookup result:%d\n", pnode->Key);
     pnode = hash_table_lookup(str2);
     printf("lookup result:%d\n", pnode->Key);


     //3.remove testing
     printf("\nremove testing ......\n");
     printf("\nbefore remove %s:\n",str3);
     hash_table_print();
     hash_table_remove(str3);
     printf("\nafter remove %s:\n",str3);
     hash_table_print();
     hash_table_delete();
     
     system("pause");
     return 0;
}