实现极小一部分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 != NULL){
int index = ht->arBuckets->h & ht->mask ;
if(i != index){
_hash_link_bucket_to_bucket_head(&ht->arBuckets,&ht->arBuckets);
ht->arBuckets = 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 = NULL;
}
//memset(ht->arBuckets,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;
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);
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;
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;
}
页:
[1]