欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

兑现极小一部分PHP的HASHMAP

程序员文章站 2022-05-13 08:35:45
...
实现极小一部分PHP的HASHMAP
又修改了一下,实现了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 mask = ht->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;
}


兑现极小一部分PHP的HASHMAP

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。

相关文章

相关视频