hash.cpp

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

#define LOAD_FACTOR_UPPER 1.0
#define LOAD_FACTOR_LOWER 0.25
#define INITIAL_CAPACITY 8

// ------------------- Node & Doubly Linked List -------------------
typedef struct Node {
    int key;
    int value;
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct DoublyLinkedList {
    Node *head;
    Node *tail;
} DoublyLinkedList;

void dll_init(DoublyLinkedList *list) {
    list->head = NULL;
    list->tail = NULL;
}

void dll_insert(DoublyLinkedList *list, int key, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        perror("Failed to allocate node");
        exit(EXIT_FAILURE);
    }
    newNode->key = key;
    newNode->value = value;
    newNode->prev = NULL;
    newNode->next = list->head;
    
    if (list->head)
        list->head->prev = newNode;
    else
        list->tail = newNode;
    list->head = newNode;
}

int dll_remove(DoublyLinkedList *list, int key) {
    Node *curr = list->head;
    while (curr) {
        if (curr->key == key) {
            if (curr->prev)
                curr->prev->next = curr->next;
            if (curr->next)
                curr->next->prev = curr->prev;
            if (curr == list->head)
                list->head = curr->next;
            if (curr == list->tail)
                list->tail = curr->prev;
            free(curr);
            return 1;  // Removed successfully
        }
        curr = curr->next;
    }
    return 0;  // Not found
}

int* dll_search(DoublyLinkedList *list, int key) {
    Node *curr = list->head;
    while (curr) {
        if (curr->key == key)
            return &(curr->value);
        curr = curr->next;
    }
    return NULL;
}

void dll_clear(DoublyLinkedList *list) {
    Node *curr = list->head;
    while (curr) {
        Node *next = curr->next;
        free(curr);
        curr = next;
    }
    list->head = list->tail = NULL;
}

// ------------------- Hash Table -------------------
typedef int (*HashFunc)(int key, int capacity);

int multiplicationHash(int key, int capacity) {
    const double A = 0.6180339887; // Fractional part of golden ratio
    double fraction = key * A - floor(key * A);
    return (int)(floor(capacity * fraction));
}

int divisionHash(int key, int capacity) {
    return key % capacity;
}

typedef struct HashTable {
    DoublyLinkedList *table; // pointer to C-style array of buckets
    int capacity;
    int size;
    HashFunc hashFunction;
} HashTable;

void ht_init(HashTable *ht, int initialCapacity, HashFunc hashFn, int useDivision) {
    ht->capacity = initialCapacity;
    ht->size = 0;
    ht->table = (DoublyLinkedList *)malloc(sizeof(DoublyLinkedList) * ht->capacity);
    if (!ht->table) {
        perror("Failed to allocate hash table buckets");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < ht->capacity; i++) {
        dll_init(&(ht->table[i]));
    }
    
    if (hashFn)
        ht->hashFunction = hashFn;
    else if (useDivision)
        ht->hashFunction = divisionHash;
    else
        ht->hashFunction = multiplicationHash;
}

void ht_resize(HashTable *ht, int newCapacity) {
    DoublyLinkedList *newTable = (DoublyLinkedList *)malloc(sizeof(DoublyLinkedList) * newCapacity);
    if (!newTable) {
        perror("Failed to allocate new table for resizing");
        exit(EXIT_FAILURE);
    }
    
    // Initialize new buckets.
    for (int i = 0; i < newCapacity; i++) {
        dll_init(&newTable[i]);
    }
    
    // Rehash all elements from the old table.
    for (int i = 0; i < ht->capacity; i++) {
        Node *curr = ht->table[i].head;
        while (curr) {
            int newIndex = ht->hashFunction(curr->key, newCapacity);
            dll_insert(&newTable[newIndex], curr->key, curr->value);
            curr = curr->next;
        }
        // Optional: clear old bucket if needed
        dll_clear(&ht->table[i]);
    }
    
    free(ht->table);
    ht->table = newTable;
    ht->capacity = newCapacity;
}

void ht_checkResize(HashTable *ht) {
    double loadFactor = (double)ht->size / ht->capacity;
    if (loadFactor > LOAD_FACTOR_UPPER) {
        ht_resize(ht, ht->capacity * 2);
    } else if (loadFactor < LOAD_FACTOR_LOWER && ht->capacity > INITIAL_CAPACITY) {
        ht_resize(ht, ht->capacity / 2);
    }
}

void ht_insert(HashTable *ht, int key, int value) {
    int index = ht->hashFunction(key, ht->capacity);
    if (!dll_search(&ht->table[index], key)) {
        dll_insert(&ht->table[index], key, value);
        ht->size++;
        ht_checkResize(ht);
    }
}

int ht_remove(HashTable *ht, int key) {
    int index = ht->hashFunction(key, ht->capacity);
    if (dll_remove(&ht->table[index], key)) {
        ht->size--;
        ht_checkResize(ht);
        return 1;
    }
    return 0;
}

int* ht_search(HashTable *ht, int key) {
    int index = ht->hashFunction(key, ht->capacity);
    return dll_search(&ht->table[index], key);
}

void ht_print(HashTable *ht) {
    for (int i = 0; i < ht->capacity; i++) {
        printf("Bucket %d: ", i);
        Node *curr = ht->table[i].head;
        while (curr) {
            printf("(%d, %d) -> ", curr->key, curr->value);
            curr = curr->next;
        }
        printf("NULL\n");
    }
}

void ht_clear(HashTable *ht) {
    for (int i = 0; i < ht->capacity; i++) {
        dll_clear(&ht->table[i]);
    }
    free(ht->table);
}

// ------------------- Testing -------------------
int main() {
    HashTable ht;
    ht_init(&ht, INITIAL_CAPACITY, NULL, 0); // Using multiplication hash by default

    // Insert test values
    for (int i = 0; i < 20; i++) {
        ht_insert(&ht, i, i * 10);
    }
    printf("--- After inserting 20 items ---\n");
    ht_print(&ht);

    // Remove a key and test search
    int *val = ht_search(&ht, 2);
    if (val)
        printf("Found key 2: %d\n", *val);
    else
        printf("Key 2 not found\n");

    ht_remove(&ht, 2);
    val = ht_search(&ht, 2);
    if (val)
        printf("Found key 2 after removal: %d\n", *val);
    else
        printf("Key 2 not found after removal\n");

    // Clean up
    ht_clear(&ht);
    return 0;
}