又修改了一下，实现了resize
#include #include #include #include #include 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;isize = 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( ; isize ; 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 size - 1; realloc(&ht->arbuckets,sizeof(bucket*) * ht->size); int i; for(i=ht->size>>1;isize;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;}