哈希表例子2

數組的特點是：尋址容易，插入和删除困難；而連結清單的特點是：尋址困難，插入和删除容易。hash表可以解決以上兩個不足之處。

假如你要在圖書館裡找一本《電路原理》，這本書首先它在工科類下面，再在工科類的電子資訊這個分類裡面，你首先要找到工科，再找到電子資訊類，然後再找《電路原理》。好了，hashEntry_s相當于這個分類表，它的key就是你要查的類别，data就是你要查的書本，hashtable就是那張存放類别的大表。

struct hashEntry_s{  
    void *key;  
    void *data;  
    struct hashEntry_s *next;     
};  
  
struct hashTable_s{  
    struct hashEntry_s **hashlist;  
};    
typedef struct hashTable_s hashTable_t;

首先要生成這樣hash表

HASHSIZE 最好是素數，這樣可以減少沖突的機率。

hashlist指向各個分類

#define HASHSIZE 67  
      
    hashTable_t *createHashTable(void)  
    {  
        hashTable_t *table;  
        int i,len,primesize;  
        table = malloc(sizeof(hashTable_t));  
        if(NULL == table){      
            printf("error in createtable");  
            return NULL;  
        }  
        len = sizeof(struct hashEntry_s *)*HASHSIZE;  
        table->hashlist = malloc(len);  
        if(table->hashlist == NULL){  
            printf("error in createtable\n");  
            exit(1);  
        }  
        for(i=0;i<HASHSIZE;i++)  
            table->hashlist[i]=NULL;  
      
        return table;   
    }

hash表中的标簽。就相當于在圖書觀的那張表中，工科類被編号1234一樣。hash表中也要将key做一個标簽，通過key可以快速定位table中的hashlist，進而快速提取資料。

hash算法有很多，可參考http://hi.baidu.com/hytjfxk/blog/item/46f6feceafbe622392457e0a.html

我截取其中一個比較簡單的算法作為我的hash算法，它将字元串轉換成了響應的整數。

unsigned long  getHashValue(char *string)  
    {      
          unsigned long ret=0;  
          long n;  
          unsigned long v;  
          int r;  
      
        if(NULL == string){  
            return 0;  
        }  
      /* 
         unsigned char b[16]; 
         MD5(c,strlen(c),b); 
         return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); 
      */  
          n=0x100;  
          while (*string) {  
            v=n|(*string);  
             n+=0x100;  
             r= (int)((v>>2)^v)&0x0f;  
             ret=(ret<<r)|(ret>>(32-r));  
             ret&=0xFFFFFFFFL;  
             ret^=v*v;  
             string++;  
        //    printf("while is over\n");  
          }  
          return((ret>>16)^ret);  
    }

由于我們table的大小為HASHSIZE，是以要将key放入表中的話，得到的hash值還需整除HASHSIZE。

将标簽和資料插入表中(int insertHash(void *key,void *data,hashTable_t *tab))，比如我要《電路原理》這部書放置在電子資訊工程這張表裡，key是電路原理，data是電路原理的内容，table是電子資訊工程。 hashlist是表中一個個分類。

/*檢查key是否已經存在于表中*/  
    int UpdateHashList(void *key,void *data,struct hashEntry_s *hashlist,hashTable_t *tab)  
    {  
        if(hashlist !=NULL){              
            struct hashEntry_s *pos;  
            for(pos=hashlist;pos != NULL;pos=pos->next){  
                if(strcmp(key,pos->key)==0){  
                    pos->key = key;  
                    pos->data =data;  
                    return 0;  
                }  
            }  
        }  
        return -1;  
    }  
      
    int insertHash(void *key,void *data,hashTable_t *tab)  
    {  
        int index;  
        index =getHashValue((char *)key)%HASHSIZE;  
    //    printf("index:%d\n",index);  
        if(UpdateHashList(key,data,tab->hashlist[index],tab)<0){  
            struct hashEntry_s *l;  
            l= hashEntryNew(key,data);  
            if(tab->hashlist[index] == NULL){  
                tab->hashlist[index] = l;  
                printf("insert data:%s\n",(char *)tab->hashlist[index]->data);  
            }else{  
                struct hashEntry_s *pos;  
                for(pos = tab->hashlist[index];pos->next !=NULL;pos->next){  
                        pos= l;  
                    }  
              }  
          }      
        return 0;  
    }

