实现极小一部分PHP的HASHMAP
又修改了一下，实现了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;}