hashtable.c

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

// November 7 2020
// More Data Structures
// Hash Table Implementation

#define TABLE_SIZE 1009

typedef struct entry {
    int key;
    int val;
    struct entry* next;
} entry;

typedef struct hashtable {
    struct entry** entries;
} hashtable;

int hash(int);
int search_table(hashtable*, int);
void append_entry(hashtable*, int, int);
void remove_entry(hashtable*, int, int);
void display_table(hashtable*);

int main(void) {

    hashtable* ht = (hashtable*)malloc(sizeof(hashtable));
    ht->entries = (struct entry**)malloc(TABLE_SIZE * sizeof(entry));

    int option, key, value, res;

    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->entries[i] = NULL; // zero all entries
    }

    time_t t;
    srand((unsigned) time(&t));
    for (int i = 0; i < 10; i++) {
        append_entry(ht, rand() % 100, rand() % 100);
    }

    printf("\nHash Table in C.\n");
    printf("Select an Action.\n\n");
    printf("1) Add to HashTable\n");
    printf("2) Remove From HashTable\n");
    printf("3) Display HashTable\n");
    printf("4) Search HashTable\n\n");

    for (;;) { // menu loop

        printf("$ ");
        scanf("%d", &option);

        switch(option) {
            case 1:
                printf("Enter a Reference Key.\n");
                printf("> ");
                scanf("%d", &key);
                printf("What Value Would You Like to Add?\n");
                printf("> ");
                scanf("%d", &value);
                append_entry(ht, key, value);
                break;
            case 2:
                printf("Which Key Would You Like to Remove?\n");
                printf("> ");
                scanf("%d", &key);
                printf("Which Value Would You Like to Remove?\n");
                printf("> ");
                scanf("%d", &value);
                remove_entry(ht, key, value);
                break;
            case 3:
                printf("Displaying Hash Table Data.\n");
                display_table(ht);
                break;
            case 4:
                printf("Enter Key to Search For.\n");
                printf("> ");
                scanf("%d", &key);
                res = search_table(ht, key);
                printf("Value: %d\n", res);
                break;
            default:
                printf("Invalid Entry.\n");
                break;
        }

    }

}

int hash(int seed) {
    int res = 13;
    for (int i = 0; i < 1337; i++) {
        res *= (seed * 37);
        res %= TABLE_SIZE;
    }
    return res;
}

void append_entry(hashtable* ht, int key, int val) {

    int pos = hash(key);

    entry* new = (entry*)malloc(sizeof(entry));
    new->key = key;
    new->val = val;
    new->next = NULL;

    if (ht->entries[pos] == NULL) {
        ht->entries[pos] = new;
        return;
    }

    new->next = ht->entries[pos]; 
    ht->entries[pos] = new;

}

void remove_entry(hashtable* ht, int key, int val) {

    int pos = hash(key);

    entry* temp = ht->entries[pos];
    if (temp->next == NULL && temp->val == val) {
        ht->entries[pos] = NULL;
        free(temp);
        return;
    }

    entry* prev = temp;
    while (temp->next != NULL) {

        temp = temp->next;

        if (temp->val == val) {
            prev->next = temp->next;
            free(temp);
            return;
        }

        prev = temp;

    }

    printf("Error: Element Not Found.\n");

}

void display_table(hashtable* ht) {

    for (int i = 0; i < TABLE_SIZE; i++) {
        if (ht->entries[i] != NULL) {

            printf("INDEX %d | ", i);
            entry* temp = ht->entries[i];

            while (temp != NULL) {
                printf("%d : %d -> ", temp->key, temp->val);
                temp = temp->next;
            }

            printf("NULL\n");

        }
    }

}

int search_table(hashtable* ht, int key) {

    int pos = hash(key);

    return ht->entries[pos]->val;

}