得到元素資料（void *getHashData(void *key,hashTable_t *tab)）。假如要取《電路原理》的資訊，那麼key即為電路原理，tab是電子資訊工程那張表。

void *getHashData(void *key,hashTable_t *tab)  
    {  
        int index;  
        char *get_data;  
        index = getHashValue((char *)key)%HASHSIZE;  
        printf("get index :%d\n",index);  
        struct hashEntry_s *pos;  
      
        for(pos = tab->hashlist[index];pos !=NULL;pos = pos->next){  
            if(strcmp(key,pos->key) == 0){  
                return pos->data;  
            }  
        }  
        return NULL;  
    }

删除表資訊

int removeHash(void *key,hashTable_t *tab)

{  
    int index;  
    index = getHashValue((char *)key)%HASHSIZE;  
    struct hashEntry_s *pos;  
    for(pos=tab->hashlist[index];pos != NULL;pos=pos->next,index++){  
        if(strcmp(key,pos->key) == 0){  
            pos->key = NULL;  
            pos->data = NULL;  
            if(pos->next != NULL){  
                pos =pos->next;  
            }else{  
                tab->hashlist[index] =NULL;  
            }  
            return 0;  
        }  
        return -1;  
    }  
    printf("remove over!\n");  
    return -1;  
}

按照上面的思路，假如你要從圖書館這個大表開始查的話，得建兩張hash表，一張是圖書館，一張是電子資訊。查的時候，圖書館表中的key是電子資訊，電子資訊表中的key是電路原理。

下面是把上面代碼整個起來做的一個簡單測試。

