又修改了一下，实现了resize
#include <stdlib.h>#include <stdio.h>#include <string.h>#include <malloc.h>#include <math.h>typedef struct bucket{ int h; char* key; void* pData; struct bucket* pNext; struct bucket* pLast;}Bucket;typedef struct hashtable{ int size; int elementsNum; int mask; Bucket** arBuckets; //这是一个存放buckets的array }HashTable;/** ** 这是一个计算HASH值的算法 **/int time33(char* arKey,int arlength){ int h = 0; int i; for(i=0;i<arlength;i++){ h = h*33 + (int)*arKey++; } return h; }/** ** 初始化一个大小是1的HASHTABLE **/int _init_hash_table(HashTable** ht){ *ht = (HashTable*)malloc(sizeof(HashTable)); (*ht)->size = 1; (*ht)->mask = (*ht)->size - 1; (*ht)->elementsNum = 1; (*ht)->arBuckets = (Bucket**)malloc(sizeof(Bucket*)*(*ht)->size); memset((*ht)->arBuckets,0,sizeof(Bucket*)*(*ht)->size); return 1; } int _hash_link_bucket_to_bucket_head(Bucket** newBucket,Bucket** bucketHead){ if(*bucketHead==NULL){ *bucketHead = *newBucket; }else{ (*newBucket)->pNext = (*bucketHead)->pNext; (*newBucket)->pLast = (*bucketHead); if((*bucketHead)->pNext != NULL){ (*bucketHead)->pNext->pLast = *newBucket; } (*bucketHead)->pNext = *newBucket; } return 1;}int _hash_new_bucket(Bucket** newBucket,int hash,char* arkey,void* pData){ (*newBucket) = (Bucket*)malloc(sizeof(Bucket)); (*newBucket)->h = hash; (*newBucket)->key = arkey; (*newBucket)->pData = pData; (*newBucket)->pNext = NULL; (*newBucket)->pLast = NULL; return 1;}int _hash_rehash(HashTable* ht){ int i = 0; //由于我没定义pListNext指针，所以只能这样rehash了。 for( ; i<ht->size ; i++){ if(ht->arBuckets[i] != NULL){ int index = ht->arBuckets[i]->h & ht->mask ; if(i != index){ _hash_link_bucket_to_bucket_head(&ht->arBuckets[i],&ht->arBuckets[index]); ht->arBuckets[i] = NULL; } } } return 1; }/** ** 将HASHTABLE的大小扩容1倍 **/int _hash_resize(HashTable* ht){ if(ht != NULL){ ht->size = ht->size << 1; ht->mask = ht->size - 1; realloc(&ht->arBuckets,sizeof(Bucket*) * ht->size); int i; for(i=ht->size>>1;i<ht->size;i++){ ht->arBuckets[i] = NULL; } //memset(ht->arBuckets[0],NULL,sizeof(Bucket*) * (ht->size >> 1)); printf("resize:%i\r\n", ht->size); _hash_rehash(ht); return 1; } return 0;}/** ** 往HASHTABLE中添加元素 **/int _hash_add_or_update(HashTable* ht,char* arKey,int arLength,void* pData){ int h = time33(arKey,arLength); int index = h & ht->mask; Bucket* p = ht->arBuckets[index]; while(p!=NULL){ if(strcmp(arKey,p->key)==0){ //这里应该执行更新操作 free(p->pData); p->pData = pData; return 1; } p = p->pNext; } Bucket* newBucket; _hash_new_bucket(&newBucket,h,arKey,pData); _hash_link_bucket_to_bucket_head(&newBucket,&ht->arBuckets[index]); ht->elementsNum++; if(ht->elementsNum = ht->size){ _hash_resize(ht); } return 0; }void* _hash_find(HashTable* ht,char* arKey,int arLength){ int h = time33(arKey,arLength); int index = h & ht->mask; Bucket* p = ht->arBuckets[index]; while(p!=NULL){ if(strcmp(arKey,p->key)==0){ return p->pData; } p = p->pNext; } return 0;}int PUT(HashTable* ht,void* key,void* value){ char* arKey = (char*)key; int len = strlen(arKey); return _hash_add_or_update(ht,arKey,len,value); }void* GET(HashTable* ht,void* key){ char* arKey = (char*)key; int len = strlen(arKey); return _hash_find(ht,arKey,len);}int main(){ printf("%s\r\n","这是一个hashtable的例子"); HashTable* ht; _init_hash_table(&ht); PUT(ht,"1","mengjun"); PUT(ht,"2","aaaaa"); PUT(ht,"3","fff"); PUT(ht,"24","eee"); PUT(ht,"25","ddd"); printf("%s\r\n",(char*)GET(ht,"1")); printf("%s\r\n",(char*)GET(ht,"2")); printf("%s\r\n",(char*)GET(ht,"3")); printf("%s\r\n",(char*)GET(ht,"24")); printf("%s\r\n",(char*)GET(ht,"25")); printf("HASHTABLE总共有元素%i个\r\n",ht->elementsNum); return 0;}