hash.c

program which uses hashing techniques for storing and retrieving the data. Input to the program:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include <sys/time.h>

#define TRUE 1
#define FALSE 0
#define SIZE_HASH_MAP 10
#define HASH_CONSTANT ((sqrt(5) - 1) / 2)

typedef struct node{
    int value;
    struct node *next;
}hashTableNode;

static hashTableNode* hashChained[SIZE_HASH_MAP];              // hash table

/* HASH FUNCTIONS */
int hash(int value);                                                /* hash function */                                  
void chainedHashInsert(int value);                                  /* inserts a value in the hash table, using chaining */
int chainedHashSearch(int value);                                   /* searches for a value in the hash table */


void populateHashMap(void);                     
void printList(int i);                                              /* prints the linked list stored in hashChained[i] */
void printHashMap();                                                /* prints the whole hash hashChained */
void searchNumbers(int numbersToBeSearched);                        /* searches random numbers in the hash map */

int hash(int value){
    return (SIZE_HASH_MAP * fmod((value * HASH_CONSTANT),1));
}

void chainedHashInsert(int value){
    int probe = hash(value);                                         // stores the hash value of the number to be inserted
      printf("\n Entering Insert\n");
      printf("Returned successfully from hash %d \n",probe);

    if(hashChained[probe] == NULL){                                  // if the list in hashChained[probe] is empty
	hashChained[probe] = malloc(sizeof(hashTableNode));          // then creates a new list
	hashChained[probe]->value = value;
	hashChained[probe]->next = NULL;
    }else{                                                           // if the list in hashChained[probe] is not empty
	hashTableNode *hashTableNode = hashChained[probe];
	while(hashTableNode->next!=NULL){                            // scrolls down the list
	    hashTableNode = hashTableNode->next;
	}
	hashTableNode->next = malloc(sizeof(hashTableNode));         // insert the value as the last element of the list
	hashTableNode->next->value = value;
	hashTableNode->next->next = NULL;
    }
}

int chainedHashSearch(int value){
    hashTableNode *hashTableNode = hashChained[hash(value)];      // pointer to the list stored in hashChained[hash(value)]
    while(hashTableNode!=NULL){                                   // scrolls the list
	if(hashTableNode->value==value){
	    return TRUE;                                          // if the value is found, returns TRUE
	}
	hashTableNode = hashTableNode->next;
    }
    return FALSE;                                                 // else returns FALSE
}

/* MAIN FUNCTION */
int main (int argc, char const *argv[]){

    struct timeval detail_time;  
	int search;
        int start, end;
    srand(time(NULL));
    populateHashMap();
    printf("\nsituation after insertion of random integers:\n");
    printHashMap();
    printf("\nEnter the number to be searched \n");
    scanf("%d", &search);
    gettimeofday(&detail_time,NULL);  
    start = detail_time.tv_usec;
    searchNumbers(search);
    gettimeofday(&detail_time,NULL);  
    end = detail_time.tv_usec;
    printf("\nTime taken for search %d micro seconds\n",end-start);

}


void populateHashMap(){                     // numbers to be taken from a file
    printf("Entering populate\n");
    int randomNumber;

    FILE *fp;
    fp = fopen("/home/abhiram/b.txt","r");
   
   if(fp) printf("Successfully opened the file\n");
    
   while(fscanf(fp,"%d",&randomNumber) != EOF)
   {
	   chainedHashInsert(randomNumber);     // inserts the number into the hash map
   }
  
}

void printList(int hashMapRow){
    hashTableNode *hashMapNode = hashChained[hashMapRow];      // pointer to the linked list stored in hashChained[hashMapRow]
    while(hashMapNode!=NULL){
        printf("%d ",hashMapNode->value);                           // prints out the value of the nodes
        hashMapNode = hashMapNode->next;
    }
}

void printHashMap(){                                            
    int i;
    for(i=0;i<SIZE_HASH_MAP;i++){                                   // for every row of the hash map
        printf("hashChained[%d]:\t",i);  
        printList(i);                                               // prints the list contained in it
        printf("\n");
    }
}

void searchNumbers(int numberToBeSearched){
    if(chainedHashSearch(numberToBeSearched))
        printf("Is the value %d present? YES\n",numberToBeSearched);
    else
        printf("Is the value %d present? NO\n",numberToBeSearched); 
    }