#include <stdio.h>  
    #include <stdlib.h>  
    #include <string.h>  
    #include <malloc.h>  
      
    #define HASHSIZE 67  
      
    struct hashEntry_s{  
        void *key;  
        void *data;  
        struct hashEntry_s *next;     
    };  
      
    struct hashTable_s{  
        struct hashEntry_s **hashlist;  
    };    
    typedef struct hashTable_s hashTable_t;  
      
    unsigned long  getHashValue(char *string)  
    {     
         unsigned long ret=0;  
         long n;  
         unsigned long v;  
         int r;  
      
        if(NULL == string){  
            return 0;  
        }  
      /* 
         unsigned char b[16]; 
         MD5(c,strlen(c),b); 
         return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); 
      */  
         n=0x100;  
        while (*string) {  
            v=n|(*string);  
            n+=0x100;  
            r= (int)((v>>2)^v)&0x0f;  
            ret=(ret<<r)|(ret>>(32-r));  
            ret&=0xFFFFFFFFL;  
            ret^=v*v;  
            string++;  
        //  printf("while is over\n");  
        }  
        return((ret>>16)^ret);  
    }  
      
    hashTable_t *createHashTable(void)  
    {  
        hashTable_t *table;  
        int i,len,primesize;  
        table = malloc(sizeof(hashTable_t));  
        if(NULL == table){    
            printf("error in createtable");  
            return NULL;  
        }  
        len = sizeof(struct hashEntry_s *)*HASHSIZE;  
        table->hashlist = malloc(len);  
        if(table->hashlist == NULL){  
            printf("error in createtable\n");  
            exit(1);  
        }  
        for(i=0;i<HASHSIZE;i++)  
            table->hashlist[i]=NULL;  
      
        return table;   
    }  
      
    inline struct  hashEntry_s *hashEntryNew(void *key, void *data)  
    {  
        struct hashEntry_s *new = malloc(sizeof(struct hashEntry_s));  
        memset(new,0,sizeof(struct hashEntry_s));  
        new->key = key;  
        new->data = data;  
        new->next = NULL;  
        return new;  
    }  
      
    int UpdateHashList(void *key,void *data,struct hashEntry_s *hashlist,hashTable_t *tab)  
    {  
        if(hashlist !=NULL){              
            struct hashEntry_s *pos;  
            for(pos=hashlist;pos != NULL;pos=pos->next){  
                if(strcmp(key,pos->key)==0){  
                    pos->key = key;  
                    pos->data =data;  
                    return 0;  
                }  
            }  
        }  
        return -1;  
    }  
      
    int insertHash(void *key,void *data,hashTable_t *tab)  
    {  
        int index;  
        index =getHashValue((char *)key)%HASHSIZE;  
    //  printf("index:%d\n",index);  
        if(UpdateHashList(key,data,tab->hashlist[index],tab)<0){  
            struct hashEntry_s *l;  
            l= hashEntryNew(key,data);  
            if(tab->hashlist[index] == NULL){  
                tab->hashlist[index] = l;  
                printf("insert data:%s\n",(char *)tab->hashlist[index]->data);  
            }else{  
                struct hashEntry_s *pos;  
                for(pos = tab->hashlist[index];pos->next !=NULL;pos->next){  
                        pos= l;  
                    }  
            }  
          }   
        return 0;  
    }  
      
    void *getHashData(void *key,hashTable_t *tab)  
    {  
        int index;  
        char *get_data;  
        index = getHashValue((char *)key)%HASHSIZE;  
        printf("get index :%d\n",index);  
        struct hashEntry_s *pos;  
      
        for(pos = tab->hashlist[index];pos !=NULL;pos = pos->next){  
            if(strcmp(key,pos->key) == 0){  
                return pos->data;  
            }  
        }  
        return NULL;  
    }  
      
    int removeHash(void *key,hashTable_t *tab)  
    {  
        int index;  
        index = getHashValue((char *)key)%HASHSIZE;  
        struct hashEntry_s *pos;  
        for(pos=tab->hashlist[index];pos != NULL;pos=pos->next,index++){  
            if(strcmp(key,pos->key) == 0){  
                pos->key = NULL;  
                pos->data = NULL;  
                if(pos->next != NULL){  
                    pos =pos->next;  
                }else{  
                    tab->hashlist[index] =NULL;  
                }  
                return 0;  
            }  
            return -1;  
        }  
        printf("remove over!\n");  
        return -1;  
    }  
    int main(void)  
    {  
        hashTable_t *table_a;  
        int i=0;  
        char *data ="hello";  
        char *getdata ="world" ;  
        char *key ="1";  
        table_a = createHashTable();  
        if(table_a == NULL){  
            printf("error!\n");  
            return -1;  
        }  
      
        insertHash(key,data,table_a);  
      
        getdata = getHashData(key,table_a);  
        if(getdata == NULL ){  
            printf("wo cao !!!\n");  
            return -1;  
        }  
        printf("get hash data :%s\n",getdata);    
      
        char *data2="next!";  
        insertHash(key,data2,table_a);  
      
        getdata = getHashData(key,table_a);  
        if(getdata == NULL ){  
            printf("empty !!!\n");  
            return -1;  
        }  
        printf("get hash data :%s\n",getdata);    
      
        removeHash(key,table_a);  
        getdata = getHashData(key,table_a);  
        if(getdata == NULL ){  
            printf("empty !!!\n");  
            return -1;  
        }  
        printf("get data remove:%s\n",getdata);  
      
        free(table_a);  
        return 0;  
    }

原文位址：http://blog.csdn.net/fenglifeng1987/article/details/7854989

哈希表例子2

繼續閱讀

遇到的坑-對象之間的關系(1)啊啊啊，關于這篇文章，有很多問題，我自己又去調試了一下，發現不是那麼回事。這裡是最新的關于這個問題的分析

Java實作雙向連結清單詳細代碼

合并k個排序連結清單（Python實作）

HashMap、HashSet、ArrayList實作機制

2017年團體程式設計天梯賽-決賽小結

PAT (Advanced Level) Practise 1097 Deduplication on a Linked List (25)

求連結清單的第一個公共節點問題（好未來筆試題）

HDU 1067（HASH + BFS）

反轉連結清單，基礎棧練習，貪心

B - No Name UVALive - 6319 思維or連結清單

python連結清單逆轉(代碼附效果)

資料結構-連結清單的基本操作實作

嚴蔚敏資料結構C語言版線性表的增删改查功能（中職學習記錄篇）（純敲代碼：完全自己敲的）

LeetCode No.21 Merge Two Sorted Lists

連結清單-Java-力扣61. 旋轉連結清單1. 題目2. 思路3. 代碼

linux下自創網絡程式設計聊天室（4）改進兩點