苗火 Nicholas

[Data structures]Hash table

2019-7-17 萧 写技术

#include <stdio.h>
#include <stdlib.h>

#define NULLKEY	-1
int hashsize[] = {10, 20, 40, 100, 1024};

typedef struct _HashTable{
	int *elem;
	int count;     // count of the elements of the table now;
	int sizeIndex; // hashsize[sizeIndex] is the size of the table now;
}HashTable;

int Hash(int key, int size)
{
	return key%size;
}

int Collision(int *p, int *c, int size)
{
	*p = (*p + *c)/size;
	return *p;
}

int RecreateHash(HashTable *H)
{
	int *p = NULL;
	int n = sizeof(hashsize)/sizeof(int);
	int i;
	if(H->sizeIndex < n){
		H->sizeIndex++;
		p = (int *)malloc(sizeof(int)*sizeof(hashsize[H->sizeIndex]));	
		for(i=0; i< hashsize[H->sizeIndex]; i++){
			p[i] = NULLKEY;
		}
		free(H->elem);
		H->elem = p;
		return 1;
	}else{
		return 0;
	}
}

int SearchHash(HashTable *H, int key, int *p, int *c)
{
	*p = Hash(key, hashsize[H->sizeIndex]);
	while(H->elem[*p] != NULLKEY && H->elem[*p] != key){
		++(*c);
		Collision(p, c, hashsize[H->sizeIndex]);
		if(*c > 10){
			break;
		}
	}
	if(H->elem[*p] == key){
		return 1;
	}else{
		return 0;
	}
		
}

int InsertHash(HashTable *H, int key)
{
	int c = 0;
	int p = 0;
	if( SearchHash(H, key, &p, &c) ){
		return 0;
	}else if( c < hashsize[H->sizeIndex]/2 ){
		H->elem[p] = key, 
		++H->count;
		return 1;	
	}else{
		RecreateHash(H);
		return -1;
	}
}

void main()
{
	int data[] = {1,3,4,5,8,10,11,22,44,55,66,22,99,32,41};
	//int data[] = {3,4,5,8,10,11};
	int n = sizeof(data)/sizeof(int);
	int i;
	int p;
	int c=0;
	
	HashTable H;
	H.count = 0;
	H.sizeIndex = 0;
	H.elem = (int *)malloc(sizeof(int) * hashsize[H.sizeIndex]);
	for(i=0;i<hashsize[H.sizeIndex];i++){
		H.elem[i] = NULLKEY;
	}


	printf("log.anycle.com\n\n");
	printf("Original data:\n");
	for(i=0;i<n; i++){
		printf(" %d", data[i]);
	}
	printf("\n");


	printf("Insert hash table:\n");
	i=0;
	while(i<n){
		for(i=0;i<n;i++){
			if(InsertHash(&H, data[i]) < 0){
				break;
			}
		}
	}

	printf("Print the hash table:\n");
	for(i=0;i<hashsize[H.sizeIndex];i++){
		printf(" %2d", H.elem[i]);
	}
	printf("\n");
}

标签: Data Structures data_structures