Unable to find out why my HashInsert and HashFind functions are wrong

Question

The question is about coalesced hashing. It is for a school assignment, I have no one to ask. I managed to pass the sample case but unable to pass any of the hidden test cases.

I am dying inside now.

Please send help.

I have attached the full code, I am only supposed to work on the HashInsert() and HashFind() functions.

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

#define TABLESIZE 37
#define PRIME     13

enum Marker { EMPTY, USED };

typedef struct _slot {
    int key;
    enum Marker indicator;
    int next;
} HashSlot;

int HashInsert(int key, HashSlot hashTable[]);
int HashFind(int key, HashSlot hashTable[]);

int hash(int key)
{
    return (key % TABLESIZE);
}

int main()
{
    int opt;
    int i;
    int key;
    int index;
    HashSlot hashTable[TABLESIZE];

    for (i = 0; i < TABLESIZE; i++) {
        hashTable[i].next = -1;
        hashTable[i].key = 0;
        hashTable[i].indicator = EMPTY;
    }

    printf("============= Hash Table ============\n");
    printf("|1. Insert a key to the hash table  |\n");
    printf("|2. Search a key in the hash table  |\n");
    printf("|3. Print the hash table            |\n");
    printf("|4. Quit                            |\n");
    printf("=====================================\n");

    printf("Enter selection: ");
    scanf("%d", &opt);
    while (opt >= 1 && opt <= 3) {
        switch (opt) {
        case 1:
            printf("Enter a key to be inserted:\n");
            scanf("%d", &key);
            index = HashInsert(key, hashTable);
            if (index < 0)
                printf("Duplicate key\n");
            else if (index < TABLESIZE)
                printf("Insert %d at index %d\n", key, index);
            else
                printf("Table is full.\n");
            break;
        case 2:
            printf("Enter a key for searching in the HashTable:\n");
            scanf("%d", &key);
            index = HashFind(key, hashTable);

            if (index != -1)
                printf("%d is found at index %d.\n", key, index);
            else
                printf("%d is not found.\n", key);
            break;

        case 3:
            printf("index:\t key \t next\n");
            for (i = 0; i < TABLESIZE; i++)
                printf("%d\t%d\t%d\n", i, hashTable[i].key, hashTable[i].next);
            break;
        }
        printf("Enter selection: ");
        scanf("%d", &opt);
    }
    return 0;
}

int HashInsert(int key, HashSlot hashTable[])
{
    // Write your code here
    int index = hash(key);

    if (hashTable[index].key == key) {
        return -1;
    }

    for (int x = 0; x < TABLESIZE; x++) {
        int index2 = hash(key + x);
        if (hashTable[index2].key == key) {
            return -1;
        }
        if (hashTable[index2].indicator == EMPTY) {
            hashTable[index2].key = key;
            hashTable[index2].indicator = USED;
            if (x > 0) {
                hashTable[index].next = index2;
            }
            return index2;
        }
    }
    return -1;
}

int HashFind(int key, HashSlot hashTable[])
{
    // Write your code here
    int index = hash(key);

    for (int x = 0; x < TABLESIZE; x++) {
        if (hashTable[x].key == key) {
            return x;
        }
    }
    return -1;
}

I do not know what is wrong with the code, I have tried many sample test cases but still did not figure it out.

Answer 1

Your approach is incorrect: you never test the hash slot indicator to check for empty slots.

In the HashFind() function, you should stop immediately if the slot indicator is EMPTY and follow the next chain and stop when next is -1.

In the HashInsert() function, you must update the next and indicator fields as you insert the key in an available spot.

Also note that the hash function must ensure that the return value is in the range 0 to TABLESIZE-1. The current implementation may return negative values for negative keys.

Here are modified versions:

int hash(int key) {
    // return index in range 0 to TABLESIZE-1
    return (unsigned)key % TABLESIZE;
}

int HashFind(int key, HashSlot hashTable[]) {
    int index = hash(key);
    for (;;) {
        if (hashTable[index].indicator == EMPTY)
            return -1;
        if (hashTable[index].key == key)
            return index;
        // follow the next chain
        index = hashTable[index].next;
        if (index < 0)
            return -1;
    }
}

int HashInsert(int key, HashSlot hashTable[]) {
    int index = hash(key);
    for (;;) {
        if (hashTable[index].indicator == EMPTY) {
            // empty slot: insert key here
            hashTable[index].indicator = USED;
            hashTable[index].key = key;
            return index;
        }
        if (hashTable[index].key == key) {
            // key already present
            return -1;
        }
        if (hashTable[index].next >= 0) {
            // follow the next chain
            index = hashTable[index].next;
        } else {
            // otherwise try and allocate a new slot
            int index2 = index;
            for (int x = 1; x < TABLESIZE; x++) {
                index2 = (index2 + PRIME) % TABLESIZE;
                if (hashTable[index2].indicator == EMPTY) {
                    // use the empty slot and link it in the chain
                    hashTable[index2].indicator = USED;
                    hashTable[index2].key = key;
                    hashTable[index].next = index2;
                    return index2;
                }
            }
            return TABLESIZE;   // table is full
        }
    }
}