hash.c

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

typedef struct{
    int size;
    int count;
    char *names;
} HashTable;

typedef enum{
    false, true
} Boolean;

void rehashTable(HashTable *table);

char *copyArray(char *array, int size){
    char *newArray = (char*)malloc(size * sizeof(char));
    if (newArray == NULL){
        printf("Error allocating memory to copy array.");
        return NULL;
    }
    for (int i = 0; i < size; i++){
        newArray[i] = array[i];
    }
    return newArray;
}

int hashFunction(char name, int size){
    int ascii = name;
    return ascii % size;
}

void add(HashTable *table, char name){
    int key = hashFunction(name, table->size);
    if (table->names[key] == 0){
        table->names[key] = name;
    }else{
        while (table->names[key] != 0){
            key++;
            if (key >= table->size){
                key = 0;
            }
        }
        table->names[key] = name;
    }
    table->count++;

    if ((double) table->count / (double) table->size >= 0.7){
        printf("Rehashing!");
        rehashTable(table);
        printf("%d--->", table->size);
    }
}

void rehashTable(HashTable *table){
    char *tempArray = copyArray(table->names, table->size);
    free(table->names);

    int oldSize = table->size;
    int updatedSize = table->size * 2;
    char *newNamesArray = (char*)calloc(updatedSize, sizeof(char));
    if (newNamesArray == NULL){
        printf("Error allocating memory to the new hash table.");
    }else{
        table->names = newNamesArray;
        table->size = updatedSize;
        for (int i = 0; i < oldSize; i++){
            if (tempArray[i] != 0){
                add(table, tempArray[i]);
            }
        }
    }
}

HashTable initializeTable(int size){

    HashTable table;

    char *nameArray = (char*)calloc(size, sizeof(char));
    if (nameArray == NULL){
        printf("Error allocating memory to array of names.");
        exit(1);
    }

    table.names = nameArray;
    table.size = size;
    table.count = 0;

    return table;
}

Boolean search(HashTable *table, char name){
    int key = hashFunction(name, table->size);
    if (table->names[key] == 0){
        return false;
    }else if (table->names[key] == name){
        return true;
    }else{
        while (table->names[key] != 0){
            key++;
            if (key >= table->size){
                key = 0;
            }
            if (table->names[key] == name){
                return true;
            }
        }
        return false;
    }
}


int main(){
    const char test[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'K'};
    const char test2[] = {'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U'};
    const int tableSize = 10;
    HashTable myHashTable = initializeTable(tableSize);
    add(&myHashTable, 'A');
    add(&myHashTable, 'B');
    add(&myHashTable, 'C');
    add(&myHashTable, 'D');
    add(&myHashTable, 'E');
    add(&myHashTable, 'F');
    add(&myHashTable, 'G');
    add(&myHashTable, 'K');
    add(&myHashTable, 'H');
    add(&myHashTable, 'M');
    add(&myHashTable, 'N');
    add(&myHashTable, 'O');
    add(&myHashTable, 'P');
    fputs("\n", stdout);
    for (size_t i = 0; i < 9; i++) {
      fprintf(stdout, "Testing: %c\n", test[i]);
      if (search(&myHashTable, test[i]) == 1){
          printf("Name is in hash table.\n");
      }else {
        fprintf(stdout, "Nothing found here!\n");
      }
    }
    fputs("\n", stdout);
    for (size_t i = 0; i < 9; i++) {
      fprintf(stdout, "Testing: %c\n", test2[i]);
      if (search(&myHashTable, test2[i]) == 1){
          printf("Name is in hash table.\n");
      }else {
        fprintf(stdout, "Nothing found here!\n");
      }
    }
    return 0;
}