[tech] Hash example in C

 

 

 

FYI,,

  http://www.c.happycodings.com/Data_Structures/code4.html

 

Hash example

 

Basic hash example

 

#include <stdio.h>

#include <stdlib.h>

 

#define HASHSIZE    1000

#define MAXLINE     1024

 

typedef struct tnode {

 char *data;

 struct tnode *next;

} node;

 

void htable_init(node *hashtable);                        // fire up hashtable

void htable_insert(node *hashtable, char *str);           // insert data into hashtable

void htable_resolve(node *hashtable, int loc, char *str); // resolve collisions in hashtable

void htable_display(node *hashtable);                     // display hashtable

int  htable_delete(node *hashtable, char *str);           // delete an entry from hashtable

int  htable_hash(char *str);                              // hash data for hashtable

 

int main(void) {

 char line[MAXLINE];

 node *hashtable;

 

 hashtable = (node *)malloc(HASHSIZE * sizeof(node));

 

 htable_init(hashtable);

 

 while((fgets(line, MAXLINE, stdin)) != NULL)

  htable_insert(hashtable, line);

 

 htable_display(hashtable);

 

 return 0;

}

 

/* fire up hashtable */

void htable_init(node *hashtable) {

 int i = 0;

 

 for(i = 0; i < HASHSIZE; i++)

  hashtable[i].data = NULL, hashtable[i].next = NULL;

}

 

/* insert data into hashtable */

void htable_insert(node *hashtable, char *str) {

 int index = 0;

 

 /*

 // determine hash function

 */

 index = htable_hash(str);

 if(hashtable[index].data != NULL) {

  /*

  // collision occurs - resolve by chaining

  */

  htable_resolve(hashtable, index, str);

 } else {

  hashtable[index].data = calloc(strlen(str) + 1, sizeof(char));

  strcpy(hashtable[index].data, str);

 }

}

 

/* hash data for hashtable */

int htable_hash(char *str) {

 int index = 0;

 char *tmp = NULL;

 

 tmp = calloc(strlen(str) + 1, sizeof(char));

 strcpy(tmp, str);

 

 while(*tmp) {

  index += *tmp;

  tmp++;

 }

 

 index = index % HASHSIZE;

 return index;

}

 

/* resolve collisions in hashtable */

void htable_resolve(node *hashtable, int loc, char *str) {

 node *tmp;

 tmp = hashtable + loc;

 

 while(tmp->next != NULL)

  tmp = tmp->next;

  tmp->next = (node *)malloc(sizeof(node));

  tmp->next->data = calloc(strlen(str) + 1, sizeof(char));

  strcpy(tmp->next->data, str);

  tmp->next->next = NULL;

}

 

/* display hashtable */

void htable_display(node *hashtable) {

 int i = 0;

 node *target;

 

 for(i = 0; i < HASHSIZE; i++) {

  if(hashtable[i].data != NULL) {

   target = hashtable + i;

   while(target)

    /* printf("location: %d, data: %s", i, target->data), target = target->next; */

    printf("%s", target->data), target = target->next;

  } /* if */

 } /* for */

}

 

/* delete an entry from hashtable */

int htable_delete(node *hashtable, char *str) {

 node *bla;

 node *blb;

 char *tmp = NULL;

 int index = 0;

 

 index = htable_hash(str);

 

 /* no item at this location */

 if(hashtable[index].data == NULL)

  return 1;

 

 /* only one item at this location */

 if(hashtable[index].next == NULL) {

  if(strcmp(hashtable[index].data, str) == 0) {

   /* item found */

   tmp = hashtable[index].data;

   hashtable[index].data = NULL;

   free(tmp);

  }

 } else {

  /* there is a chaining case */

  bla = hashtable + index;

  /* linked list similar */

  while(bla->next != NULL) {

   if(strcmp(bla->next->data, str) == 0) {

    blb = bla->next;

    if(bla->next->next)

     bla->next = bla->next->next;

    else

     bla->next = NULL;

 

    free(blb);

   } /* if */

  } /* while */

 } /* else */

 

 return 0;

}