langc_algo_hash_openaddressing.c

#include <stdio.h>
#include <string.h>

#define MAX_HASH  20

#define HASH_KEY		0
#define HASH_VAL		1

static int hashmap[MAX_HASH][2]={0}; // open-addressing hash, pointer
static int hashsize=0;
static int vacated = (int) &hashsize; //need address ,  deleted hash, 

unsigned int hash1(char * str)
{
	int val=0x7464321; 

	while(*str != '\0' )
	{	
		val  = (val << 4) + *str; 
		str++;
	}
	
	return val;
}

unsigned int hash2(char * str)
{
	int val=0x1238742; 

	while(*str != '\0' )
	{	
		val  = (val << 3) + *str; 
		str++;
	}
	
	return val;
}



int insertHash(char* key, char *value)
{
	int pos,i;
	
	for(i=0;i<MAX_HASH;i++)
	{
		pos = ( hash1(key) + (i *  hash2(key)) ) % MAX_HASH;
	
		if(hashmap[pos][HASH_KEY]==0 || hashmap[pos][HASH_KEY]==vacated){
			hashmap[pos][HASH_KEY] = (int ) key;   // address 
			hashmap[pos][HASH_VAL] = (int ) value; // address  
			hashsize++;
			
			printf("insert pos=%02d cnt=%02d key=%s value=%s ok\n",pos,i,key,value);
			return 0;
		}
	}
	
	return -1;
}



int removeHash(char *key)
{
	int pos,i;
	int ret;
	
	for(i=0;i<MAX_HASH;i++)
	{
		pos = ( hash1(key) + (i *  hash2(key)) ) % MAX_HASH;
	
		if(hashmap[pos][HASH_KEY] ==0)
			return -1;
	    else  if(hashmap[pos][HASH_KEY] ==vacated)  
	    	continue;	
		else{
			
			ret = strcmp((char *)hashmap[pos][HASH_KEY], key);
			
			if(ret ==0){
			
			    printf("remove pos=%02d cnt=%02d key=%s value=%s ok\n",pos,i,(char *)hashmap[pos][HASH_KEY],hashmap[pos][HASH_VAL]);
					
				hashmap[pos][HASH_KEY] = vacated; // deleted   
				hashmap[pos][HASH_VAL] = 0;
				hashsize--;
				return 0;
			}else
				continue;
		}
		
		
	}	
	
	return -1;
}

int lookupHash(char* data, char ** outdata  )
{
	int pos,i;
	int ret=0;
	
	for(i=0;i<MAX_HASH;i++)
	{
		pos = ( hash1(data) + (i *  hash2(data)) ) % MAX_HASH;
	
		if(hashmap[pos][HASH_KEY] ==0 ){
			printf("lookup pos=%d cnt=%d err\n",pos,i);
			return -1;
		}else if(hashmap[pos][HASH_KEY] == vacated ){
			continue;
		}else{
			ret = strcmp((char*)hashmap[pos][HASH_KEY],data);
			if(ret==0){
				*outdata = (char *) hashmap[pos][HASH_VAL]; // address 
				  printf("lookup pos=%02d cnt=%02d ",pos,i);
				//printf("data=%s hash_in=%s hash_out=%s ok\n",data,hashmap[pos][0],hashmap[pos][1]);
				return 0;
			}else{
				//printf("lookup pos=%d cnt=%d ret=%d " ,pos,i,ret);
				//printf("data=%s hash_in=%s hash_out=%s fail\n",data,hashmap[pos][0],hashmap[pos][1]);
				continue;
			}
		}
		
	}
	
	return -1;
}



int main(void) {
	
	int i,cnt,ret ;
	char *ptest;
	
	char key[][50]={"James","Coach","Name","Mono","Hash","Table","Mapping","GoToHome","LetitBe","Coffee"};

	char data1[][50]={"A1","A2","A3","A4","A5","A6","A7","A8","A9","A10"};
	char data2[][50]={"B1","B2","B3","B4","B5","B6","B7","B8","B9","B10"};
	char data3[][50]={"C1","C2","C3","C4","C5","C6","C7","C8","C9","C10"};
	
	printf("1st Hash Test  \n");
	
	for(i=0;i<10;i++)
		insertHash(&key[i][0],&data1[i][0]);
	
	cnt=0;
	while(cnt<10)
	{
		ret = lookupHash(&key[cnt][0],&ptest);
		if(ret == 0){
			printf("value= %s \n",ptest);
			cnt++;
		}
	}
	
	for(i=0;i<10;i++)
		removeHash(&key[i][0]);	
	
	
	printf("\n2nd Hash Test  \n");
	
	/* second test , not remove  */
	
	for(i=0;i<10;i++)
		insertHash(&key[i][0],&data2[i][0]);
	
	cnt=0;
	while(cnt<10)
	{
		ret = lookupHash(&key[cnt][0],&ptest);
		if(ret == 0){
			printf("result= %s \n",ptest);
			cnt++;
		}
	}	
	
	for(i=0;i<10;i++)
		removeHash(&key[i][0]);		
	
	printf("\n3rd Hash Test  \n");
	/* 3rd test   */
	
	for(i=0;i<10;i++)
		insertHash(&key[i][0],&data3[i][0]); 
	
	cnt=0;
	while(cnt<10)
	{
		ret = lookupHash(&key[cnt][0],&ptest);
		if(ret == 0){
			printf("result= %s \n",ptest);
			cnt++;
		}
	}	

	return 0;
}