Hash table with double hashing

Question

I writing a hash table with double hashing. This code works ONLY with ASCII text files and finding the number of occurrences of each word in input file! Please point out mistakes and shortcomings.

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

#define STRINGSIZE 50 
#define EXP 2 
#define TABLESIZE 100 

struct hashtable {
    int amount; 
    char string[50]; 
};

struct hastable *insert(char *str, struct hashtable *table, int *psize, int *pbusy);
unsigned int hash(const char *str);
unsigned int hash2(const char *str);
int get(char *str, struct hashtable *table, int size);

struct hashtable *rehash(struct hashtable *table, int *size, int *pbusy) {
    int i = 0;
    int size2 = 0;
    int psize2 = *size;
    int result = 0;
    (*size) *= EXP; 
    struct hashtable *temp = (struct hashtable*)calloc(sizeof(struct hashtable), *size);
    *pbusy = 0;

    while (i < psize2) {
        temp = insert(table[i].string, temp, size, pbusy, table[i].amount);
        i++;
    }

    free(table);
    return temp;
}

int get(char *str, struct hashtable *table, int size) {
    unsigned int value = hash(str) % size; 
    int i = 0;

    while (value < size) {

        if (!strcmp(table[value].string, str)) {
            return table[value].amount;
        } 

        value = (hash(str) + i + hash2(str)) % size;
        i++;

        if (value == (size - 1)) 
            break;
    }

    return 0;
}

unsigned int hash2(const char *str) {  
    unsigned int hash = 0;

    for(; *str; str++) {
        hash += (unsigned char)(*str);
        hash -= (hash << 13) | (hash >> 19);
    }

    return hash;
}

unsigned int hash(const char *str) {
    static const unsigned int b = 378551;
    unsigned int a = 63689;
    unsigned int hash = 0;

    for (; *str; str++) {
        hash = hash * a + (unsigned char)(*str);
        a *= b;
    }

    return hash;
}

struct hastable *insert(char *str, struct hashtable *table, int *psize, int *pbusy, int amount) {
    unsigned long long int value = 0;

    if ((*pbusy) > ((2 * (*psize)) / 3)) { 
        printf("Rehash... ");
        printf("Table Size = %d", *psize);
        table = rehash(table, psize, pbusy, str);
        printf(" [OK]\n");
    }

    value = hash(str) % (*psize);

    if (!strcmp(table[value].string, str)) { 
        (table[value].amount)++;
    } else if (!strlen(table[value].string)) { 
        strcpy(table[value].string, str); 

        if (!amount){
            table[value].amount++;  
        } else {
            table[value].amount = amount;
        }

        (*pbusy)++; 
    } else if ((strcmp(table[value].string, str)) && (strlen(table[value].string))) { 
        value = (hash(str) + hash2(str)) % (*psize); 
        int i = 0;

        while (value < *psize) {

            if (!strcmp(table[value].string, str)) {
                table[value].amount++;
                break;

            } else if (!strlen(table[value].string)) {
                strcpy(table[value].string, str);

                if (!amount){
                    table[value].amount++; 
                } else {
                    table[value].amount = amount;
                }

                (*pbusy)++; 
                break;
            }

            value = (hash(str) + (i + hash2(str))) % (*psize);
            i++;

        }
    } 

    return table;
}

void WorkWithFile(char *argv[]) {   
    FILE *text = fopen(argv[1], "r"); 

    if (NULL == text) { 
        printf("Error! You was opened empty file or file doesn't exist!\n");
        return;
    } else {
        printf("File was opened\n");
        char string[STRINGSIZE] = { 0 }; 
        int size = TABLESIZE;
        int busy = 0; 
        int *psize = &size;
        int *pbusy = &busy;
        int i = 0;
        struct hashtable *table = (struct hashtable*)calloc(size, sizeof(struct hashtable)); 

        printf("Building HashTable...\n");
        while (fscanf(text, "%s", string) == 1) { 
            table = insert(string, table, psize, pbusy, 0);
        }

        fclose(text); 
        printf("[OK]\n\n");

        while (!strstr(string, "EOF")) {
            printf("Enter Substring : ");
            scanf("%s", string);
            printf("The Number of Occurrences ");
            printf("%d\n\n", get(string, table, size));
        }

        free(table);
    }
}

int main(int argc, char *argv[]) {
    printf("Welcome to HashTable Program!\n");

    if (1 < argc) {
        printf("Argument has been Received\n");
        srand(time(NULL));
        WorkWithFile(argv);
    } else {
        printf("The program requires an argument on the command line!\nPlease run this program from console with any arguments.\n");
        return 1;
    }

    return 0;
}

Answer 1

A few things to start with (there's probably more though):

• I would give your top level global constants better names. The names you've chosen are very frequent and could cause collisions. I suggest adding a name prefix to the constants, to make sure they are unique to this module. EXP is also quite vague. It seems to be the size increase when resizing the table, so we can think of a more descriptive name.

  My suggestion for naming, with the HT_ prefix for Hash Table:

  #define HT_PAYLOAD_SIZE      50
  #define HT_RESIZE_MULTIPLIER 2
  #define HT_NUM_BUCKETS       100
  

  And make sure you use your constants! The string field of hashtable is using the raw number 50, which should probably be one of your #defines instead.

• In rehash(), you got the call to calloc() wrong! The first argument is the number of elements to allocate, the second it the size of each element. This is probably what you wanted:

  struct hashtable *temp = calloc(*size, sizeof(struct hashtable));
  

• Don't cast the result of malloc/calloc/etc, actually, never cast from void* to T* in pure C code, a void pointer converts implicitly to any other pointer type, so the cast is just boilerplate.

  The one exception to this is if you plan on compiling this code as C++. A C++ compiler is much more strict about type castings, so no void* => T* conversions are allowed in such case.

• Consider using a typedef with your structs to make code less verbose. E.g.:

  typedef struct {
      int amount; 
      char string[50]; 
  } hashtable;
  

  Now you can just use hashtable without the struct tag everywhere.

• Speaking of hashtable, this struct looks more like a table bucket then a Hash Table itself. A Hash Table is usually just a collection of such buckets. You might want to clear that ambiguity by giving it a more accurate name. You should be looking at something along these lines:

  typedef struct {
      int amount; 
      char string[HT_PAYLOAD_SIZE]; 
  } TableBucket;
  
  typedef struct {
      unsigned int capacity;
      unsigned int used;
      TableBucket * buckets;
  } HashTable;
  
  HashTable * rehash(HashTable * ht, unsigned int newCapacity);
  bool insert(HashTable * ht, const char * value);
  ...
  

  Notice that now all those parameters are consolidated into a single structure, which makes your public interface a lot cleaner.

• The char *str parameter of insert is not meant to be modified, so mark it as const char * instead.

• Finally, naming your hash functions with the name of the hash algorithm would be much better than just hash and hash2. Which hashing algorithm is it? E.g.: Is it a hashCRC32? A hashOAT, hashFNV? Embed that info in the name of the function.