test_collision_strategies.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

#define TABLE_SIZE ((uint32_t)(4096 * 16)) // Size of the hash table

typedef struct {
    uint32_t hashKey;
    bool occupied;
    uint32_t chainLength;
} HashTableSlot;

typedef struct {
    HashTableSlot slots[TABLE_SIZE];
    uint32_t totalChainLength;
    uint32_t entryCount;
    uint32_t hits;
    uint32_t misses;
    uint32_t adjustments;
} HashTable;

void initTable(HashTable* table) {
    memset(table->slots, 0, sizeof(table->slots));
    table->totalChainLength = 0;
    table->entryCount = 0;
    table->hits = 0;
    table->misses = 0;
    table->adjustments = 0;
}

// Simple primary hash function
uint32_t primaryHash(uint32_t key) {
    return key % TABLE_SIZE;
}

// Secondary hash function for probing (e.g., double hashing)
uint32_t secondaryHash(uint32_t hashKey, uint32_t initialCollisionKey) {
    // Ensure probe length is non-zero and respects table size
    return (((hashKey ^ initialCollisionKey) & 7) | 1);
}

// Linear probing strategy
uint32_t linearProbing(uint32_t slotIndex, uint32_t i) {
    return 1;
}

// Linear probing strategy
uint32_t linearProbing2(uint32_t slotIndex, uint32_t i) {
    return (slotIndex & 31) | 1;
}
static bool adjustOnce;

// Insert function using a selected probing strategy
bool insert(HashTable* table, uint32_t key, uint32_t (*probingStrategy)(uint32_t, uint32_t)) {
    uint32_t hashKey = primaryHash(key);
    uint32_t initialSlotIndex = hashKey;
    uint32_t slotIndex = initialSlotIndex;
    uint32_t probeLength = 0;

    for (uint32_t i = 0;;i++) {
        HashTableSlot* slot = &table->slots[slotIndex];
        if (!slot->occupied) {
            // Found an empty slot
            slot->hashKey = hashKey;
            slot->occupied = true;
            slot->chainLength = i;
            table->totalChainLength += i;
            table->entryCount += 1;
            table->misses += i; // Increment misses for the number of probes
            if (i == 0) table->hits += 1;
            // printf("%d\n", key);
            return true;
        } else {
            // Collision occurred
            uint32_t collisionKey = slot->hashKey;
            // table->hits++; // Increment hits due to collision
            if ((!adjustOnce) || probeLength == 0)
            {
                probeLength = probingStrategy(hashKey, collisionKey);
                table->adjustments += 1;
            }
            slotIndex = (slotIndex + probeLength) % TABLE_SIZE;
            if (i > TABLE_SIZE * 2)
            {
                // printf("probing slot %d\n", slotIndex);
            }
            if (i > TABLE_SIZE * 3)
            {
                printf("Probe Limit reached aborting\n");
                return false;
            }
        }
    }
    // Table is full, insertion failed
    return false;
}
static time_t initTs;

// Run tests with the specified probing strategy
void runTests(uint32_t (*probingStrategy)(uint32_t, uint32_t), const char* strategyName, double loadFactor) {
    srand(initTs);
    HashTable table;
    int numKeys = TABLE_SIZE * loadFactor;
    initTable(&table);
    for (int i = 0; i < numKeys; i++) {
        uint32_t randomKey = rand() % (TABLE_SIZE * 4);
        if (!insert(&table, randomKey, probingStrategy)) break;
    }

    printf("Strategy: %s\n", strategyName);
    if (table.entryCount == numKeys)
    {
        printf("Average Hits: %g %%\n", (double) table.hits / table.entryCount);
        printf("adjustments: %u\n", table.adjustments);
        printf("Average Chain Length: %lf\n\n", (double)table.totalChainLength / table.entryCount);
    }
    else
    {
        printf(" !!! Failiure !!! \nn");
    }
    // printf("Load Factor: %lf\n\n", (double)table.entryCount / TABLE_SIZE);
}

int main() {
    double loadFactors[] = { 0.5, 0.75, 0.80, 0.95, 0.9999 };
    initTs = time(NULL);
    for(int i = 0; i < (sizeof(loadFactors) / sizeof(*loadFactors)); i++)
    {
        double loadFactor = loadFactors[i];
        // Test linear probing
        adjustOnce = false;
        printf("loadFacotor: %g %% -- Expected EntryCount %u\n", loadFactor, (uint32_t)(TABLE_SIZE * loadFactor));
        runTests(linearProbing, "Linear Probing", loadFactor);

        runTests(linearProbing2, "Linear Probing2", loadFactor);

        // Test secondary hashing (e.g., double hashing)
        runTests(secondaryHash, "Secondary Hashing", loadFactor);
        adjustOnce = true;

        runTests(linearProbing, "Linear Probing (adjustOnce)", loadFactor);

        runTests(linearProbing2, "Linear Probing2 (adjustOnce)", loadFactor);

        // Test secondary hashing (e.g., double hashing)
        runTests(secondaryHash, "Secondary Hashing (adjustOne)", loadFactor);

    }

    return 0;
}